Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, в котором ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование). Известно, что для двух букв были использованы кодовые слова 10 и 110. Определите наименьшую возможную суммарную длину всех шести кодовых слов.
Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. Известны кодовые слова 10 и 110, следовательно, для других кодовых слов мы можем использовать только коды, начинающиеся с 0 или 111. Взять в качестве кодового слова 0 нельзя, т.к. в таком случае невозможно будет найти другие кодовые слова, удовлетворяющие условию Фано для оставшихся сообщений. Таким образом, можем использовать 00, 010, 011, 111. Суммарная длина всех кодовых слов – 16.
Ответ: 16