Избыточность кодирования. Нижняя граница средней длины кодирования

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

Для доказательства первой теоремы напомним одно свойство логарифма, которое заключается в том, что график функции лежит ниже касательной к ней в точке , и следовательно, выполняется неравенство . Это свойство иллюстрирует рис.6.6.

Теорема. Для произвольного источника и префиксного кода избыточность кодирования неотрицательна, т. е. .

Рис. 6.6. График функции log2(x) и касательной к ней в точке x=1

Доказательство.

С учетом отмеченного выше неравенства для функции каждое слагаемое можно оценить сверху следующим образом:

После суммирования получим

причем последнее неравенство следует из неравенства Крафта (6.3) для префиксного кода и равенства . Таким образом, , что доказывает утверждение теоремы.

Из доказанной теоремы следует, что энтропия источника является нижней границей средней длины кодирования. Для источников, у которых вероятности являются целыми отрицательными степенями 2, эта граница достижима. Легко проверить, что для источника с распределением вероятностей средняя длина кодирования равна 1,75 и совпадает с энтропией источника.

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

Рис. 6.7. График функции [x]

Теорема. Для каждого источника найдется префиксный код , избыточность которого не превышает единицы, т. е. .

Пусть , где функция "потолок". Тогда

Это означает, что числа удовлетворяют неравенству Крафта. Тогда из теоремы Крафта следует, что найдется префиксное кодирование , такое что . Оценим избыточность этого кодирования

Теорема доказана.

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