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