Карточки
Тесты
Главная
Курсы
Подписка
4. Кодирование и декодирование информации: #291258
По каналу связи передаются шифрованные сообщения, содержащие только десять букв: $A$, $B$, $C$, $D$, $E$, $F$, $S$, $X$, $Y$, $Z$; для передачи используется неравномерный двоичный код. Для кодирования букв используются кодовые слова.
| Буква | Кодовое слово | Буква | Кодовое слово |
|---|---|---|---|
| $A$ | $F$ | $0110$ | |
| $B$ | $0111$ | $S$ | $0011$ |
| $C$ | $100$ | $X$ | $0101$ |
| $D$ | $101$ | $Y$ | $0010$ |
| $E$ | $0100$ | $Z$ | $000$ |
Укажите кратчайшее кодовое слово для буквы $A$, при котором код удовлетворяет условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Коды длины $1$ выбрать нельзя:
- $0$ является началом кодов $000$, $0010$, $0011$, $0100$, $0101$, $0110$, $0111$;
- $1$ является началом кодов $100$ и $101$.
Проверим коды длины $2$:
- $00$ является началом кодов $000$, $0010$, $0011$;
- $01$ является началом кодов $0100$, $0101$, $0110$, $0111$;
- $10$ является началом кодов $100$ и $101$;
- $11$ не является началом ни одного известного кодового слова и само не начинается ни с одного известного кода.
Следовательно, кратчайшее подходящее кодовое слово для буквы $A$ — $11$.
20
