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