Решение: Кодовое слово по условию Фано
По каналу связи передаются сообщения, содержащие только четыре буквы: З, А, Р, Я; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв Я, Р, З используются такие кодовые слова: Я — $0$, Р — $101$, З — $110$. Укажите кратчайшее кодовое слово для буквы А, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наибольшим числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Решение по шагам
4 шагаКодовое слово для буквы А не может начинаться с $0$, так как код $0$ уже используется для буквы Я и будет началом нового слова.
Одноразрядное слово $1$ не подходит: оно будет началом кодовых слов $101$ и $110$. Двухразрядные слова, начинающиеся с $1$, также не подходят: $10$ является началом слова $101$, а $11$ — началом слова $110$.
Среди трёхразрядных слов подходят $100$ и $111$: ни одно из них не является началом или продолжением кодов $0$, $101$ и $110$.
Из подходящих слов выбираем слово с наибольшим числовым значением: $111 > 100$.
Где здесь ошибаются
Выбор слова, начинающегося с $0$, несмотря на наличие кодового слова $0$.
Выбор $1$, $10$ или $11$, которые являются началами уже заданных кодовых слов.
Выбор $100$ без сравнения с другим подходящим словом $111$.