Задание 4. Кодирование и условие Фано

Задание 4 демонстрационного варианта ЕГЭ-2027 (ФИПИ).

По каналу связи передаются сообщения, содержащие только буквы из набора: Б, К, Л, О, Н. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Б – 00, Н – 010, Л – 111. Для двух оставшихся букв К и О кодовые слова неизвестны. Какое количество двоичных знаков требуется для кодирования слова КОЛОБОК, если известно, что оно закодировано минимально возможным количеством двоичных знаков?

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

1. Проведите ветки и повесьте известные коды. Из каждого узла две ветки: влево $0$, вправо $1$. Тогда 00 – это два шага влево, 010 – влево, вправо, влево, 111 – три шага вправо. В конце каждого пути ставим букву.
2. Посмотрите, какие концы остались свободны. Свободный конец – ветка, на которой нет буквы и которая не лежит по дороге ни к одной из них. Считать ничего не нужно, они видны на картинке: 10, 011 и 110. Самый короткий – 10, 2 шага от корня.

Два правила читаются прямо с картинки:

• под буквой дерево обрывается. Буква обязана быть листом – в этом всё условие Фано. Поэтому ниже 00, 010 и 111 брать нечего;
• свободный конец можно продолжить (100, 0110 и так далее) – но незачем: чем длиннее код, тем длиннее запись, а нас просят самую короткую.

Вот это дерево, только живое. Коды у букв О и К пусты – впишите их сами и посмотрите, что станет с пунктирными ветками.

Свободных концов 3, букв без кода 2. Кто какой получит – решает частота.

1. Посчитайте буквы в слове. В слове КОЛОБОК: О – 3, К – 2.
2. Самый короткий конец – самой частой букве. О достаётся 10, всего 2 бита.
3. Оставшийся конец – второй букве. Как только 10 занято, свободных концов остаётся два – 011 и 110, оба длиной 3. Длина одна и та же, так что К берёт 011: из равных принято брать меньшее как двоичное число.
4. Сложите биты по всему слову. Длина кода каждой буквы, помноженная на то, сколько раз буква встречается.

Ответ: 17.

1. Взяли не конец, а развилку. Путь 01 кажется свободным: буквы на нём нет. Но он лежит по дороге к 010, то есть это развилка, а не конец, и буква на ней перестала бы быть листом. Впишите в виджете К = 01 – строка покраснеет, а буква К в дереве повиснет на развилке над Н.
2. Отдали короткий код редкой букве. Набор кодов получился неоптимальным, запись – не самой короткой: 18 битов вместо 17.
3. Ответили не на тот вопрос. Перечитайте вопрос задачи и ответьте именно на него.