Приложение Б. ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ 8 (ГРАНИЦА ДЛЯ СЛУЧАЙНОГО КОДА)

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

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

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

такого для которого отличаются в наименьшем числе позиций.

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

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

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

смежном классе а эта вероятность ограничена сверху суммой вероятностей того, что каждое , т. е.

Правая часть ограничена сверху суммой по всем возможным

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

ограничена сверху следующим образом:

Неравенство является обычной формой границы для случайного кода.

Некоторые авторы [23, 24, 16] получили асимптотические оценки величины Лучшая такая оценка дана Возенкрафтом [3]; приведем его результат без доказательства.

Оценки даны в терминах величин где

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

где

и

Первый вывод асимптотической оценки неравенства дал Элайес [24], который доказал, что показатель степени в точно такой же, что и показатель степени для величины полученной из соображений «плотной упаковки». Этот показатель можно получить и геометрически — построением,

приведенным на рис. Б.1. На этом рисунке представляет собой точку, в которой угол наклона касательной к кривой в два раза меньше, чем угол наклона касательной в точке

Рис. Б.1. Геометрическая интерпретация показателя степени в выражении для

Эту интересную геометрическую интерпретацию показателя степени в выражении для Элайес [24] приписывает Шеннону.