Решение: Кодирование по условию Фано
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 00, Б — 1000, В — 101, Г — 1001, Д — 01, Е — 110. Какое наименьшее количество двоичных знаков потребуется для кодирования двух оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв: Ж, З.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Решение по шагам
4 шагаПостроим двоичное дерево кодовых слов. Слова 00 и 01 полностью занимают ветви, начинающиеся с 0.
В ветви, начинающейся с 1, кодовые слова 1000, 1001 и 101 занимают соответствующие свободные участки. Кодовое слово 110 занимает одну из ветвей после 11.
Оставшиеся две буквы нельзя закодировать словом 111, поскольку тогда для второй буквы пришлось бы использовать продолжение 111, а кодовое слово стало бы началом другого. Поэтому минимальные подходящие слова — 1110 и 1111.
Суммарная длина двух кодовых слов равна:
$$4+4=8$$Где здесь ошибаются
Использовать кодовое слово 111 для одной буквы и продолжение 1110 или 1111 для другой, нарушив условие Фано.
Считать свободными ветви, которые уже являются продолжениями заданных кодовых слов.