Шешімі: Кодовое слово по Фано
По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова. Укажите кратчайшее кодовое слово для буквы Т, при котором код будет удовлетворять условию Фано. Если таких слов несколько, укажите код с наибольшим числовым значением.
Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
| Буква | Кодовое слово | Буква | Кодовое слово |
|---|---|---|---|
| А | 00 | Л | 1001 |
| Б | 1000 | Р | 1110 |
| Е | 010 | С | 1010 |
| И | 011 | Т | |
| К | 1011 | У | 110 |
Шешім по шагам
3 қадамПроверим кодовые слова небольшой длины. Код длины 1 невозможен, так как 0 и 1 являются началами уже имеющихся кодов.
Все кодовые слова длины 2 и 3 также конфликтуют с существующими кодами: 00, 01, 10 и 11 уже являются началами кодовых слов, а их продолжения заняты.
Среди слов длины 4 проверяем свободные ветви двоичного дерева. Слово 1110 уже используется, а 1111 не является началом или продолжением ни одного другого кодового слова.
Где здесь ошибаются
Выбрать кодовое слово, которое является началом уже существующего слова.
Не проверить конфликт с кодом 1110.
Выбрать более длинное слово, не убедившись, что существует подходящее слово минимальной длины.