По каналу связи передаются сообщения, содержащие только шесть букв: Т, Е, Н, С, И, В. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для букв…
По каналу связи передаются сообщения, содержащие только шесть букв: Т, Е, Н, С, И, В. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для букв известны: Т — 010, Е — 0100, Н — 1100, С — 01000, И — 0110, В — 1110. Как можно сократить код для буквы Н, чтобы сохранялось свойство однозначности декодирования? Если таких кодов несколько, в качестве ответа указать код наименьшей длины.
Ключ: сохранить однозначное декодирование значит оставить префиксный код (ни один код не должен быть префиксом другого).
Разбираем варианты для буквы Н, если остальные коды оставлять без изменений:
- Т (010), Е (0100), С (01000), И (0110), В (1110) – все начинаются либо с 0, либо с 11.
- 01 недопустим: код 01 является префиксом кодов 010, 0100, 01000, 0110.
- 11 недопустим: код 11 является префиксом коду 1110 (В).
Остаются варианты длиной 2 бита для Н:
- 00 — не является префиксом ни одного из существующих кодов, и ни один существующий код не начинается с 00.
- 10 — тоже не является префиксом ни одного из существующих кодов, и ни один существующий код не начинается с 10.
Таким образом, минимальная длина для кода буквы Н — 2 бита. Возможны варианты:
- Н = 00 (предпочтительно как простой пример)
- Н = 10 (альтернатива)
Итоговая кодовая таблица (пример с Н = 00):
- Т — 010
- Е — 0100
- Н — 00
- С — 01000
- И — 0110
- В — 1110
Примечание: оба варианта длины 2 бита (00 и 10) удовлетворяют условию Фано для данной фиксации остальных кодов. Если требуется выбрать один конкретный, можно привести Н = 00.
