Карточки
Тесты
Главная
Курсы
Куратор
Подписка
4. Кодирование и декодирование информации: #291226
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:
| Буква | Кодовое слово |
|---|---|
| А | $00$ |
| Б | $1000$ |
| В | $101$ |
| Г | $1001$ |
| Д | $01$ |
| Е | $110$ |
Какое наименьшее количество двоичных знаков потребуется для кодирования двух оставшихся букв?
В ответе запишите суммарную длину кодовых слов для букв: Ж, З.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Кодовые слова $00$ и $01$ занимают обе ветви, начинающиеся с $0$. Поэтому новые кодовые слова могут начинаться только с $1$.
В ветви $10$:
- коды $1000$ и $1001$ занимают всю ветвь $100$;
- код $101$ уже используется.
Следовательно, ветвь $10$ полностью занята.
В ветви $11$ код $110$ уже используется, поэтому остаётся свободной только ветвь $111$.
Код $111$ нельзя использовать для одной буквы, так как тогда он станет началом любого другого кода в этой ветви, а других свободных ветвей нет.
Поэтому два кратчайших возможных кодовых слова: $1110$ и $1111$.
Длина каждого кодового слова равна $4$. Их суммарная длина: $4+4=8$.
20
