Равномерные и неравномерные коды. Условие Фано

Условие Фано: Никакое кодовое слово не может быть началом другого кодового слова.

Пример. По каналу связи передаются сообщения, содержащие только шесть букв: А, B, C, D, E, F. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв A, B, C используются такие кодовые слова: А — 11, B — 101, C — 0. Укажите кодовое слово наименьшей возможной длины, которое можно использовать для буквы F.

Решение:

1. строим дерево от корня;
2. буква С блокирует левую ветку (0);
3. продолжаем строить дерево от правой ветки (1);
4. буква А блокирует правую ветку (11);
5. продолжаем строить дерево от левой ветки;
6. буква В блокирует правую ветку (101);
7. продолжаем строить дерево от левой ветки;
8. для кодирования трёх букв необходимо ещё
9. построить дерево от правой ветки 4-го уровня;
10. левая ветка 4-го уровня является наименьшей длиной для буквы F (100);
11. кодируем оставшиеся буквы E и D.