такого
для которого
отличаются в наименьшем числе позиций.
Пусть декодирование ведется по правилу максимального правдоподобия; вычислим среднюю вероятность
ошибки при выяснении, к какому смежному классу принадлежит переданная информационная последовательность. Так как множество расстояний от любого кодового слова до кодовых слов во всех других смежных классах в точности совпадает с множеством весов кодовых слов в собственных смежных классах, можно без ограничения общности предположить, что передана сплошь нулевая последовательность
.
Пусть
любая информационная последовательность в собственном смежном классе, и пусть в канале возникла комбинация ошибок веса
Положим далее, что
число информационных позиций в комбинации ошибок, отличных от
общее число позиций, в которых
отличается от комбинации ошибок. Так как была передана сплошь нулевая последовательность, то принятая последовательность отличается от переданной в
позициях. По всему ансамблю кодов вероятность того, что
ближе к принятой последовательности, чем
вычисляется по формуле
поскольку суммирование по
дает общее число проверочных последовательностей, которые, будучи присоединенными к
образуют кодовые слова, отличающиеся от комбинации ошибок не более чем в
разрядах, и каждая из этих проверочных последовательностей имеет по предположению вероятность
Если вес комбинации ошибок есть
то вероятность ошибки
равна вероятности того, что для некоторого кодового слова в собственном
смежном классе
а эта вероятность ограничена сверху суммой вероятностей того, что каждое
, т. е.
Правая часть ограничена сверху суммой по всем возможным
Так как
вероятность, она никогда не превосходит единицы. Таким образом, средняя вероятность ошибки
выраженная формулой
ограничена сверху следующим образом:
Неравенство
является обычной формой границы для случайного кода.
Некоторые авторы [23, 24, 16] получили асимптотические оценки величины
Лучшая такая оценка дана Возенкрафтом [3]; приведем его результат без доказательства.
Оценки даны в терминах величин
где
В этих обозначениях асимптотической формой неравенства
будет
где
и
Первый вывод асимптотической оценки неравенства
дал Элайес [24], который доказал, что показатель степени в
точно такой же, что и показатель степени для величины
полученной из соображений «плотной упаковки». Этот показатель можно получить и геометрически — построением,
приведенным на рис. Б.1. На этом рисунке
представляет собой точку, в которой угол наклона касательной к кривой
в два раза меньше, чем угол наклона касательной в точке
Рис. Б.1. Геометрическая интерпретация показателя степени в выражении для
Эту интересную геометрическую интерпретацию показателя степени в выражении для
Элайес [24] приписывает Шеннону.