По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано; для букв A, Б, В используются такие кодовые слова: А — 0, Б — 101, В — 110.
Какова наименьшая возможная суммарная длина всех кодовых слов?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование.
Нам уже известны длины букв А, Б и В, теперь необходимо подобрать кодовые слова для Г, Д, Е. У нас имеется два свободных кодовых слова — 100 и 111. Так как нужно закодировать три буквы, нужно три свободных кодовых слова. Для этого добавляем разряд в любое из них и получаем два кодовых слова с длиной 4. Таким образом, для Г мы можем взять кодовое слово 100, для Д — 1110, а для Е — 1111. Складываем длины имеющихся слов и получаем ответ: 