По каналу связи передаются сообщения, содержащие только буквы из набора: А, М, К, Т, О, Л. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: Л — 001, А — 1. Для четырёх оставшихся букв О, М, К и Т кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова МОЛОТОК, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
Решение:
Слово МОЛОТОК. Частота букв: О (3 раза), М (1 раз), Л (1 раз), Т (1 раз), К (1 раз).
Известные коды: А = 1, Л = 001.
Так как А = 1, все остальные коды начинаются с 0.
Ветка 0 разделена на 00 и 01. Ветка 00 занята кодом Л=001 и кодом О=000.
Остаётся ветка 01 для букв М, К, Т.
Оптимальное распределение: О = 000 (длина 3), М = 010 (длина 3).
Для К и Т остаётся разбить код 011 на 0110 и 0111 (длина 4).
Назначаем: К = 4, Т = 4.
Слово МОЛОТОК: М(3) + О(3) + Л(3) + О(3) + Т(4) + О(3) + К(4).
Сумма: 3 + 3 + 3 + 3 + 4 + 3 + 4 = 23.