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