Кодирование информации. Задача 3-7*
В сообщении встречается 7 разных букв. При его передаче использован неравномерный двоичный код, удовлетворяющий условию Фано. Известны коды трёх букв: 1, 01, 001. Коды остальных четырёх букв имеют одинаковую длину. Какова минимальная суммарная длина всех семи кодовых слов?
Ответ
26
Решение
Построим дерево Фано для известных нам кодов букв:
Можно заметить, что свободна только ветвь 000. Чтобы получить 4 различных кода требуется 2 разряда (log24), поэтому для кодов оставшихся 4 букв необходимо 5 разрядов (к двум требуемым добавляются лидирующие три нуля). Общее количество бит кодов: 5 ⋅ 4 + 1 + 2 + 3 = 26