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