По каналу связи передаются сообщения, содержащие только буквы из набора: А, В, И, Н, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: Р – 0, Т – 11. Для четырёх оставшихся букв А, В, И и Н кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова ИНВАРИАНТ, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
Решение:
Р = 0, Т = 11. По условию Фано ни одно кодовое слово не может быть началом другого.
-
Так как Р = 0, все остальные коды должны начинаться с 1.
-
Так как Т = 11, все остальные коды не могут начинаться с 11.
-
Следовательно, буквы А, В, И, Н должны начинаться с 10.
Ветка «10» соответствует 1/4 кодового дерева. Чтобы разместить в ней 4 буквы (А, В, И, Н) с минимальной длиной:
— Длина 3: поместится только 2 кода (100, 101).
— Длина 4: поместится 4 кода (1000, 1001, 1010, 1011).
Значит, минимальная длина кодов для А, В, И, Н равна 4.
Слово ИНВАРИАНТ: И(4) + Н(4) + В(4) + А(4) + Р(1) + И(4) + А(4) + Н(4) + Т(2).
Сумма: 4 + 4 + 4 + 4 + 1 + 4 + 4 + 4 + 2 = 31.