9.10. АСИМПТОТИЧЕСКАЯ НОРМАЛЬНОСТЬ НЕКОТОРЫХ ВЕСОВЫХ СПЕКТРОВ

Пусть двоичный -код со спектром весов где число кодовых слов веса Тогда

где представляет собой вектор, у которого

Пример. Пусть -код БЧХ, исправляющий две ошибки. Тогда согласно рис. 15.3 код имеет следующий весовой спектр:

Согласно теореме 1 гл. 5 весовая функция кода равна

Следовательно, весовой спектр кода равен:

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

Заметим, что в случае, когда является -кодом в (9.33) имеет место строгое равенство. Нетрудно также показать, что равенство (9.33) выполняется при случайном выборе кода (см. упражнение (8)).

В теореме 23 этого параграфа мы дадим некоторое обоснование формулы (9.33) для случая, когда минимальное расстояние дуального кода велико. Мы предполагаем некоторое знакомство с теорией вероятностей.

До сих пор мы ничего не говорили о том, как понимается знаков формуле (9.33). Для того чтобы дать точную формулировку, определим функцию распределения ассоциированную с кодом.

Пусть -некоторый вектор над полем действительных чисел, для которого выполняются условия Среднее и дисперсию вектора а определим равенствами

Рис. 9.7. Числа для -кода

Центральный момент порядка равен

Таким образом, Ниже естественно, особую роль будет играть биномиальный вектор где Для него

Лемма 22. Пусть код и вектор а задается формулой (9.32). Если минимальное расстояние кода равно для

Доказательство. Утверждение вытекает из упражнения гл. 5.

Определение. Для произвольного действительного числа функция распределения вектора а определяется равенством

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

В данном параграфе рассматривается следующий частный случай этой общей теоремы.

Теорема 23. (Сидельников.) Пусть — двоичный код, и пусть минимальное расстояние дуального кода не меньше чем 3. Тогда

Доказательство. (Некоторые детали опускаются.) Пусть а — некоторое слово кода 92. Согласно Определим характеристическую функцию вектора а

Уравнение (9.35) представляет собой разложение функции в ряд Тейлора, и нам нужна оценка остатка этого ряда. Прежде всего (индукцией по ) показывается, что для

Отсюда, используя равенство (9.36), получаем, что для всех четных и произвольного имеет место неравенство

и, следовательно, полагая имеем

Положим теперь равным наибольшему четному числу, не превосходящему Тогда согласно лемме 22 неравенство (9.37) можно заменить неравенством

В качестве отправной точки для доказательства используем следующую классическую формулу теории вероятностей (см., например, [427], уравнения (3.13) на с. 616 и (5.3) на с. 621)

справедливую для всех Используя неравенство (9.38), интеграл в (9.39) можно оценить сверху так:

Первый из этих двух интегралов равен:

Пусть Оценим величину с помощью разложения в ряд по степеням функции При с учетом неравенств

получаем, что

Таким образом, подынтегральное выражение не превосходит

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

Таким образом, первый интеграл в (9.40) не превосходит

Второй интеграл в (9.40) равен

Согласно упражнению (9) эта величина не превосходит

Собирая вместе все полученные результаты, для получаем

Выбор приводит к желаемому результату.

В отличие от границы Карлица-Ушиямы и теоремы 21 эта теорема применима к кодам БЧХ с небольшим конструктивным расстоянием. Другие применения этого результата даны в замечаниях к главе, а также в главе, посвященной квадратично-вычетным кодам.

Следствие 24. (Вариант классической центральной предельной теоремы.) Функция распределения биномиального вектора b удовлетворяет условию

Доказательство. Пусть -код Тогда

Константа 20, участвующая в формулировке теоремы 23, конечно, не очень хороша, так как теорема приобретает смысл лишь при превосходящих 400. С другой стороны, рис. 9.7 может служить подтверждением того, что является хорошей аппроксимацией функции даже для коротких кодов.

Задача (нерешенная). (9.16). Усилить теорему 23.

Упражнения. (8). (см. также упражнение (31) гл. 17). Рассмотрим двоичный -код с порождающей матрицей где А — матрица размерности состоящая из нулей и единиц (см. уравнение (1.8)). Предположим, что каждый элемент матрицы А выбирается равным 0 или 1 случайным образом с вероятностью а затем случайным образом выбирается слово и из кода Доказать, что

Таким образом, можно утверждать, что для случайно выбранного -кода выполняется равенство (9.33).

(9). Доказать, что величины определяемые условиями (9.34), для всех четных удовлетворяют неравенствам

[Указание. Ввести в рассмотрение независимые случайные величины каждая из которых принимает значение +1 или —1 с вероятностью Величина аппроксимируется нормально распределенной случайной величиной со средним, равным 0, и дисперсией, равной 1. Если четно, то

Тогда