Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, Ж решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г использовали соответственно кодовые слова 0, 100, 101, 111. Укажите кратчайшее возможное кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

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