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

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

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

Функция линейна относительно и, значит, если минимум существует, то он лежит на границе области определения. Поэтому ищем минимум при ограничении . Используем метод неопределённых множителей Лагранжа. Перепишем ограничение в виде , или . Тогда , и решение должно удовлетворять системе из уравнений:

(1) , , ;

(2) ;

Подставив все выражений для , из (1) в (2), находим, что . Обратная подстановка этого значения в (1) даёт , , и, значит экстремум достигается в точке , .

Так как для всех , и, то и в точке экстремума квадратичная форма определена положительно: . Значит, это точка минимума.

Таким образом, минимум математического ожидания длины закодированного сообщения , где - энтропия распределения вероятностей.