Прямое условие Фано:
Никакое кодовое слово (буква)
не может быть началом другого кодового слова (буквы)
Обратное условие Фано:
Никакое кодовое слово (буква)
не может быть окончанием другого кодового слова (буквы)
Для однозначного декодирования достаточно выполнение одного из условий.
А теперь на пальцах… 😉
Другим выходом из данной ситуации про ЗИМУ будет использование неравномерного кода. Правда придется воспользоваться условием Фа́но[1] см.выше. Рассмотрим следующую задачу:
ЗАДАЧА:
Для кодирования некоторой последовательности, состоящей из букв А, Б, В и Г, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В используются такие кодовые слова:
А – 010, Б – 1, В – 011.
Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
РЕШЕНИЕ:
Давайте разберем подробнее, что такое условие Фа́но:
Никакое кодовое слово (буква)
не может быть началом другого кодового слова(буквы)
Это значит:
- Если буквы имею одинаковое количество разрядов, то они не должны быть одинаковыми. В самом деле, а = 10 и в = 10 не допускаются
- Если же буквы имеют разное количество разрядов, то буква с меньшим количеством разрядов не должна быть началом буквы с бо́льшим количеством разрядов
Например:
А – 01,
Б – 011 – так быть не может, потому что буква А является началом
буквы Б
А вот так может:
А — 01,
Б — 001
Решим нашу задачу графически. Проще всего ее решать с помощью графов, а точнее частного случая графа – дерева.
Код букв может начинаться как с нуля, так и с единицы. По условию задачи буква Б – 1. Значит, код остальных букв будет начинаться с нуля. В противном случае буква Б будет являться началом для других букв.
Код буквы А, В, Г начинается с нуля. Второй символ у букв А, В по условию начинается с единицы, значит для буквы Г можно использовать ноль.
Графически описание этой задачи выглядит понятнее
ЗЕ ЭНД 🙂
[1]Ро́берт Ма́рио Фа́но (Robert Mario Fano, 11 ноября 1917, Турин, Италия — 13 июля 2016, Нейплс, Флорида, США) — итальяно-американский учёный в области информатики, профессор-эмерит факультетов электротехники и компьютерных наук в Массачусетском технологическом институте, действительный член Национальной академии наук США и ряда других национальных академий. Фано известен по работам в области теории информации, он независимо от Клода Шеннона изобрел ранний алгоритм сжатия информации и вывел неравенство Фано. /Источник: https://ru.wikipedia.org/wiki/Фано,_Роберт/