Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В,…
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г использовали соответственно кодовые слова 0, 100, 101, 111. Укажите кратчайшее возможное кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Задача про условие Фано говорит о префиксном коде: ни одно кодовое слово не может быть префиксом другого.
Данные кодовые слова для А, Б, В, Г:
- А: 0
- Б: 100
- В: 101
- Г: 111
Найдем кратчайшее слово для Д.
- Длина 1:
- 0 уже занят кодом А; слово 1 является префиксом для 100, 101 и 111, поэтому не подходит. Нет подходящего слова длиной 1.
- Длина 2:
- Любое слово, начинающееся с 0, нарушит префиксность с кодом 0.
- Слова, начинающиеся с 1: 10 и 11. 10 является префиксом 100 и 101, 11 — префиксом 111. Значит слова длины 2 не подходят.
- Длина 3:
- Среди слов длины 3 подходящие: 100,101,111 заняты; остаётся 110.
- Проверка: 110 не является префиксом ни одного существующего кода, и ни один существующий код не является префиксом 110. Это удовлетворяет условию префиксности.
Следовательно, кратчайшее возможное кодовое слово для буквы Д — 110. Так как других допустимых слов той же длины нет, выбора с меньшим числовым значением не возникает.
Ответ: Д = 110.
