По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Н, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: К – 1, Н – 001. Для трёх оставшихся букв А, З и Т кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАНТАТА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
Решение:
К = 1, Н = 001. По условию Фано:
Все остальные коды должны начинаться с 0 (так как К = 1).
Так как Н = 001, коды не могут начинаться с 001.
Чтобы минимизировать длину слова КАНТАТА, нужно присвоить самый короткий код букве А (встречается 3 раза).
Попробуем выделить букве А код длины 2: А = 01.
Тогда ветка 01 занята. Остаётся ветка 00.
Под веткой 00 занят код Н = 001.
Оставшееся место под веткой 00 (код 000) позволяет разместить 2 кода длины 4 (0000, 0001).
Эти коды длины 4 получат буквы З и Т.
Длины кодов: К = 1, Н = 3, А = 2, Т = 4.
Слово КАНТАТА: К(1) + А(2) + Н(3) + Т(4) + А(2) + Т(4) + А(2).
Сумма: 1 + 2 + 3 + 4 + 2 + 4 + 2 = 18.