Карточки
Тесты
Главная
Курсы
Подписка
4. Кодирование и декодирование информации: #291251
Для кодирования растрового рисунка, напечатанного с использованием шести красок, применили неравномерный двоичный код. Для кодирования цветов используются кодовые слова.
| Цвет | Кодовое слово | Цвет | Кодовое слово |
|---|---|---|---|
| Белый | $0$ | Синий | |
| Зелёный | $11111$ | Фиолетовый | $11110$ |
| Красный | $1110$ | Чёрный | $10$ |
Укажите кратчайшее кодовое слово для кодирования синего цвета, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Коды длины $1$ выбрать нельзя:
- $0$ уже используется;
- $1$ является началом остальных кодовых слов.
Коды длины $2$ также не подходят:
- $00$ и $01$ начинаются с кода $0$;
- $10$ уже используется;
- $11$ является началом кодов $1110$, $11110$ и $11111$.
Проверим коды длины $3$:
- $100$ и $101$ начинаются с кода $10$;
- $111$ является началом существующих кодов;
- $110$ не начинается ни с одного имеющегося кодового слова и не является началом другого кодового слова.
Следовательно, кратчайшее подходящее кодовое слово — $110$.
20
