15.2. ВЕСОВОЙ СПЕКТР КОДА РИДА—МАЛЛЕРА ВТОРОГО ПОРЯДКА

Слова кода Рида-Маллера второго порядка длины задаются булевыми функциями от степень которых не превосходит 2 (см. § 13.3). Таким образом, типичное кодовое слово задается булевой функцией

Это можно записать в виде

где

верхняя треугольная двоичная матрица; двоичный вектор и равно 0 или 1.

называется квадратичной формой, а линейной формой. (Формой называется однородный многочлен.)

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

С матрицей В связана другая форма определяемая равенством

или иначе

(Последнее равенство следует из формулы (15.1). Форма называется билинейной и согласно (15.3) удовлетворяет условиям

Из уравнения (15.4) следует, что форма является также альтернированной, т. е. удовлетворяет условиям

и

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

является симплектической, и соответствующая ей симплектическая форма равна

В качестве конкретного примера рассмотрим РМ-коды первого и второго порядков длины представляет собой [16, 5, 8] расширенный симплексный код и порождается первыми пятью строками на рис. представляет собой [16, 11, 4] расширенный код Хэмминга и порождается первыми одиннадцатью строками на этом рисунке. Код состоит из смежных классов по коду Одним из смежных классов является сам код а квадратичная и симплектическая формы, соответствующие этому смежному классу, равны нулю.

Другой смежный класс состоит из 16 векторов вида четыре из которых указаны на рис. 15.1.

Рис. 15.1. Четыре вектора из смежного класса

Булевы функции (выражение (15.1)), соответствующие этим четырем векторам, имеют вид.

Отметим, что в данном случае они являются максимально нелинейными функциями (см. § 14.5). Все они имеют одну и ту же квадратичную часть (15.2)

Таким образом,

являются соответственно верхней треугольной и симплектической матрицами, соответствующими этому смежному классу. Симплек-тическая форма, соответствующая данному смежному классу, равна (15.3)

Упражнение (1). Доказать, что если функция удовлетворяет уравнениям (15.6) и (15.7), то найдется квадратичная форма такая, что

Таким образом, мы доказали, что:

Теорема 1. Между симплектическими формами и смежными классами кода по существует взаимно-однозначное соответствие. Нулевая форма соответствует самому коду

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

Теорема 2. Пусть обозначает число симплектических -матриц ранга над полем Тогда

Доказательство. Заметим, что

Мы теперь выведем рекуррентную формулу для Пусть А — фиксированная симплектическая -матрица ранга и пусть

— матрица размерности

Лемма 3. Среди всех различных матриц В точно имеют ранг и ровно ранг

Доказательство леммы. Если вектор у независим от строк матрицы А и может быть выбран способами, то ранг матрицы равен и соответственно ранг В равен . С другой стороны, если у зависит от строк матрицы А, скажем то

матрица имеет ранг Чтобы доказать, что вектор зависит от столбцов матрицы заметим, что

Из леммы 3 следует, что число удовлетворяет следующему рекуррентному уравнению:

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

что и дает общее решение, указанное в теореме.

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

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

Примерами матрицы для являются

(2). Любая булева функция, степень которой не превосходит где верхнетреугольная матрица, — произвольны, может быть приведена к виду преобразованием переменных где матрица, определяемая теоремы при Более того, линейно независимы.

(3). Если линейно зависит от то существует аффинное преобразование, приводящее к виду

где линейно независимы и каждая из представляет собой линейную форму от

Доказательство. (1). Утверждение очевидно для Предположим, что оно выполняется для всех Тогда симплектическая матрица В может быть записана в виде

где А имеет такой же вид. Например, симплектическая матрица может быть записана в виде

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

где

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

В этом случае

Если то

где ранг матрицы В равен если если . В любом случае

(Проверить это для

(2). Преобразование переводит билинейную форму в

Соответствующая квадратичная форма равна

(3). Пусть

где линейно зависит от скажем,

Например, если так что то подстановка переводит эту форму в

Если то при подстановке переходит в

Ясно, что продолжая таким образом, придем к желаемому результату.

Замечания. (1). Так как код содержит булеву функцию 1, то смежный класс содержит одновременно

(2). Многочлен Мэттсона-Соломона, соответствующий канонической форме

согласно следствию 26 гл. 13, равен

где линейно независимые элементы поля

Упражнение. (2). Доказать, что в теоремы константа равна

Доказать, таким образом, что число линейных форм для которых равно

Задаваемое теоремой 4 каноническое представление квадратичной формы мы используем теперь для вычисления весового спектра соответствующего смежного класса (нижеследующая теорема). Этот результат будет использоваться в данной главе много раз.

Теорема 5. Если ранг матрицы В равен то спектр весов смежного класса кода по коду равен:

Вес Число векторов

Предпошлем доказательству две леммы.

Лемма 6. Число векторов на которых обращается в нуль форма

равно

Доказательство. Если то это число равно 3 (этими векторами являются и лемма справедлива. Далее продолжим индукцией по

Имеются случая, при которых случаев, при которых Общее число равно:

Таким образом, число векторов на которых форма обращается в нуль, равно

Лемма 7. Пусть где не все а, равны нулю.

Число различных векторов для которых многочлен обращается в нуль, равно

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

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

Используя теоремы Диксона, приведем к одному из видов

Согласно замечанию, сделанному после леммы 6, веса этих многочленов равны соответственно . С другой стороны, если линейная часть зависит не только от (что возможно в случаях), то согласно лемме 7 вес кодового слова равен

Замечание. Из теоремы 5 следует, что чем больше h, тем больше минимальный вес в смежном классе. Значение соответствует самому коду Наибольший возможный минимальный вес соответствует (и, следовательно, должно быть четным). Булева функция, соответствующая такому смежному классу, является квадратичной максимально нелинейной функцией (см. § 14.5, в частности упражнение (15)).

Для иллюстрации теоремы 5 вычислим весовой спектр смежного класса Матрица В задается равенством (15.9), и ее ранг равен 4. Следовательно, и спектр весов смежного класса равен (что соответствует последней строке на рис. 14.6).

Непосредственным следствием из теоремы 5 является следующая теорема.

Теорема 8. (Спектр весов кода Рида-Маллера второго порядка.) Пусть — число слов веса в коде Тогда

за исключением случаев или для некоторого Кроме того, и для

Для числа нет простой формулы, но, естественно,

Доказательство Вытекает из теорем

Пример Весовой спектр -кода Рида-Маллера равен

Замечания. (1). Полагая в формуле получаем, что число кодовых слов минимального веса равно что согласуется с теоремой гл. 13 (2). Формула (15 12) имеет громоздкий вид, который может быть упрощен, если использовать для записи гауссовские биномиальные коэффициенты.

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

(Здесь действительное число, как правило, целое). Например,

Между гауссовскими биномиальными коэффициентами и обычными биномиальными коэффициентами, как показывает следующее упражнение (ср. с упражнением (18) гл. 1), имеется много аналогий.

Упражнение (3). Свойства гауссовских биномиальных коэффициентов:

Определим равенствами

Тогда

В терминах гауссовских биномиальных коэффициентов при уравнение (15.12) переписывается в виде

Эти коэффициенты обладают еще одним полезным свойством.

Теорема 9. Число различных (хотя не обязательно неэквивалентных) -кодов над полем GF(q) равно -ичному гауссовскому биномиальному коэффициенту

Доказательство. Число способов выбора линейно независимых векторов равно Каждое такое множество задает базис -кода. Число базисов в равно Следовательно, число различных кодов равно

Это очень легко запомнить: число -кодов равно

Упражнения. (4). (Сервейт.) Пусть весовая функция кода и пусть Доказать, что

[Указание. Эти три члена соответствуют словам кода весов ]

(5). Используя развитые в этом параграфе методы, доказать следующую теорему. Пусть делит Пусть минимальный циклический код. Доказать, что состоит из нулевого вектора слов веса слов веса где [Указание. Пусть не нуль кода Если то для некоторого (см. теорему 9 гл. 8). Выбрать сначала где примитивный элемент поля Показать, что

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