Задание базового уровня, проверяющее умение кодировать и декодировать информацию. На его выполнение отводится около двух минут.
Условие задачи
По каналу связи передаются сообщения, содержащие только 8 букв (A, B, C, D, E, F, Ж, З). Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:
- A — 00
- B — 001
- C — 0101
- D — 011
- E — 101
- F — 0100
Необходимо определить, какое наименьшее количество двоичных знаков потребуется для кодирования двух оставшихся букв (Ж и З). В ответе следует записать суммарную длину кодовых слов для этих букв.
Решение задачи
Для решения задачи используется бинарное дерево. Каждая ветвь дерева соответствует биту (0 или 1). Условие Фано гласит, что ни одно кодовое слово не должно быть началом другого кодового слова. Это значит, что при построении дерева, мы не можем использовать уже существующие кодовые слова в качестве префиксов для новых кодов.
Построим дерево, используя известные кодовые слова: При построении учитываем условие Фано – ни один код не может быть префиксом другого.
Обратите внимание, что после кода 00 нельзя использовать 000 или 0010. Аналогично для других кодов.
Нам осталось закодировать буквы Ж и З. Для минимизации длины кодовых слов, выберем кратчайшие свободные ветви:
- Буква Ж: 11 (длина 2)
- Буква З: 10 (длина 2)
Суммарная длина кодовых слов для букв Ж и З составляет 2 + 2 = 4 двоичных знака. Это наименьшее возможное количество знаков, удовлетворяющее условию Фано. Таким образом, ответ на задачу – 4.