Для кодирования некоторой последовательности, состоящей из шести букв: А, Б, В, Г, Д, Е — решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 10; для буквы Б — кодовое сло­ во 001. Какова наименьшая возможная сумма длин всех шести кодовых слов?

Предыдущий
вопрос Следующий
вопрос

Для нахождения минимальной суммы длин всех кодовых слов по методу Фано необходимо сначала упорядочить буквы по убыванию вероятности их появления.

Предположим, что вероятности появления букв следующие:
P(А) = 0.4
P(Б) = 0.3
P(В) = 0.1
P(Г) = 0.1
P(Д) = 0.08
P(Е) = 0.02

Сначала объединим две наименее вероятных буквы, Г и Д:
P(ГД) = 0.1 + 0.08 = 0.18

Теперь у нас остались следующие вероятности:
P(А) = 0.4
P(Б) = 0.3
P(В) = 0.1
P(ГД) = 0.18
P(Е) = 0.02

Продолжаем объединять наименее вероятные буквы:
P(Е) = 0.02
P(ВЕ) = 0.1 + 0.02 = 0.12

Остались буквы:
P(А) = 0.4
P(Б) = 0.3
P(ВЕ) = 0.12
P(ГД) = 0.18

Теперь объединяем буквы ВЕ и ГД:
P(ВЕГД) = 0.12 + 0.18 = 0.3

Остались буквы:
P(А) = 0.4
P(Б) = 0.3
P(ВЕГД) = 0.3

Теперь объединяем оставшиеся буквы:
P(А) = 0.4
P(Б) = 0.3
P(ВЕГДА) = 0.3

Таким образом, получим следующие длины кодовых слов для каждой буквы:
Длина кода для А = 3 (10)
Длина кода для Б = 3 (001)
Длина кода для В = 2 (11)
Длина кода для ГД = 2 (00)
Длина кода для Е = 3 (010)

Сумма длин всех кодовых слов: 3 + 3 + 2 + 2 + 3 = 13

Наименьшая возможная сумма длин всех шести кодовых слов равна 13.