Решение: Минимальная сумма длин кодов
Для кодирования некоторой последовательности, состоящей из букв $A$, $B$, $C$, $D$, $E$, $F$, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы $A$ использовали кодовое слово $0$; для буквы $B$ — кодовое слово $10$. Какова наименьшая возможная сумма длин кодовых слов для букв $C$, $D$, $E$, $F$?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Решение по шагам
3 шагаКодовые слова $0$ и $10$ являются листьями дерева кодирования, поэтому продолжать их нельзя. Для букв $C$, $D$, $E$, $F$ остаётся ветвь, начинающаяся с $11$.
Четыре кодовых слова можно разместить на минимальной одинаковой глубине: $1100$, $1101$, $1110$, $1111$. Все они удовлетворяют условию Фано.
$$|1100|=|1101|=|1110|=|1111|=4$$Наименьшая сумма длин кодовых слов равна:
$$4+4+4+4=16$$Где здесь ошибаются
Учитывают только длины кодов $0$ и $10$.
Размещают одно из оставшихся слов как $11$, не учитывая, что тогда остальные слова должны начинаться с $110$ или $111$ и суммарная длина увеличится.