Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, решили...

Question

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, решили
использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А
использовали кодовое слово 1, для буквы Б – кодовое слово 001. Какова наименьшая
возможная суммарная длина всех четырёх кодовых слов? как делать это задание?

Answer 1

Из условия Фано следует, что в префиксном неравномерном двоичном коде, предусматривающем однозначное декодирование, ни одно кодовое слово не может быть началом другого. 

Таким образом, оставшиеся три кода не могут быть началом кода буквы Б, и началами кодов друг друга.

То есть коды 0 и 00 отпадают сразу, т.к. это начала буквы Б.

Если предположить, что один из кодов равен 1, и что нам нужны кратчайшие коды, значит оставшиеся коды могут быть только 01 и 011.

Если предположить, что коды двузначны, тогда кодами могут быть 01, 10 и 11.

В первом случае суммарная длина кодов равна 1+2+3+3 = 9, во втором случае - 2+2+2+3 = 9.

Оба варианта подходят, кратчайшая суммарная длина - 9

Comments

В первом варианте есть код 01, значит 010 быть не может, т.к. 01 является началом кода 010. 1+2+3+3 и 2+2+2+3 - это суммарная длина кодов. Сложите вместе цифры в кодах 1, 01, 011 и 001 - получите 1+2+3+3=9