Карточки
Тесты
Главная
Курсы
Подписка
4. Кодирование и декодирование информации: #291245
Для кодирования некоторой последовательности, состоящей из букв $A$, $B$, $C$, $D$, $E$, $F$, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы $A$ использовали кодовое слово $0$; для буквы $B$ — кодовое слово $10$. Какова наименьшая возможная сумма длин кодовых слов для букв $C$, $D$, $E$, $F$?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Код $0$ занимает всю ветвь, начинающуюся с $0$.
Код $10$ занимает ветвь, начинающуюся с $10$. Поэтому кодовые слова для букв $C$, $D$, $E$, $F$ должны начинаться с $11$.
Чтобы получить четыре кратчайших кодовых слова, разделим ветвь $11$ на четыре равноправные ветви: $1100$, $1101$, $1110$, $1111$.
Каждое кодовое слово имеет длину $4$ и удовлетворяет условию Фано.
Сумма длин: $4+4+4+4=16$.
20
