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