11. Верхняя граница, полученная методом исчерпывания

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

Сначала будет показано, что при можно найти по меньшей мере

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

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

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

Рис. 6. Геометрия сферы радиуса

Заметим, что каждая выбранная следующая точка удалена от предыдущей не менее чем на расстояние D. Следовательно, все расстояния между точками не меньше D. Далее замечаем, что число повторений этой операции может по крайней мере равняться отношению поверхности сферы радиуса У пР к поверхности сферы радиуса Н. Отношение площадей этих поверхностей, очевидно, равно

Из простых геометрических построений (рис. 6) видно, что Н и D связаны следующим образом:

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

Подставляя Н в предыдущее отношение, видим, что можно разместить по меньшей мере

точек с расстояниями друг от друга, не меньшими D для

Если имеется точек с минимальным расстоянием не меньше D, то вероятность ошибки при оптимальном декодировании меньше или равна

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

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

Если положить

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

при

что следует из хорошо известной формулы для верхней границы

Это — параметрические уравнения относительно D. Более удобно

положить При этом будем иметь

Асимптотическая надежность, т. е. коэффициент при в экспоненте равна При она стремится к

Асимптотическую нижнюю границу надежности находим путем исключения

При выражение, стоящее справа, стремится к

Эта нижняя граница экспоненты изображена на кривых в разд. 14. По ним можно видеть, что при малых скоростях передачи эта граница дает больше информации, чем граница, полученная методом случайного кодирования. Можно, однако, улучшить метод случайного кодирования так называемым процессом «вычеркивания». Он приводит к границе, совпадающей с только что найденной и даже несколько более сильной внутри части области. Не входя детально в описание этого метода, упомянем лишь, что он состоит в вычеркивании из случайного кода точек ансамбля, которые имеют слишком близкое соседство друг к другу, и в рассмотрении кодов, которые возникают после такого вычеркивания.