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

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

Требуется вычислить среднюю вероятность ошибки для нашего ансамбля кодов.

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

вероятности ошибки, соответствующей некоторой частной кодовой точке, например, кодовой точке 1. Вычислим ее следующим образом: вероятность того, что передано сообщение 1, равна Дифференциальная вероятность того, что из-за шума оно будет перемещено в область между конусами с полууглом и полууглом (эти конусы имеют вершину в начале координат и общую ось — линию, соединяющую начало координат с точкой кодового слова 1), есть . (Напомним, что по определению является вероятностью того, что из-за воздействия шума точка окажется вне конуса с углом и осью, проходящей через соответствующую точку передаваемого кодового слова и начало координат.) Рассмотрим теперь конус с полууглом окружающий точку принятого кодового слова (но не конус, описанный вокруг соответствующей точки передаваемого слова, как это было выше). Если этот конус свободен от точек, соответствующих передаваемым кодовым словам, то принятое слово декодируется правильно как сообщение 1. Если он не свободен, то другие точки окажутся ближе и принятое слово будет декодировано неправильно. (Очевидно, что вероятность того, что две или более точки находятся точно на одном и том же расстоянии от принятого кодового слова, равна нулю и может не учитываться.)

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

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

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

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

или

Для удобно выбрать то же значение, которое появлялось при подсчете нижней границы, т. е. значение, при котором другими словами, значение, при котором внутри конуса с полууглом получается одна ожидаемая точка. Второй член в выражении (19) совпадает с нижней оценкой найденной ранее. Итак, подводя итоги, имеем

где Это и есть наши основные нижняя и верхняя границы для значений

Теперь желательно вычислить и оценить значения