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

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

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

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

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

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

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

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

Таблица 1.

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

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

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

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

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

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

Дата добавления: 2013-12-12