Неравномерное кодирование для последовательности сообщений

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

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

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

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

бит/сообщение источника.

Подбирая длину блоков, при которой средняя длина кода будет наименьшей, получаем следующее определение для средней длины, кода на сообщение:

.

Здесь пишем нижнюю грань вместо минимума, поскольку наименьшее значе­ние скорости может достигаться при .

Рассматриваемое кодирование называется -кодированием (fixed to variable), поскольку блоки из фиксированного числа сообщений и кодируются ко­довыми словами переменной длины. Наша задача — связать достижимые значе­ния средней скорости -кодирования с характеристиками источника, в частно­сти, с его энтропией . Начнем с обратной теоремы кодирования.

Теорема 8.4. Для дискретного стационарного источника с энтропией для любого -кодирования имеет место неравенство

.

Теорема 8.5 (прямая теорема кодирования). Для дискретного стационар­ного источника с энтропией и для любого существует такой способ не­равномерного -кодирования, для которого

.

Итак, выбрав достаточно большую длину блоков п и применив к блокам побуквенное кодирование, мы получим кодирование со средней длиной

,

где при .

К сожалению, этот внешне оптимистический результат оказывается почти бесполезным при решении практических задач. Основное препятствие на пути его применения — это экспоненциальный рост сложности при увеличении длины блоков п. Поясним эту проблему следующим простым примером.

Предположим, что кодированию подлежат файлы, хранящиеся в памяти компьютера. Символы источника — байты и, значит, объем алфавита . При кодировании последовательностей длиной п = 2 объем алфавита уве­личивается до . Далее при п = 3, 4,... объемы алфавита будут со­ставлять , ,... Понятно, что работать с кодами та­ких размеров невозможно.

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