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