Вопрос № 10. 2.5. Теорема кодирования для дискретных источников без памяти (неравномерные коды)

2.5. Теорема кодирования для дискретных источников без памяти
(неравномерные коды)

 

Все предыдущие рассуждения проводились в предположении, что кодирование осуществлялось побуквенно: каждому элементарному сообщению которое уместно также именовать буквой, сопоставлялось кодовое слово. В действительности реальный источник обычно генерирует элементарные сообщения (буквы) одно за другим последовательно во времени. Рассмотрим блок из последовательных букв , где верхний индекс (i), т.е. номер элемента последовательности, как и ранее, отвечает дискретному времени. Указанный блок может трактоваться как новое, укрупненное сообщение, с тем чтобы объектом кодирования служили теперь не буквы, а подобные -блоки. Убедимся, что при таком подходе среднюю длину неравномерного кода можно сделать сколь угодно близкой к энтропии источника.

Ограничимся анализом стационарного ДИБП, генерирующего буквы из ансамбля . Будем кодировать не отдельные буквы а последовательности букв (блоки) длины , т.е. , где блок . Напомним, что для стационарных дискретных источников m -мерные вероятности не зависят от временного сдвига. Кроме того, ДИБП формирует буквы независимо друг от друга, т.е. при нахождении энтропии множества -блоков можно использовать свойство аддитивности.

При мощности множества мощность множества , образованного всеми возможными векторами , равна . Тогда, согласно (1.3), энтропия определится как

.

Рассмотрим последовательность , где

, (2.5)

энтропия на букву блока длины , получившей наименование удельной энтропии. Пусть – длина слова, кодирующего вектор ( -блок) , а – средняя длина кода при заданной длине блока букв . Тогда на основании теоремы 2.2.3 существует префиксный код, для которого

В силу аддитивности энтропии для ДИБП так что . Тогда число кодовых символов, в среднем затрачиваемых на одну букву, определяемое как , удовлетворяет соотношению

,

и при .

Итогом приведенных рассуждений является следующая теорема.

Теорема 2.5.1. Кодируя достаточно длинные последовательности букв стационарного ДИБП, можно сделать среднее число кодовых символов на букву источника сколь угодно близким к значению энтропии алфавита источника .

Теоремы 2.2.3 и 2.5.1 проливают новый свет на роль энтропии как характеристики дискретного источника. Ранее эта роль представлялась довольно абстрактной: ее значение выступало как характеристика непредсказуемости источника. Теперь же установлен строгий количественный смысл энтропии как минимально возможного числа двоичных символов, затрачиваемых на кодирование буквы источника. Как было доказано на примере неравномерного кодирования ДИБП, к этой границе всегда можно подойти сколь угодно близко, кодируя достаточно длинные блоки букв источника.

 

2.6. Теорема кодирования для дискретных источников без памяти
(равномерные коды)

 

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

Этого можно избежать, если заранее ограничиться лишь равномерными кодами. Вопрос, однако, в том, откуда могут возникнуть резервы экономии в рамках кода с одинаковой длиной слов. Казалось бы, если длина всех слов равна n, для однозначного кодирования L сообщений (или букв) источника потребуется иметь n, как минимум, не меньше, чем , что может весьма значительно превысить фактическую энтропию ансамбля мощности L. В рассмотренных ранее вариантах кодирования источника сближение затрат в символах кода на букву с энтропией источника как раз и обеспечивалось за счет неравномерности кода, когда часто возникающим сообщениям отвечали короткие слова, а редким – длинные. При равномерном кодировании подобный шанс отсутствует, и, тем не менее, фундаментальная роль энтропии как асимптотически достижимого предела экономности кодирования сохраняется. Механизм экономии при этом оказывается иным, основанным на отказе от непременной однозначности кодирования всех сообщений. Для его реализации все множество сообщений разбивается на два подмножества, первое из которых кодируется однозначно, тогда как сообщения из второго отображаются с нарушением однозначности, скажем, в одно и то же слово. Ясно, что сообщения из второго подмножества не восстанавливаются однозначно по кодовому слову, что означает появление ошибки декодирования, вероятность которой равна общей вероятности выдачи источником сообщений, принадлежащих второму подмножеству.

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

Теорема 2.6.1. Пусть – независимые, одинаково распределенные, дискретные случайные величины, имеющие математическое ожидание и конечную дисперсию. Тогда для любых положительных e и d найдется такое N, что для всех вероятность большего, чем e, отклонения среднего арифметического величин от , не превзойдет d:

. (2.6)

Доказательство этой теоремы можно найти в любом учебнике по теории вероятностей.

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

,

где ,– независимые одинаково распределенные случайные величины с математическим ожиданием .

К последовательности таких случайных величин можно применить закон больших чисел (2.6), согласно которому для всех достаточно больших и заданных положительных

,

или

. (2.7)

Определение 2.6.1. Последовательности символов длины , для которых выполняется соотношение (2.7), называются типичными (высоковероятными).

Обозначим множество высоковероятных последовательностей через , т.е. . Для этих последовательностей выполняется соотношение , а поскольку , то

. (2.8)

Таким образом, последовательности сообщений на выходе ДИБП могут быть разбиты на два подмножества: и , где второе – дополнение до . Последовательности из множества обладают тем свойством, что их вероятности достаточно близки друг другу (см. (2.8)) и, как следует из (2.7), суммарная вероятность всех элементов этого множества весьма близка к единице.

Определим мощность множества , для чего просуммируем обе части левого неравенства в (2.8) по элементам этого множества. В результате

,

откуда

.

Как можно видеть, доля высоковероятных последовательностей в общем объеме множества составляет

, (2.9)

где учтено, что , а L – объем алфавита X и . Отсюда следует, что выигрыш в длине кодового блока при равномерном кодировании обусловлен относительно малой долей высоковероятных последовательностей по сравнению с их общим числом . Требуемое же число кодовых символов на букву источника определится как

.

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

Теорема 2.6.2. Для произвольно малых e и d всегда можно выбрать такую длину блока букв источника, что число двоичных символов кодового слова на букву источника не превысит значения H (X)+e и при этом вероятность ошибки декодирования будет не больше d.

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

Подчеркнем, что при равновероятных и независимых символах источника все последовательностей относятся к высоковероятным и экономное кодирование с приемлемой ошибкой невозможно (см. (2.9)).

Пример 2.6.1. Обратимся к двоичному источнику с алфавитом , , . Его энтропия . Вероятность появления на его выходе конкретной последовательности длины , зависит только от числа t единиц, содержащихся в ней: . Тогда

, а .

Следовательно, условие (2.7), определяющее принадлежность последовательностей к множеству , можно записать в виде

.

После приведения подобных членов это условие преобразуется к виду

, где .