Решение: Кодирование слова по Фано
По каналу связи передаются сообщения, содержащие только буквы из набора: А, К, М, О, Т, Ч. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Ч – 00, М – 01, А – 11. Для трёх оставшихся букв К, О и Т кодовые слова неизвестны. Какое количество двоичных знаков требуется для кодирования слова КОТОМКА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Решение по шагам
4 шагаКодовые слова 00, 01 и 11 занимают три ветви двоичного дерева. Чтобы условие Фано выполнялось, неизвестные слова могут располагаться только в ветви 10.
Для трёх кодовых слов в ветви 10 минимально возможные длины — 3, 4 и 4. Более короткое слово длины 3 выгоднее назначить букве, которая встречается чаще всего.
Буквы К и О встречаются в слове КОТОМКА по два раза, поэтому одной из них можно назначить длину 3, а другой — длину 4. Букве Т назначается длина 4. Для М и А длина кодового слова равна 2.
Суммарное количество двоичных знаков равно:
$$2 \cdot 3 + 2 \cdot 4 + 1 \cdot 4 + 1 \cdot 2 + 1 \cdot 2 = 22$$Где здесь ошибаются
Назначают трём неизвестным буквам кодовые слова одинаковой длины 3, хотя в ветви 10 для этого недостаточно свободных кодовых слов.
Забывают учесть, что буквы К и О встречаются в слове по два раза.
Складывают длины кодовых слов для букв, а не учитывают количество повторений букв в слове.