Условие Фано - зачем оно?

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

Неравномерный код раздаёт частым буквам короткие слова, редким — длинные. Сообщение выходит заметно короче. Но вместе с экономией приходит вопрос, которого раньше не было: где кончается одна буква и начинается следующая? Разделителей-то нет — идёт сплошной поток нулей и единиц.

Строка, которую можно прочитать двумя способами

Возьмём кодовые слова: А = 0, Б = 01, В = 10. Выглядит безобидно. Передадим три бита: 010.

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

Почему? Код буквы А — это 0, и ровно с этого нуля начинается код буквы Б. Приёмник дошёл до нуля и встал: то ли буква кончилась, то ли только началась.

Условие Фано

Правило, которое чинит эту беду, укладывается в одну строку:

Никакое кодовое слово не является началом другого кодового слова.

Всё. Ни слова сверх того. Такой код называют ещё префиксным — «префикс» и есть начало.

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

Проверь себя