Question

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

Answer 1

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