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