Question

Для кодирования последовательности из букв А, Б, В, Г и Д используется неравномерный двоичный код, обеспечивающий однозначное декодирование:

- А — 0
- Б — 100
- В — 1010
- Г — 111
- Д — 110

Требуется сократить длину кодового слова для одной из букв так, чтобы код остался однозначно декодируемым. Коды остальных букв не должны меняться. Какой из предложенных вариантов допустим?

1) для буквы В — 101
2) это невозможно
3) для буквы В — 010
4) для буквы Б — 10

Accepted Answer

1

Answer

Идея решения: проверить каждый вариант на соответствие условию Фано — ни один код не должен быть префиксом другого.

Текущий набор кодов удовлетворяет условию Фано. При сокращении кода для какой-либо буквы новый код не должен быть началом никакого существующего кода и не должен содержать никакой существующий код как свой префикс.

**Вариант 1: В → 101**

Новый набор: А — 0, Б — 100, В — 101, Г — 111, Д — 110.

Проверяем:
- 0 не является префиксом других кодов ✓
- 100 не является префиксом других кодов ✓
- 101 не является префиксом других кодов ✓
- 110 не является префиксом других кодов ✓
- 111 не является префиксом других кодов ✓

Ни один код не является началом другого. Условие Фано выполнено. ✓

**Вариант 3: В → 010**

Новый набор: А — 0, Б — 100, В — 010, Г — 111, Д — 110.

Код буквы А (0) является префиксом кода буквы В (010). Условие Фано нарушено. ✗

**Вариант 4: Б → 10**

Новый набор: А — 0, Б — 10, В — 1010, Г — 111, Д — 110.

Код буквы Б (10) является префиксом кода буквы В (1010). Условие Фано нарушено. ✗

Только первый вариант сохраняет свойство однозначного декодирования.

Задание №4Представление информацииЕГЭ по информатике