№№ заданий Пояснения Ответы Ключ Добавить инструкцию Критерии
Источник Раздел кодификатора Ф ИПИ Справка
PDF-версия PDF-версия (вертикальная) PDF-версия (крупный шрифт) PDF-версия (с большим полем) Версия для копирования в MS Word
Задания
Задание 5 № 10406

По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано; для букв A, Б, В используются такие кодовые слова: А — 1, Б – 010, В – 001.

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

Решение.

Перечислим возможные коды в порядке возрастания длины. Стоит сразу сказать, что любой код, начинающийся с 1, не подходит, так как код А - 1, поэтому смотрим только на те, что начинаются с 0.

0 - нельзя, Б, В начинаются с 0.

01 - нельзя из-за Б.

00 - нельзя из-за В.

000 - можно использовать, пусть это будет код Д.

011 - также можно использовать, но если мы его возьмём, то не будет больше кодов, которые можно будет взять, так как все коды, начинающиеся с 1, уже нельзя брать, а все коды, начинающиеся с 0 и имеющие длину больше трёх, начинаются с одной из этих строк: 011, 010, 001, 000.

Рассмотрели все коды с длинами от 1 до 3, поэтому теперь достаточно взять любые два подходящие кода длины 4. Например, 0111 и 0110.

В сумме длина кодов 1 + 3 + 3 + 3 + 4 + 4 = 18.