Условие Фано
Начнем с примера. Допустим мы закодировали 4 буквы наборами единиц и нулей A-0, B-1, C-10, D-11. Тогда мы непременно сталкиваемся с проблемами при попытке декодировать данное нам закодированное сообщение. Например, сообщение 1001 мы можем декодировать как BAAB, либо как CAB. Чтобы избежать таких разночтений было сформулировано условие Фано. Условие Фано звучит так. Никакое кодовое слово не может быть началом другого кодового слова. Под кодовым словом понимается набор нулей и единиц, которым кодируется конкретная буква. Проблема с нашим примером в том, что кодовое слово для B является началом кодовых слов для C и D. Например, если бы мы закодировали A-00, B-01, C-10, D-11, то сообщение 1001 декодировалось бы однозначно как CB.
Построение графов
Определить удовлетворяет ли набор кодовых слов условию Фано мы можем, построив граф. Например, у нас есть набор кодовых слов: A-01, B-000, C- 1, D-011, E-00. Графы строятся следующим образом: сверху пишутся 0 и 1 и от них рисуются две ветки на концах которых тоже находится 0 и 1 и так далее до бесконечности.
Далее, читая сверху вниз, находим каждую из букв, например буква A – это 0 и 1. Значит мы выбираем левый граф и (потому что A начинается с 0), далее идем вправо (потому что вторая цифра – это 1). Далее под единицей ставим черту, стираем всё что из нее выходило (потому что никакие другое кодовое слово уже не может начинаться с того же набора цифр) и пишем букву A.
Аналогично определяем буквы B и C.
Попытаемся добавить букву D-011. Как видите, чтобы была возможность добавления буквы D, мы должны от буквы A продолжить дерево. Это и значит, что для пары букв A и D было нарушено условие Фано.
При попытке же добавить букву E-00, получится, что мы должны стереть, все, что находится ниже буквы E и тем самым стереть букву B, это также означает, что условие Фано для пары B и E нарушено.
Чтобы закодировать все 5 букв и не нарушить условие Фано, мы можем, например, букву D представить как 0011, а букву E как 0010.
