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