Префиксные коды.


Неравномерный код с разделителем

Условимся, что разделителем отдельных кодов букв будет последовательность 00 (признак конца знака), а разделителем слов - 000 (признак конца слова - пробел). Довольно очевидными оказываются следующие правила построения кодов:

· код признака конца знака может быть включен в код буквы, поскольку не существует отдельно (т.е. коды всех букв будут заканчиваться 00);

· коды букв не должны содержать двух и более нулей подряд в середине (иначе они будут восприниматься как конец знака);

· код буквы (кроме пробела) всегда должен начинаться с 1;

· разделителю слов (000) всегда предшествует признак конца знака; при этом реализуется последовательность 00000 (т.е., если в конце кода встречается комбинация ...000 или ...0000, они не воспринимаются как разделитель слов); следовательно, коды букв могут оканчиваться на 0 или 00 (до признака конца знака).

В соответствии с перечисленными правилами построим кодовую Таблицу 1 для букв русского алфавита, основываясь на приведенных ранее вероятностях появления отдельных букв.

Таблица 1.

 

Теперь, учитывая, что среднее для значений случайных независимых величин определяется как , можно найти среднюю длину кода для данного способа кодирования:

 

Поскольку для русского языка, как указывалось ранее, H1(r)=4,356 бит, избыточность данного кода, согласно , составляет:

 

это означает, что при данном способе кодирования будет передаваться приблизительно на 14% больше информации, чем содержит исходное сообщение.

Аналогичные вычисления для английского языка дают значение , что при H1(e) = 4,036 бит приводят к избыточности кода .

Рассмотрев один из вариантов двоичного неравномерного кодирования, попробуем найти ответы на следующие вопросы: возможно ли такое кодирование без использования разделителя знаков? Существует ли наиболее эффективный (оптимальный) способ неравномерного двоичного кодирования?

Суть первой проблемы состоит в нахождении такого варианта кодирования сообщения, при котором последующее выделение из него каждого отдельного знака (т.е. декодирование) оказывается однозначным без специальных указателей разделения знаков. Наиболее простыми и употребимыми кодами такого типа являются так называемые префиксные коды, которые удовлетворяют следующему условию (условию Фано):