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