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