Энтропия и эффективность кодирования

Рассмотрим случайную переменную с множеством возможных значений (х₁ х₂,..., x_N), принимаемых с вероятностями (P₁, Р₂,..., P_n), где Р, означает вероятность резуль­тата x_i. Определим нижнюю границу средней длины кода. Мы знаем, что мерой информации для х_i является log(1/Р). Поэтому в идеальном слу­чае мы сможем представить значение x_i - кодовым словом длины L_i = log(l/P_i) бит. Однако в большинстве случаев log(l/P_i) не является целым числом, и лучшее, что мы можем сделать, — это выбрать ближайшее целое число L_i такое что

Умножая на Р_i и суммируя по всем кодовым словам, получаем:

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

Можно показать, что код Хаффмана удовлетворяет данному неравенству. При­мер приводится в таблице. Средняя длина кода составляет 2,184, а энтропия рав­на 2,167. Обратите внимание на то, что не все отдельные кодовые слова удовлет­воряют неравенству. Однако в среднем это неравенство выполняется.