По каналу связи передаются сообщения, которые содержат только восемь букв: Г, Е, Ж, С, Т, У, Ч и Ь. Для передачи используется двоичный код, удовлетворяющий условию Фано. Коды для…
По каналу связи передаются сообщения, которые содержат только восемь букв: Г, Е, Ж, С, Т, У, Ч и Ь. Для передачи используется двоичный код, удовлетворяющий условию Фано. Коды для некоторых букв известны: Буква Кодовое слово Ж 00 Г 111 У 1100 Ч 011 Е 1000 С 1001 Т 1101 Укажите возможный код минимальной длины для буквы Ь. Если их несколько, выберите код с максимальным числовым значением. Примечание. Условие Фано означает, что никакое кодовое слово не составляет начало другого кодового слова. Это позволяет однозначно расшифровывать закодированные сообщения.
Задача: для восьми букв (Г Е Ж С Т У Ч Ь) подобрать кодовое слово для Ь, при этом код должен быть префикс-фree (условие Фано). Известны коды для остальных букв: Ж 00, Г 111, У 1100, Ч 011, Е 1000, С 1001, Т 1101.
- Проверка длины 1
- Коды длины 1: 0 или 1.
- 0 был бы префиксом кодов 00 и 011 — конфликт.
- 1 был бы префиксом кодов 111, 1100, 1101, 1000, 1001 — конфликт. Значит, длина 1 невозможна.
- Проверка длины 2
- Возможные двоичные слова: 01, 10, 11 (поскольку 00 уже занят кодом Ж).
- 01 является префиксом 011 — конфликт.
- 10 является префиксом 1000 и 1001 — конфликт.
- 11 является префиксом 111, 1100, 1101 — конфликт. Значит, длина 2 невозможна.
Итак, минимальная возможная длина равна 3.
- Проверка длины 3 Рассматриваем все 3-битные слова и проверяем два условия:
- ни одно существующее кодовое слово не должно быть префиксом нового,
- новое слово не должно быть префиксом ни одного существующего кода.
Из существующих кодов видно, что префиксами надо избегать слов, начинающихся с 00, 11 и т.д.
- 000: начинается с 00, значит 00 — префикс 000 → недопустимо.
- 001: начинается с 00 → недопустимо.
- 010: ни один существующий код не является префиксом 010, и 010 не является префиксом ни одного существующего кода. Допустимо.
- 011: уже занят кодом Ч.
- 100: является префиксом 1000 и 1001 → недопустимо.
- 101: ни один существующий код не является префиксом 101, и 101 не является префиксом ни одного существующего кода. Допустимо.
- 110: является префиксом 1100 и 1101 → недопустимо.
- 111: уже занят кодом Г.
Получаем допустимые варианты длины 3: 010 и 101. Среди них выбираем код с максимальным числовым значением: 101 (2^2 + 0·2 + 1 = 5) больше, чем 010 (2).
Ответ
- Код для буквы Ь: 101
- Длина кодового слова: 3
- Такая запись сохраняет свойство префикс-фree и является минимальной по длине.
