Карточки
Тесты
Главная
Курсы
Куратор
Подписка
4. Кодирование и декодирование информации: #291225
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово $0$; для буквы Б — кодовое слово $10$. Какова наименьшая возможная сумма длин кодовых слов для букв В, Г, Д, Е?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Кодовое слово $0$ запрещает использовать другие слова, начинающиеся с $0$.
Кодовое слово $10$ запрещает использовать слова, начинающиеся с $10$. Слово $1$ также выбрать нельзя, поскольку оно является началом слова $10$.
Следовательно, все четыре новых кодовых слова должны начинаться с $11$.
Код $11$ использовать нельзя, так как тогда он стал бы началом остальных кодовых слов. Наименьшая сумма длин получается при выборе четырёх слов длины $4$: $1100$, $1101$, $1110$, $1111$.
Они удовлетворяют условию Фано. Сумма их длин равна $4+4+4+4=16$.
20
