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

Ответ

Проверено экспертом

Автор - Silverpain

Итак первые два символа кодируются кодовыми словами 0 и 10. Найдём для оставшихся трех символов наиболее короткое представление, удовлетворяющее условию Фано. Из двузначных чисел можно взять 11, но тогда невозможно подобрать трехзначное число для четвертого символа, по этому не берем. Единственное подходящее трехзначное число - 110 (111 не подходит по той же причине. что и 11). Аналогично выбираем числа 1110 и 11110.
В итоге получается ряд: 0, 10, 110, 1110, 11110.
Общая длина = 1+2+3+4+5=15