§ 1.12. Неравномерное кодирование дискретных стационарных источников

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

Пусть произвольный дискретный ансамбль сообщений и его энтропия.

Обозначим: средняя длина ичного кода, слова которого сопоставляются сообщениям ансамбля

Теорема 1.12.1. Для любого кода со свойством однозначного декодирования

Доказательство. Из определения средней длины кодовых слов имеем

Рассмотрим разность

Воспользуемся неравенством (1.3.7). В результате получим, что

где последнее неравенство является следствием того, что код обладает свойством однозначного декодирования (см. теорему Теорема доказана.

Замечание. Первое неравенство в (1.12.4), так же как и второе, обращается в точное равенство, если

Таким образом, если вероятности сообщений являются целыми отрицательными степенями числа О (1.12.5), то существует -ичное дерево с концевыми узлами порядков (теорема 1.11.1) и соответствующий D-ичный код будет иметь среднюю длину

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

Этим рассуждением мы показали, что в случае, когда вероятности сообщений есть целые отрицательные степени числа средняя длина оптимального D-ичиого кода совпадает со своей нижней границей. Такой код сопоставляет сообщению слово длины

Теорема 1.12.2. Существует D-ичный код со свойством однозначного декодирования, для которого

Доказательство. Пусть наименьшее целое число, удовлетворяющее условию где собственная информация сообщения

Очевидно,

Поскольку

то по теореме 1.11.1 существует дерево с концевыми вершинами порядков Соответствующий код будет иметь среднюю длину

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

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

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

Кроме того, существует код, для которого

Рассмотрим стационарный источник выбирающий сообщения из множества X и имеющий энтропию на сообщение Пусть этот источник кодируется с помощью D-ичного неравномерного кода, т. е. каждой последовательности сообщений ставится в соответствие кодовое слово длины Средняя длина кода а среднее количество кодовых символов, приходящееся на одно сообщение источника,

При этом средняя скорость кодирования

Теорема 1.12.3 (обратная теорема кодирования). Для любого кода, кодирующего источник однозначно, средняя скорость кодирования

Доказательство. Из определения средней скорости (1.12.14), из неравенства (1.12.11), справедливого для всех однозначно декодирующих кодов, и из теорем 1.5.1 и 1.5.2 следует, что для всех выполняются неравенства

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

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

Доказательство. Согласно теореме 1.5.2 для любого положительного найдется такое что для всех

Отсюда и из утверждения, связанного с неравенством (1.12.12), вытекает, что для произвольного целого существует

однозначно декодируемый D-ичный код со средним колинеством символов на сообщение

и, следовательно, со скоростью кодирования

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

Из теорем 1.12.3 и 1.12.4 (обратной и прямой теорем кодирования дискретного стационарного источника при неравномерном кодировании) следует, что средняя скорость создания информации таким источником равна энтропии на сообщение т. е. равна той же величине, что и в задаче равномерного кодирования. Это означает, что минимальное количество двоичных символов, затрачиваемое в среднем на одно сообщение Источника, может быть сделано сколь угодно близким к как при равномерном, так и при неравномерном кодировании.