Кодирование информации. Задача 3-1
Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К — кодовое слово 10. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?
Примечание: Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Ответ
9
Решение
Построим дерево Фано, при этом ветвь 0 занята буквой Н, а ветвь 10 - буквой К.
Свободной остается ветвь 11, из нее можем построить еще две ветви для букв Л и М. Коды букв:
Н - 1
К - 10
Л - 110
М - 111
Считаем количество бит: 1 + 2 + 3 + 3 = 9.