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