Question

По каналу связи передаются сообщения, содержащие 16 букв А, 8 букв Б, 4 буквы В и 4 буквы Г (других букв нет). Каждую букву кодируют двоичной последовательностью. При выборе кода учитываются два требования:

а) ни одно кодовое слово не является началом другого (условие Фано — необходимо для однозначного декодирования);

б) общая длина закодированного сообщения должна быть как можно меньше.

Какой код следует выбрать?

1) А: 0, Б: 10, В: 110, Г: 111
2) А: 0, Б: 10, В: 01, Г: 11
3) А: 1, Б: 01, В: 011, Г: 001
4) А: 00, Б: 01, В: 10, Г: 11

Accepted Answer

1

Answer

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

Вариант 2: код А = 0 является началом кода В = 01. Не подходит.

Вариант 3: код Б = 01 является началом кода В = 011. Не подходит.

Варианты 1 и 4 удовлетворяют условию Фано.

**Расчёт длины закодированного сообщения:**

Для варианта 1:
- Длина = $16 	imes 1 + 8 	imes 2 + 4 	imes 3 + 4 	imes 3 = 16 + 16 + 12 + 12 = 56$ бит

Для варианта 4:
- Длина = $16 	imes 2 + 8 	imes 2 + 4 	imes 2 + 4 	imes 2 = 32 + 16 + 8 + 8 = 64$ бита

Вариант 1 даёт меньшую длину сообщения (56 < 64), поэтому его следует выбрать.

![Рисунок](https://ege.sdamgia.ru/formula/svg/16/163066d49e83130ee8a8df5841cf4e76.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/40/4054316fec44f4810d297fdb074af864.svg)

Задание №8Системы счисления и арифметикаЕГЭ по информатике