Кодирование информации. Задача 3-6*
В сообщении встречается 10 разных букв. При его передаче использован неравномерный двоичный префиксный код. Известны коды трех букв: 11, 100, 101. Коды остальных семи букв имеют одинаковую длину. Какова минимальная суммарная длина всех 10 кодовых слов?
Ответ
36
Решение
Построим дерево Фано для известных нам кодов букв:
Можно заметить, что ветвь, которая начинается с 1 занята полностью, поэтому коды остальных букв должны начинаться с 0. Чтобы получить 7 различных кодов требуется 3 разряда (log27), поэтому для кодов оставшихся 7 букв необходимо 4 разряда (к трем требуемым добавляется лидирующий разряд, равный 0). Общее количество бит кодов: 7 ⋅ 4 + 2 + 3 + 3 = 36