Карточки
Тесты
Главная
Курсы
Куратор
Подписка
4. Кодирование и декодирование информации: #291214
Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв К, Л, М, Н использовали соответственно кодовые слова $00$, $01$, $100$, $110$. Для двух оставшихся букв — П и Р — кодовые слова неизвестны.
Укажите кратчайшее возможное кодовое слово для буквы П, при котором код допускает однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Код длины $1$ выбрать нельзя:
- $0$ является началом кодов $00$ и $01$;
- $1$ является началом кодов $100$ и $110$.
Коды длины $2$ также не подходят:
- $00$ и $01$ уже используются;
- $10$ является началом кода $100$;
- $11$ является началом кода $110$.
Рассмотрим коды длины $3$. Коды $101$ и $111$ не нарушают условие Фано:
- для буквы П можно выбрать $101$;
- для буквы Р можно выбрать $111$.
Из возможных кодов минимальной длины код $101$ имеет наименьшее числовое значение.
20
