По каналу связи передаются сообщения, каждое из которых содержит 15 букв А, 10 букв Б, 7 букв В и 5 букв Г (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью.При выборе кода учитывались два требования: а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование); б) общая длина закодированного сообщения должна быть как можно меньше.
Определите, чему равна длина кодового сообщения для кода, удовлетворяющего перечисленным условиям.
Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. В данной задаче требуется получить минимальную длину закодированного сообщения, поэтому кодовые слова следует подбирать так, чтобы самая часто встречающаяся буква кодировалась самым коротким кодовым словом. Исходя из этого, можно построить код следующего вида: А – 00, Б – 01, В – 10, Г – 11. Этот код удовлетворяет условию Фано, и длина всего сообщения, закодированного этим кодом, будет равна 15$·$2+10$·$2+7$·$2+5$·$2=74. Для проверки имеет смысл составить ещё один код, удовлетворяющий условию Фано, который мог бы быть оптимальным для некоторых сообщений. Например, рассмотрим такой код: А – 0, Б – 10, В – 110, Г – 111. Тогда длина закодированного сообщения будет 15$·$1+10$·$2+7$·$3+5$·$3=71. Следовательно, такой вариант нас устраивает, данный код является более выгодным, и длина сообщения, закодированного этими кодовыми словами, рана 71.
Ответ: 71