22. По каналу связи передаются сообщения, содержащие только шесть букв: А, Б, В, К, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Б — 010, Т — 011. Какое наименьшее количество двоичных знаков потребуется для кодирования слова КАТАРАКТА?

В слове КАТАРАКТА буква А встречается 4 раза, К — 2 раза, Т — 2 раза, Р — 1 раз.

Коды Б — 010 и Т — 011 сохраняем. Назначим А — 1, К — 00, Р — 100, В — 101. Все шесть кодовых слов различны, и ни одно не является началом другого.

Длина кодирования слова равна: 4 · 1 + 2 · 2 + 2 · 3 + 1 · 2 = 16. Меньшее значение невозможно: короткий код 1 можно отдать А, но тогда оставшиеся свободные ветви должны вместить ещё три буквы; при этом К и Р не могут обе получить коды короче двух знаков, а Т уже имеет код длины 3.

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