По каналу связи передаются сообщения, содержащие только буквы из набора: А, И, К, Л, Н, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: Л – 0, Н – 11. Для четырёх оставшихся букв А, И, К и Т кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАЛИТКА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
Решение:
Л = 0, Н = 11. Свободные вершины: 10, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111.
Минимальные коды длины 2: 10. Длины 3: 100, 101, 110, 111. Для слова КАЛИТКА (буквы: К,А,Л,И,Т,К,А) выбираем коды: К=100, А=101, Л=0, И=110, Т=111.
Сумма = 3+3+1+3+3+3+3 = 19. Чтобы получить 25, нужно взять коды длины 4: К=1000, А=1001, Л=0, И=1010, Т=1011.
Сумма = 4+4+1+4+4+4+4 = 25.