Карточки
Тесты
Главная
Курсы
Куратор
Подписка
4. Кодирование и декодирование информации: #291242
Для кодирования некоторой последовательности, состоящей из букв $A$, $B$, $C$, $D$, $E$, $F$, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы $A$ использовали кодовое слово $00$; для буквы $B$ — кодовое слово $01$. Какова наименьшая возможная сумма длин кодовых слов для букв $C$, $D$, $E$, $F$?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Кодовые слова $00$ и $01$ занимают все ветви, начинающиеся с $0$. Поэтому коды букв $C$, $D$, $E$, $F$ должны начинаться с $1$.
Код $1$ использовать нельзя, так как тогда он станет началом остальных кодовых слов.
Минимальную сумму получим, если использовать четыре кодовых слова длины $3$:
$100$, $101$, $110$, $111$.
Они удовлетворяют условию Фано. Сумма их длин равна $3+3+3+3=12$.
Меньшая сумма невозможна: если использовать код длины $2$, например $10$, то три остальных кода придётся размещать в ветви $11$, и их минимальные длины составят $3$, $4$ и $4$. Тогда сумма будет равна $2+3+4+4=13$.
20
