3.13.3. Нижняя граница для вероятности ошибки декодирования кода с фиксированной композицией.

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

и среднюю энтропию распределения относительно распределения

Пусть, кроме того, для фиксированного и для каждой

последовательности определено множество

где

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

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

Доказательство. Рассмотрим функцию

которая при каждом фиксированном отображает множество в числовую ось. Эту функцию можно рассматривать как случайную величину на ансамбле ее математическое ожидание равно

Из (3.13.21) следует, что

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

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

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

где

Применим теперь неравенство Чебышева. В результате получим, что

Аналогичным образом можно получить неравенство

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

Пусть множество всех таких которые удовлетворяют первому неравенству в (3.13.20), а множество всех таких которые удовлетворяют второму неравенству в (3.13.20). Очевидно, что Обозначая через дополнение к множеству получим с учетом

Из (3.13.26) следует, что для любого и любого найдется такое, что при выполняется (3.13.22). Лемма доказана.

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

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

где определяется соотношением (3.13.19), и любого найдется такое, что при выполняется следующее неравенство для средней вероятности ошибки декодирования 3:

Доказательство. Пусть Тогда среднюю вероятность ошибки этого кода можно оценить следующим образом:

где множество, определяемое для данного соотношением (3.13.20). Из (3.13.20) (первое неравенство) имеем для каждого

Подставляя (3.13.30) в (3.13.29), получим

Используем соотношение . Тогда получим, что

Из (3.13.20) (второе неравенство) следует, что всех

Из (3.13.27) и (3.13.33) получим теперь

где последнее равенство в (3.13.34) следует из того, что решающие множества не пересекаются, а последнее неравенство — из того, что

Из (3.13.31), (3.13.32), (3.13.34) и леммы 3.13.3 следует окончательно, что

Для любого можно так выбрать что при будет выполняться неравенство (3.13.28). Теорема доказана.

Доказанная теорема вместе с леммой 3.13.2 дает возможность построить нижнюю границу вероятности ошибки декодирования произвольного кода в дискретном канале без памяти. Заметим сначала, что неравенство (3.13.28) справедливо для любой стохастической матрицы Я, для которой выполняется условие (3.13.27). Следовательно, вероятность ошибки декодирования любого кода с фиксированной композицией удовлетворяет неравенству

где максимум разыскивается по всем стохастическим матрицам согласованным с каналом и удовлетворяющим условию

где причем положительные величины, которые могут быть выбраны сколь угодно малыми

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

где минимум разыскивается по всем композициям а максимум — по всем стохастическим матрицам согласованным с каналом, для которых удовлетворяется условие (3.13.36) для данной композиции

Заметим, что множество всех композиций зависит от так как компонентами вектора являются дроби со знаменателем

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

Положим

и

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

Теорема 3.13.2. Для любого найдется такое, что при средняя вероятность ошибки декодирования X любого кода удовлетворяет неравенству

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

где — средняя вероятность ошибки для кода , имеющего композицию и скорость Из неравенств (3.13.35), (3.13.36), (3.13.41) с учетом обозначения (3.13.38) следует, что для любых положительных при достаточно больших справедливо следующее неравенство:

где и последнее равенство получено в силу непрерывности и невозрастания как функции от Величина положительна, но может быть сделана произвольно малой за счет выбора достаточно большого Заметим далее, что неравенство (3.13.42) справедливо лишь при определенной композиции, зависящей от кода Поэтому для получения нижней границы вероятности ошибки, справедливой для любого кода, следует взять минимум правой части (3.13.42) по всем композициям Тогда, учитывая обозначение (3.13.39), получим, что для любого найдется такое, что при средняя вероятность ошибки декодирования любого кода удовлетворяет неравенству

что совпадает с (3.13.40). Теорема доказана.

Из сравнения (3.13.13) и (3.13.14) с (3.13.39) можно заключить, что показатель экспоненты в нижней границе для ДСК, полученный в п. 3.13.1, также может быть представлен в форме (3.13.39). При этом для случая ДСК максимум по достигается при выборе равномерного распределения вероятностей на , а минимум по достигается при выборе следующих переходных вероятностей: если если Функцию (см. (3.13.39)), частным случаем которой является показатель экспо ненты сферической упаковки для ДСК, также принято называть экспонентой сферической упаковки сокращение от английского «sphere packing» - «сферическая упаковка»). В следующем пункте мы покажем, что, как и в случае ДСК, экспоненты случайного кодирования и сферической упаковки совпадают при всех скоростях для произвольного дискретного канала без памяти.