6.5. Энтропия и кодирование

Докажем теперь фундаментальное соотношение между средней длиной кода и энтропией Пусть задан некоторый мгновенный код. Пусть длины кодовых слов по некоторому основанию Из неравенства Крафта (4.5.1) имеем

Определим теперь числа

Тогда, конечно, Можно считать, что задают распределение вероятностей. Поэтому можно использовать фундаментальное неравенство (6.4.2).

Представляя логарифм частного в виде разности логарифмов, заметим, что один член равен энтропии, так что

Применив к правой части неравенства соотношение (6.5.2), получаем

Иопользуя неравенство Крафта, имеем так что

Отбрасывание этого члена только усиливает неравенство. Поэтому

или

где средняя длина кодового слова

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

Для хороших двоичных кодов Поэтому строгое неравенство в двоичном случае имеет место, только если