4.3
Критерий однозначности декодирования
Здесь мы
рассматриваем алфавитное кодирование для алфавитов
и
, задаваемое схемой
:
а1 – В1
а2 – В2
. . . . .
(S)
ar –
Вr.
и полагаем
, т. е. источник сообщений порождает все множество слов в
алфавите
. Очевидно, что алфавитное кодирование порождает отображение
множества
в
множество
. Обозначим через
образ множества
в этом отображении.
В случае,
когда отображение
на
взаимно однозначно,
возможно декодирование, т. е. возможно по коду В однозначно восстановить исходное сообщение А, кодом которого является В.
В этом случае говорят также, что алфавитное кодирование является взаимно
однозначным.
Пример. Рассмотрим алфавитное кодирование, для
которого
,
и схема имеет вид:
а1 – b1
а2 – b1 b2.
Пусть
и
являются кодами слов
и
соответственно. Очевидно,
что если
, то
.
Процесс
декодирования происходит следующим образом. Произведем разбиение слова В,
, на элементарные коды. Для этого заметим, что перед каждым
вхождением буквы b2 в слове В находится буква b1. это позволяет выделить все пары (b1b2). Оставшаяся часть слова В будет состоять из букв b1. если теперь заменить каждую пару (b1b2) на а2,
а каждую из оставшихся букв b1 – на а1, то получим слово А, являющееся прообразом слова В.
Пусть В = b1 b1 b2 b1 b2 b1 b1 b1 b2.
После выделения пар мы получим разбиение на элементарные коды
В = b1( b1 b2)(
b1 b2) b1 b1(
b1 b2),
из которого
находим слово
А = а1 а2
а2 а1 а1
а2.
Можно
привести большое количество примеров, в которых алфавитное кодирование не будет
обладать свойством взаимной однозначности. В связи с этим возникает вопрос:
можно ли по схеме
алфавитного
кодирования узнать, обладает алфавитное кодирование свойством взаимной
однозначности или нет. трудность
решения задачи состоит в том, что для непосредственной проверки взаимной
однозначности необходимо просмотреть бесконечное число слов.
Определение. Пусть слово В имеет вид
.
Тогда слово
называется началом или префиксом слова В, а
– концом слова В. При этом пустое слово
и само слово В считаются началами и концами слова В. Все начала и концы слова В, отличные от него самого, называются собственными.
Определение. Схема
обладает свойством префикса, если для любых i и j(
) слово Bi не является
префиксом слова B j.
Теорема 1 Если схема
обладает свойством
префикса обладает свойством префикса, то алфавитное кодирование будет взаимно
однозначным.
Предыдущий
пример показывает, что условие префиксности не
является необходимым:
может не обладать
свойством префикса, а алфавитное кодирование, определяемое
будет взаимно
однозначным.