Для кодирования некоторой последовательности, состоящей из букв И, К, Л, М, Н, решили...

Question

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

Answer 1

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