Для передачи сообщений нужно использовать неравномерный двоичный код

Пример задания:

По каналу связи передаются сообщения, содержащие только 4 буквы: А, И, С, Т. В любом сообщении больше всего букв А, следующая по частоте буква — С, затем — И. Буква Т встречается реже, чем любая другая.

Для передачи сообщений нужно использовать неравномерный двоичный код, допускающий однозначное декодирование; при этом сообщения должны быть как можно короче. Шифровальщик может использовать один из перечисленных ниже кодов. Какой код ему следует выбрать?

1. А−0, И−1, С−00, Т−11
2. С−1, И−0, А−01, Т−10
3. А−1, И−01, С−001, Т−000
4. С−0, И−11, А−101, Т−100

Решение:

Проверим каждый код на однозначное декодирование и выберем наиболее оптимальный из них. Оптимальным вариантом будет тот, при котором самые используемые буквы будут иметь самый короткий код.

Вариант 1

Данный код не является однозначно декодируемым, так как 00 можно расшифровать как АА или С, а 11 можно расшифровать как ИИ или Т.

Вариант 2

Данный код не является однозначно декодируемым, так как 10 можно расшифровать как СИ или Т, а 01 можно расшифровать как ИС или А.

Вариант 3

Данный код является однозначно декодируемым, так как он является префиксным (ни одно слово не является началом другого слова).

Вариант 4

Данный код также является однозначно декодируемым, так как он является префиксным (ни одно слово не является началом другого слова).

Значит, нужно сделать выбор между вариантами 3 и 4. Вариант 3 предпочтительнее, так как буква А в сообщениях встречается чаще всего и она имеет самый короткий код именно в варианте номер 3.

Ответ: 3