ИННОВАЦИИ БИЗНЕСУ

Результат выполнения научно-исследовательской работы.

Пусть - длины кодовых слов некоторой, в общем случае счётной, кодовой системы переменной длины над -буквенным алфавитом. Пусть кодовая система используется для кодирования сообщения из источника с текущим распределением . Обозначим . В соответствии с неравенством Крафта: .

Запишем неравенство Йенсена для набора аргументов функции : . Представим логарифм отношения в левой части неравенства как разность логарифмов, сократим в правой части, и умножим неравенство на . Получим эквивалентное неравенство:

(1) ,

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

(1') ,

где

(2) .

Из (1') следует, что - минимально возможный избыток ожидаемой кодовой длины сообщения над энтропией , достигаемый тогда и только тогда, когда код используется для кодирования сообщений с вероятностями :

(3) ,

где (4) .

Последнее утверждение следует из того, что неравенство Йенсена переходит в равенство лишь в случае равных значений аргументов функции, в нашем случае при для всех , где - некоторая константа. Поскольку величина зависит лишь от кода , и не зависит от , то, следовательно, она является характеристикой внутренней, не зависящей от , составляющей избыточности при кодировании с использованием кодовой системы . В этом смысле, любая кодовая система переменной длины может быть строго оптимальной лишь в случае . Заметим также, что с использованием обозначения (2) неравенство Крафта может быть записано как (5) .