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