8. Общая задача: символы различной длины

Мы переходим к рассмотрению обшей задачи с символами различной длины; докажем, что предшествующий результат сохраняет силу: наиболее эффективным является такое кодирование, которое дает различным символам наиболее вероятное априорное распределение частот. Мы выведем также это наиболее вероятное распределение и покажем его связь с (4.11) и (4.12).

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

Введем общее число символов и относительные частоты :

откуда

Перепишем (4.51) в следующем виде:

(4.54)

Логарифм полного числа Р различных сообщений, которые можно составить, переставляя различные символы, по-прежнему выражается формулой (4.46):

Информация, полученная при выборе одного из Р сообщений, равна , в соответствии с нашим определением (1.1). Все эти сообщения имеют одинаковую длительность 7, так как они состоят из одинаковых чисел различных символов и могут считаться априори равновероятными. Мы желаем найти наиболее вероятное распределение, или, что то же, сделать максимальной информацию, содержащуюся в сообщении. Это значит, что мы делаем максимальным , учитывая условия (4.53) и (4.54). Максимум находится методом множителей Лагранжа. Запишем условие)

где два произвольных множителя будут определены ниже. Переменными являются . Дифференцируя (4.55), получаем:

Подставляя это выражение в (4.56), находим:

Мы должны рассматривать теперь как произвольные независимые величины. Полный дифференциал может быть равен нулю, только если все скобки равны нулю:

Подстановка (4.59) в (4.58) дает:

Учитывая условие (4.53), мы должны выбрать

и теперь (4.59) сводится к

Произвольная постоянная р определяется из условия (4.53):

Запишем

и вспомним, что мы можем иметь более чем один символ определенной длительности. Пусть имеется символов длительности . Тогда (4.62) запишется в виде

а это совпадает с (4.11) (см. п. 3).

Если рассмотреть бесконечно длинные сообщения, то снова обнаружится совпадение асимптотического распределения п. 3 и распределения, дающего максимум информации. Это последнее (см. распределение п. 7) является также наиболее вероятным распределением, равно как и среднее распределение. Распределение (4.61) дает число сообщений (4.55):

или

в соответствии с (4.54) и определением X. Наиболее вероятное распределение Р в свою очередь совпадает с величиной соответствующей всем возможным распределениям, и пропускная способность, в соответствии с (4.43), равна

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

в соответствии с (4.61). Наибольший вещественный корень уравнения (4.62) соответствует наибольшему значению X, получаемому в качестве решения уравнения (4.12), и дает на основании (4.64) самое вероятное распределение и тем самым наибольшее значение Р.

Применяя наиболее эффективный код и распределение символов, соответствующее наиболее вероятному, мы получаем для информации на символ:

где есть средняя длительность символа, когда вероятности различных символов выражены соотношением (4.61). Из (4.65) и (4.67) получаем для скорости передачи

Эта формула очень похожа на (4.50).