Передача сообщений

📑 Задание

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

📑 Решение.

1) В сообщениях используются 4 символа с вероятностями:

• Г: 32/(8+8+16+32)=0.5
• В: 16/(8+8+16+32)=0.25
• А и Б: 8/(8+8+16+32)=0.125

2) Присвоим коды, используя принцип: чем чаще встречается символ, тем короче код.

• Г:0, В:11, А:100, Б:101 или
• Г:0, В:10, А:110, Б:111 или
• Г:1, В:00, А:010, Б:011 или
• Г:1, В:01, А:110, Б:111

3) Вычислим длину одного сообщения, состоящего из всех четырех символов:

• 1+2+3*2=9

📑 Ответ: 9