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