Задание №4 — Префиксные коды, условие Фано
По каналу связи передаются сообщения, содержащие только шесть букв: А, Б, В, Г, Д, Е и Ж. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:
| Буква | Кодовое слово |
| А | 00 |
| Б | 01 |
| В | 100 |
| Г | 1010 |
| Д | 10110 |
Какое наименьшее количество двоичных знаков потребуется для кодирования двух оставшихся букв? В ответе для такого способа кодирования запишите минимально возможное произведение длин кодовых слов для букв: Е, Ж.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Правильный ответ
9
Пояснение
Решение:
Известно: А — 00, Б — 01, В — 100, Г — 1010, Д — 10110. Найдём свободные вершины дерева.
- Ветвь 0 занята целиком: 00 — А, 01 — Б.
- В ветви 10: слово 100 — это В, слово 1010 — это Г; в ветви 1011 слово 10110 — это Д, свободна вершина 10111.
- Ветвь 11 свободна целиком.
Свободные места: 11 (2 знака) и 10111 (5 знаков). Кодовые слова нужны буквам Е и Ж:
- занять оба свободных места: 11 и 10111 — сумма длин ;
- разбить вершину 11 на 110 и 111 — сумма длин .
Второй способ короче, и меньше 6 знаков получить нельзя. Произведение длин при нём равно .
Ответ: 9