§ № Префиксный двоичный код
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. При этом используются следующие коды: А — 1110, Б — 0, В — 10, Г — 110. Каким кодовым словом может быть закодирована буква Д? Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.
Решение
Имеющиеся слова образуют префиксный код: , , , не являются началами друг друга. По прямому условию Фано новое слово тоже нельзя расположить на ветви, которая уже занята одним из этих слов.
Однобитное слово уже занято, а слово было бы началом слов , и . Среди двухбитных занято; и начинаются с , а является началом слов и . Среди трёхбитных занято; является началом , а слова, начинающиеся с или , снова попадают в занятые ветви.
У слова есть соседняя свободная ветвь той же длины — . Оно не начинается ни одним из прежних слов и не является их началом, поэтому код с добавленным словом остаётся префиксным и однозначно декодируемым. Поскольку все варианты меньшей длины исключены, это кратчайшее слово.
