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 Если схема  обладает свойством префикса обладает свойством префикса, то алфавитное кодирование будет взаимно однозначным.

Предыдущий пример показывает, что условие префиксности не является необходимым:  может не обладать свойством префикса, а алфавитное кодирование, определяемое  будет взаимно однозначным.