Какой код из приведённых ниже следует выбрать для кодирования букв А, Б, В и Г?
По каналу связи передаются сообщения, каждое из которых содержит 15 букв А, 10 букв Б, 6 букв В и 4 буквы Г (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью. При выборе кода учитывались два требования:
а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование);
б) общая длина закодированного сообщения должна быть как можно меньше.
Какой код из приведённых ниже следует выбрать для кодирования букв А, Б, В и Г?
1) А:1, Б:01, В:001, Г:111
2) А:1, Б:01, В:10, Г:111
3) А:00, Б:01, В:10, Г:11
4) А:100, Б:101, В:11, Г:0
Ответ:
Решение:
Ни одно кодовое слово не является началом другого: А является началом Г в 1-й и 2-й вариантах.
Общая длина закодированного сообщения должна быть как можно меньше.
3) А:00 (15), Б:01 (10), В:10 (6), Г:11 (4)
2.15+2.10+2.6+2.4 = 70
4) А:100 (15), Б:101 (10), В:11 (6), Г:0 (4)
3.15+3.10+2.6_1.4 = 61
Ответ: 3