3.13.4. Совместное рассмотрение экспонент случайного кодирования и сферической упаковки.

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

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

Будем отправляться от определений (3.13.38) и (3.13.39). Напомним, что в этих определениях матрица переходных вероятностей канала,

— некоторая вспомогательная согласованная с каналом матрица переходных вероятностей и

Введем в рассмотрение еще одну функцию

Заметим, что определения функций (см. (см. (3.13.43)) различаются только областью изменения параметра в первом случае находится в интервале [0, 1], во втором Очевидно, что при при Как было показано ранее, при функция представляет собой прямую с наклоном —1, касательную к в точке Значение максимизирующее правую часть соотношения (3.13.43), как и раньше, определяется как корень уравнения (3.12.30). Поэтому график функции может быть построен таким же образом, как и график функции (см. § 3.12), На рис. 3.12.2 показаны обе функции и

Замечание. Пусть значение скорости при данном которое удовлетворяет уравнению (3.12.30). Пусть Если то при Отметим, что это возможно только для таких каналов, для которых при некоторых Детальное обсуждение свойств таких каналов выходит из рамок данной книги.

Наша ближайшая задача состоит в установлении связи между функциями и а также между функциями и

Лемма 3.13.4. Пусть произвольное распределение вероятностей на и распределения вероятностей на которые порождаются распределением т. е. Пусть — соответствующий вероятностный вектор. Пусть, кроме того, -распределения вероятностей,

задающие канал, произвольное распределение вероятностей на Тогда

Если то минимум в (3.13.44) достигается при где распределение определяется соотношениями (3.12.22) при таком значении что

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

Тогда Если же то в соответствии с замечанием, предшествующим формулировке теоремы, левая часть соотношения (3.13.44) обращается в бесконечность. Правая часть также обращается в бесконечность при условии, что обе части (3.13.44) совпадают при всех поскольку правая часть является монотонно невозрастающей функцией а левая — непрерывная функция

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

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

получим

где

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

Заметим, что оба неравенства в последнем соотношении переходят в точные равенства, если Действительно, при этом кроме того, из (3.12.30) и (3.12.24) следует, что Такой выбор распределения удовлетворяет условию, при котором разыскивается минимум в (3.13.44). Следовательно, из (3.13.46) вытекает утверждение леммы. Лемма доказана.

Лемма 3.13.5. Функция определяемая соотношением (3.13.38), представима в виде

где

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

Доказательство. Положим

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

Обозначим через распределение вероятностей, на котором достигается максимум в выражении (3.13.48). Из теоремы Куна-Таккера и из (3.13.49) следует, что оптимизирующее распределение должно удовлетворять следующей системе соотношений:

где с — неопределенный множитель Лагранжа и знак неравенства может иметь место только для тех для которых Зпметим, однако, что если для некоторого но . В этом случае из (3.13.48) следует, что Поэтому соотношения (3.13.50) выполняются со знаком равенства для всех Домножая левую и правую части неравенства (3.13.50) на и суммируя по X, получим, что Отсюда следует, что необходимые условия максимума в (3.13.48) задаются следующей системой уравнений:

Легко видеть, что, как и в теореме 3.13.1, эти условия являются и достаточными.

Обозначим теперь через распределение вероятностей на определяемое соотношением (3.12.22) при условии, что заменено на Тогда из (3.13.51) получим, что

Далее из (3.12.24), (3.12.25) и следует, что

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

Введем следующие обозначения. Пусть матрица переходных вероятностей, на которой достигается минимум в (3.13.38). Пусть распределения вероятностей на такие, что где переходные вероятности канала. Пусть — распределение вероятностей на такое, что матрица переходных вероятностей, элементы которой определяются из условия и Пусть, наконец, еще одна матрица переходных вероятностей, элементы которой определяются из условия Тогда из (3.13.45) имеем

Учитывая, что распределение доставляет максимум правой части (3.13.48), из (3.13.54) и (3.13.48) получим, что

Пусть параметр удовлетворяет уравнению (3.13.53). Тогда из (3.13.55) следует, что

Оба неравенства в (3.13.56) превращаются в равенства при или, как это следует из Из (3.13.52) и (3.13.53) вытекает, что матрица доставляет минимум в в (3.13.38). Поэтому из (3.13.56) следует утверждение леммы. Лемма доказана.

Положим

Имеет место следующее утверждение.

Теорема 3.13.3. Для произвольного дискретного канала без памяти

для любого распределения вероятностей на кроме того,

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

Кроме того,

где последнее равенство обусловлено выбором матрицы Из (3.13.60), (3.13.61) и леммы 3.13.4 следует (3.13.58). Докажем теперь справедливость равенства (3.13.59). Из леммы 3.13.5 и (3.13.39) имеем

Учитывая, что при фиксированных в выражении под знаком в (3.13.62) от распределения зависит только а также учитывая лемму 3.12.1, из (3.13.62) получим

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

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

Задачи, упражнения и дополнения

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

КРАТКИЙ ИСТОРИЧЕСКИЙ КОММЕНТАРИЙ И ЛИТЕРАТУРА

Задача кодирования в канале с шумом впервые была рассмотрена К. Шенноном [13], Первое доказательство прямой теоремы кодирования для дискретных каналов без памяти было получено А. Файистейном [9]. Позднее эта же теорема была доказана К. Шенноном методом случайного кодирования [14].

Большое число работ посвящено теоремам кодирования для различных моделей дискретных каналов. К их числу в первую очередь относятся работы К. Шеннона [14], А. Я. Хинчина [12], Р. Л. Добрушина [7], А. Файнстейна [10] и Дж. Вольфовица [4]. Изложенный в § 3.5 итеративный алгоритм вычисления пропускной способности был построен независимо С. Аримото [1] и Р. Блэйхутом 13]. Экспоненциально точные в области высоких скоростей границы для вероятности ошибки декодирования в ДСК были впервые получены П. Элайесом [16]. Р. Л. Добрушин [8] получил аналогичные границы для произвольных симметричных каналов без памяти. Р. Фано [11] построил экспоненциально точные в области высоких скоростей границы для вероятности ошибки декодирования в произвольном дискретном канале без памяти. Позднее Р. Галлагер [5] предложил более простой, чем способ Фано, метод построения верхних границ. Параграф 3.12 основывается на методе Галлагера. В той же работе Галлагер улучшил верхнюю границу в области малых скоростей. К. Шеннон, Р, Галлагер и Е. Берлекэмп [15] построили нижнюю границу, более точную при малых скоростях, чем граница Фано. Метод построения границы сферической упаковки, использованный в п. 3.13.2, принадлежит Е. А. Арутюняну [2], Наиболее подробно вопросы кодирования в дискретных каналах рассмотрены в книгах Вольфовица [4] и Галлагера [6].

(см. скан)

(см. скан)