§ 3.13. Нижняя граница вероятности ошибки декодирования для дискретных каналов без памяти (граница сферической упаковки)

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

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

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

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

3.13.1. Нижняя граница вероятности ошибки для ДСК.

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

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

Введем вначале несколько вспомогательных понятий. Пусть — двоичный алфавит и две двоичные последовательности длины Расстоянием Хемминга между последовательностями называется число позиций, в которых эти последовательности различаются. Например, пусть тогда Пусть фиксирована последовательность (точка) Сферой Хемминга с центром в точке и радиусом называется множество всех таких двоичных последовательностей которых Например, сфера Хемминга с центром в точке и радиусом 2 содержит следующие 7 последовательностей из ; точка (100) находится на расстоянии 3 от центра и в данную сферу не входит.

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

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

где число таких последовательностей из решающей области которые отличаются от позициях. Так как

Следовательно,

где наибольшее целое, удовлетворяющее неравенству

Неравенства (3.13.3) и (3.13.4) отражают тот факт, что при фиксированном объеме решающей области наименьшую вероятность ошибки дает область, которая является сферой Хемминга с центром в кодовом слове

Так как общее число выходных последовательностей канала равно то найдется такое, что

Обозначим через наибольшее целое число, удовлетворяющее неравенству (3.13.4) при Тогда из (3.13.4) и (3.13.5) имеем

Обозначим через и воспользуемся формулой Стирлинга для факториалов, чтобы оценить величину Учитывая задачу 1.6.3, можно записать

или

где

Оценим теперь величину Из (3.13.3), снова учитывая задачу 1.6.3, получим

где

и

Так как непрерывная функция то из (3.13.9) и (3.13.10) следует, что

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

Обозначим через функцию, определяемую следующим образом:

где корень уравнения

Легко видеть, что непрерывная функция аргумента Поэтому из (3.13.7), (3.13.12), (3.13.13) и (3.13.14) следует, что максимальная вероятность ошибки декодирования любого кода в ДСК удовлетворяет неравенству

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

С помощью леммы 3.2.1 можно сделать аналогичное утверждение для средней вероятности ошибки декодирования. Из этой леммы следует, что если не существует кода с максимальной вероятностью ошибки то не существует и кода со средней вероятностью ошибки, меньшей чем где Учитывая это замечание, из (3.13.15) получим, что для любого кода средняя вероятность ошибки декодирования в ДСК удовлетворяет неравенству

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

Сравнивая (3.13.13) и (3.13.14) с (3.12.44) и (3.12.45), можно убедиться в том, что в случае ДСК функции и совпадают при всех следовательно, верхняя и нижняя оценки для вероятности ошибки декодирования в ДСК экспоненциально точны.

Заметим, что приведенный выше вывод нижней границы вероятности ошибки декодирования в ДСК основан на следующих двух утверждениях: 1. При фиксированном объеме решающей области наименьшую вероятность ошибки дает область, представляющая собой сферу Хемминга с центром в соответствующем кодовом слове. 2. Наибольшее число непересекающихся сфер радиуса в множестве всех двоичных последовательностей длины

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

В соответствии с этими утверждениями наименьшей вероятностью ошибки в ДСК обладает код, для которого все решающие области являются сферами Хемминга радиуса где определяется из условия Такой код называется «сферически плотно упакованным» или просто тлотно упакованным». Использованный метод построения нижней границы заключается в построении оценки для гипотетического плотно упакованного кода, скорость которого равна скорости исходного кода. При данных плотно упакованного кода почти во всех случаях не существует. Однако асимптотическая точность полученных оценок свидетельствует о том, что при больших существуют почти плотно упакованные коды, для которых решающие области почти сферичны.