По каналу связи передаются сообщения, содержащие только буквы из набора: А, К, Н, О, П, Ч, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: К – 01, Я – 001. Для пяти остальных букв А, О, Н, П и Ч кодовые слова неизвестны. Какое количество двоичных потребуется для кодирования слова КНОПОЧКА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?

Известные кодовые слова: К = 01, Я = 001. Поэтому кодовое слово 0 использовать нельзя, так как оно было бы началом обоих известных слов.

Для минимальной длины можно выбрать, например, такие кодовые слова:

• К = 01;
• Я = 001;
• О = 10;
• Н = 110;
• П = 111;
• Ч = 0000;
• А = 0001.

Эти слова удовлетворяют условию Фано: ни одно из них не является началом другого.

Слово «КНОПОЧКА» содержит буквы: К, Н, О, П, О, Ч, К, А.

Длина кодирования:

К: 2 знака, Н: 3 знака, О: 2 знака, П: 3 знака, О: 2 знака, Ч: 4 знака, К: 2 знака, А: 4 знака.

Складываем: 2 + 3 + 2 + 3 + 2 + 4 + 2 + 4 = 22.

Меньшую длину получить нельзя: при распределении пяти неизвестных кодовых слов по ветвям двоичного дерева минимальные возможные суммы длин равны 21, 20, 18, 18 и 20 знаков; минимум равен 18 знакам для неизвестных букв. Два вхождения буквы К дают ещё 2 + 2 = 4 знака.

Ответ: 22 двоичных знака.