Префиксные коды.
Неравномерный код с разделителем
Условимся, что разделителем отдельных кодов букв будет последовательность 00 (признак конца знака), а разделителем слов - 000 (признак конца слова - пробел). Довольно очевидными оказываются следующие правила построения кодов:
· код признака конца знака может быть включен в код буквы, поскольку не существует отдельно (т.е. коды всех букв будут заканчиваться 00);
· коды букв не должны содержать двух и более нулей подряд в середине (иначе они будут восприниматься как конец знака);
· код буквы (кроме пробела) всегда должен начинаться с 1;
· разделителю слов (000) всегда предшествует признак конца знака; при этом реализуется последовательность 00000 (т.е., если в конце кода встречается комбинация ...000 или ...0000, они не воспринимаются как разделитель слов); следовательно, коды букв могут оканчиваться на 0 или 00 (до признака конца знака).
В соответствии с перечисленными правилами построим кодовую Таблицу 1 для букв русского алфавита, основываясь на приведенных ранее вероятностях появления отдельных букв.
Таблица 1.
Теперь, учитывая, что среднее для значений случайных независимых величин определяется как , можно найти среднюю длину кода для данного способа кодирования:
Поскольку для русского языка, как указывалось ранее, H1(r)=4,356 бит, избыточность данного кода, согласно , составляет:
это означает, что при данном способе кодирования будет передаваться приблизительно на 14% больше информации, чем содержит исходное сообщение.
Аналогичные вычисления для английского языка дают значение , что при H1(e) = 4,036 бит приводят к избыточности кода .
Рассмотрев один из вариантов двоичного неравномерного кодирования, попробуем найти ответы на следующие вопросы: возможно ли такое кодирование без использования разделителя знаков? Существует ли наиболее эффективный (оптимальный) способ неравномерного двоичного кодирования?
Суть первой проблемы состоит в нахождении такого варианта кодирования сообщения, при котором последующее выделение из него каждого отдельного знака (т.е. декодирование) оказывается однозначным без специальных указателей разделения знаков. Наиболее простыми и употребимыми кодами такого типа являются так называемые префиксные коды, которые удовлетворяют следующему условию (условию Фано):