Карточки
Тесты
Главная
Курсы
Подписка
4. Кодирование и декодирование информации: #291250
По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У; для передачи используется неравномерный двоичный код. Для кодирования букв используются кодовые слова.
| Буква | Кодовое слово |
|---|---|
| А | $00$ |
| Б | $1000$ |
| Е | $010$ |
| И | $011$ |
| К | $1011$ |
| Л | $1001$ |
| Р | $1100$ |
| С | $1010$ |
| Т | $1101$ |
| У |
Укажите кратчайшее кодовое слово для буквы У, при котором код удовлетворяет условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Коды длины $1$ выбрать нельзя:
- $0$ является началом кодов $00$, $010$, $011$;
- $1$ является началом остальных кодов.
Коды длины $2$ также не подходят:
- $00$ уже используется;
- $01$ является началом кодов $010$ и $011$;
- $10$ является началом кодов $1000$, $1001$, $1010$, $1011$;
- $11$ является началом кодов $1100$ и $1101$.
Проверим коды длины $3$:
- $000$ и $001$ начинаются с кода $00$;
- $010$ и $011$ уже используются;
- $100$ и $101$ являются началами существующих кодов;
- $110$ является началом кодов $1100$ и $1101$;
- $111$ подходит.
Код $111$ не начинается ни с одного существующего кодового слова и сам не является началом другого кодового слова.
20
