Решение: Кодирование по условию Фано
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:
В — 00
Г — 10
Д — 010
Е — 110
Ж — 0110
З — 111
Какое наименьшее количество двоичных знаков потребуется для кодирования двух оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв А, Б.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Решение по шагам
4 шагаПроверим свободные ветви дерева кодов. Кодовые слова 00, 10, 010, 110, 0110 и 111 уже заняты, поэтому новое слово не может начинаться с одного из них и не может быть началом другого кодового слова.
После слова 0110 остаётся свободная ветвь 0111. Одно кодовое слово можно было бы взять равным 0111, но тогда второго слова в этой ветви разместить нельзя: слово 0111 стало бы его началом.
Разделим ветвь 0111 ещё на один уровень. Получаем два кодовых слова: 01110 и 01111. Они имеют одинаковую длину 5 и не являются началами друг друга или известных слов.
Находим суммарную длину кодовых слов для букв А и Б.
$$5 + 5 = 10$$Где здесь ошибаются
Выбрать слово 0111 и попытаться добавить второе слово с тем же началом, нарушив условие Фано.
Не учитывать, что для двух кодовых слов ветвь 0111 нужно разделить ещё на один уровень.
Сложить сами кодовые слова вместо их длин.