Кодирование информации. Задача 3-1

Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К — кодовое слово 10. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?

Примечание: Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Ответ
9
Решение

Построим дерево Фано, при этом ветвь 0 занята буквой Н, а ветвь 10 - буквой К.

Дерево Фано КЛМН

Свободной остается ветвь 11, из нее можем построить еще две ветви для букв Л и М. Коды букв:

Н - 1

К - 10

Л - 110

М - 111

Считаем количество бит: 1 + 2 + 3 + 3 = 9.