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