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