Двоичные коды и условие Фано

В двоичном сообщении видна одна цепочка нулей и единиц. Границы между буквами в ней обычно не отмечены. Код должен позволять восстановить эти границы и получить единственное исходное сообщение. Условие Фано даёт простой способ организовать такой код.

Символ, кодовое слово и сообщение

Алфавит — набор допустимых символов: например, букв А, Б, В, Г. Каждому символу назначается непустая цепочка нулей и единиц — кодовое слово. Один ноль или одна единица занимает один бит. Длина кодового слова равна числу его битов.

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

Код сообщения получается приписыванием кодов букв друг к другу. Для АБАГ это выглядит так:

\underbrace{\mathtt{0}}_{\text{А}}\ \underbrace{\mathtt{10}}_{\text{Б}}\ \underbrace{\mathtt{0}}_{\text{А}}\ \underbrace{\mathtt{111}}_{\text{Г}}\;\longrightarrow\;\mathtt{0100111}.

Пробелы и подписи слева показывают границы только в объяснении. Справа записана передаваемая последовательность из семи битов.

Почему условие Фано помогает читать код

Префикс — начало кодового слова. Код удовлетворяет условию Фано, если никакое кодовое слово не является началом другого. Разные буквы при этом не могут иметь одинаковые коды.

В учебном наборе выше после первого нуля уже понятна буква А: ни одно другое кодовое слово с нуля не начинается. После единицы чтение продолжается. Если следующая цифра — ноль, получилось слово \mathtt{10}, то есть Б. Если следующая цифра — единица, нужен ещё один бит, чтобы отличить В от Г.

Так сообщение читается слева направо: найденное кодовое слово завершается, затем начинается поиск следующего. В момент завершения не требуется угадывать, является ли оно только началом более длинного слова: условие Фано исключает эту ситуацию.

Как это показывает двоичное дерево

В начале пути ещё нет битов. Каждая ветвь добавляет 0 или 1. Путь до буквы задаёт её кодовое слово, а число пройденных ветвей — его длину. Ниже показан тот же учебный набор.

Узлы с буквами — листья. Если поместить букву во внутренний узел, код этой буквы станет началом кодов ниже него. Поэтому готовый код закрывает все свои продолжения. И наоборот: начало уже готового кода нельзя объявить отдельным кодовым словом.

Свободное начало можно оставить для одной буквы или разделить на два продолжения. Например, из \mathtt{10} получаются \mathtt{100} и \mathtt{101}. Теперь вместо одного слова длины 2 есть два слова длины 3. Само \mathtt{10} одновременно с ними использовать нельзя.

Длина набора кодов и длина сообщения

Сумма длин кодовых слов считает каждый код один раз. Для учебного набора это 1+2+3+3=9. Но сообщение АБАГ занимает 7 бит: код А встречается дважды, коды Б и Г — по одному разу, а код В не встречается.

Если буква встречается n раз, а её код имеет длину \ell, она добавляет в сообщение n\ell битов. Общая длина получается сложением этих вкладов:

L=\sum_i n_i\ell_i.

Здесь i обозначает букву алфавита, n_i — число её повторений в сообщении, \ell_i — длину её кода. Для АБАГ:

L=2\cdot1+1\cdot2+0\cdot3+1\cdot3=7.

При подборе кодов более частой букве выгоднее назначить более короткое из доступных слов. Например, если две буквы встречаются 3 и 1 раз, длины 2 и 4 дадут 3\cdot2+1\cdot4=10 битов. Обратное назначение даст 3\cdot4+1\cdot2=14. При таком обмене меняются только подписи двух свободно назначаемых слов; заданные условием коды переставлять нельзя.

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

Нарушение Фано и неоднозначность — разные утверждения

Условие Фано гарантирует однозначное декодирование, но не является единственным способом его обеспечить. Например, два кода А — \mathtt{0} и Б — \mathtt{01} нарушают условие Фано. Однако сообщение из этих кодов можно однозначно разбирать с конца: последняя единица означает код Б целиком, \mathtt{01}; последний ноль означает код А, \mathtt{0}. После удаления последнего кода разбор продолжается тем же способом.

Другой набор — \mathtt{0},\ \mathtt{01},\ \mathtt{10} — уже даёт неоднозначность: цепочка \mathtt{010} разбивается и как \mathtt{0}\mid\mathtt{10}, и как \mathtt{01}\mid\mathtt{0}. Значит, одного нарушения Фано недостаточно для вывода о неоднозначности. В задании с явным требованием Фано проверяется именно это требование.

Применение в заданиях

Как найти кратчайшее кодовое слово и при этом оставить место для остальных букв? Почему минимум суммы длин кодов может отличаться от минимума длины сообщения?

Эти вопросы разобраны на конкретных примерах в статье «Задание №4. Выбор кодов и длина сообщения».