Задания
Версия для печати и копирования в MS Word
Тип 4 № 13616
i

По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко пять букв: П, И, Л, О, Т. Для пе­ре­да­чи ис­поль­зу­ет­ся дво­ич­ный код, удо­вле­тво­ря­ю­щий усло­вию Фано. Для буквы И ис­поль­зу­ет­ся ко­до­вое слово 1; для буквы О ис­поль­зу­ет­ся ко­до­вое слово 01.

Ка­ко­ва ми­ни­маль­ная общая длина ко­до­вых слов для всех пяти букв?

 

При­ме­ча­ние. усло­вие Фано озна­ча­ет, что ни одно ко­до­вое слово не яв­ля­ет­ся на­ча­лом дру­го­го ко­до­во­го слова.

Спрятать решение

Ре­ше­ние.

Сле­ду­ю­щая буква ко­до­во­го слова долж­на ко­ди­ро­вать­ся кодом длины 3, так как 0, 11 и 10 мы взять не можем. Под­хо­дя­щий трех­знач­ный код  — 000 или 001. Если мы возь­мем оба, то тогда наша пятая буква не может на­чи­нать­ся на 1, 01, 0, 00, 000, 001. Та­ко­го кода не су­ще­ству­ет, зна­чит, мы можем взять толь­ко 1 из них. Тогда чет­вер­тая и пятая буква будут ко­ди­ро­вать­ся ми­ни­мум че­ты­ре­мя би­та­ми. Можно за­ме­тить, что нам по­дой­дет код 0001 и 0000. Тогда длина равна 4 + 4 + 3 + 2 + 1  =  14.

 

Ответ:14.


Аналоги к заданию № 13589: 13616 Все

Раздел кодификатора ФИПИ: