канонических форм:

(fe-l)/2

х\-\- S 21-121, t=l

ft/2

к нечетно,

X{xl-\-xi) 2 X2i-iX2i, к четно, 1=1

где k а Я, - нуль или элемент поля GF (2"), для которого

Тг (X) = 1.

Доказательство. Пусть k - наименьшее число переменных, через которые можно записать F при произвольном обратимом линейном преобразовании неременных.

Докажем прежде всего, что если F зависит от х н k 3, то, не ограничивая общности рассуждений, можно положить 5, = 0. Если Bj, о ш 2 = 0. то х можно заменить на х. Если Bj, j + -f В I =! О для всех пар (i, /), i Ф j, то F - полный квадрат и /с = 1 <; 3. Следовательно, можно предположить, что В2,2 ф О и -2. 3 + Вз, гфО. Заменяя В;, -f- Bj, t на Bj, у, получим )

i¥=2, з=#2

Полагая Хз = 2г.22:г и я: = а:г для 1=53, преобразуем F к виду

"BijXiXj,

где Bi, 2 -О- Замена х, = хУВ хУг.г и = для i2 исключает В. Таким образом, если зависит от х ж к 3, то, не ограничивая общности рассуждений, можно предположить, что Bi,i = 0.

Если Bi, у - О для всех /, то F не зависит от Xi, и можно предположить, что Bi, 2 О, Полагая - 2 i. JJ ж xi - xt для

i Ф 2, приведем к виду хх,, -f jij- Замена х = 2-2 з)

Преобразует F к виду хХг + F, где F - квадратичная форма от

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

1) На самом деле, конечно,

F= Вг, + Г2 2 г. 2г + SS л

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

приведена к виду F - х-х + F, где F не зависит от х и х. Если F зависит от большего числа переменных, то редукцию можно продолжить: F = Х3Х4 -{-Еж так далее до тех пор, пока в конце концов не получим квадратичную форму, зависящую не более чем от двух переменных. Единственная квадратичная форма, зависящая от одной переменной - это х; единственная квадратичная форма, зависящая от двух переменных,- это Ах -\- Вху -f- Су. Если АС = О, то очевидная подстановка приводит эту форму к виду ху; если АС Ф О, то, заменив х на xYa ж у па у YC, получим х -Ь Вху -f у. Если В = О, то это полный квадрат. Если В О, то подстановка у = By дает F = х ху у/В. Подстановка х = х иу приводит F к х -\- ху -{- (и + и -i- 1/В2) г/2. Если Тг (l/B) = О, то w можно выбрать так, что и -\- и1/В = 0; если Тг (1/В) = 1, то и можно выбрать так, что -f ы -f l/B = Х. Полагая х = xlY%, у = у/У> приведем F к виду ху -\- {х + У)-

16.351. Следствие. Любой многочлен степени 2 от конечного числа переменных над конечным полем характеристики 2 может быть приведен с помощью обратимого аффинного преобразования его переменных к одной из канонических форм

(ft-l)/2

Xh+ 2 X2i-iX2l-}-BkXk + B, i=l (fe-l)/2

F = < xl-\- 2 X2i-iX2i-{-Bk.,iXk.,i + B, BxBfe+i = 0,

ft/2

(x-fxI i) + 2 X2i-iX2i-i-Bk.,iXk+i-B, BxBfe+i = 0.

Доказательство. Тождество

Я:2г-12г ~Ь 2!-l*2J-l ~Ь 2121 - = (2i-l + 21) {X2i + Ец-т) + Bl-lBl

позволяет исключить все лишние линейные члены с помощью соответствующих линейных сдвигов, щ

Доказательство теоремы 16.34. Так как аффинные преобразования сохраняют многочлены степени :1, то они переводят кодовые слова РМ-кода первого порядка в другие кодовые слова РМ-кода первого порядка. Например, типичное аффинное преобразование может перевести С<) в С) -f С() -f- 1. Согласно следствию 16.351 и тому факту, что С ® С* = С, выражение (16.341) можно

привести к одному из видов

(16.352)

2 с<2->с(>+ { 1

где /<т/2. Вес кодового слова 2 (;;(2Л-1)(2й) р числу коор-

динат, J = 0, 1, 2, ...,n-i, оо, таких, что 2 = 1, т. е.

равен числу способов выбора двоичных координат U, U,..., Um, удовлетворяющих уравнению

(16.353) j]U, ,U,, = i

ft=i

при i=l. Пусть TVi -число решений уравнения (16.353) для г = 0, 1. Тогда

iVo=2n-2i 2 (;)3S

i четн.

iV, = 2-2i 2 (i)3\

i нечетн.

iVo iVi = 2"-2i (3 +1) = 2", iVo - iVj = 2"-2i (3 -1)= г""-, Ao = 2"-i + 2«-i-i, iVi = 2"-i -2"-J-i.

( 2 C-CO = Л, = 2--1-2-i-i,

( 2 C<2ft-i)c(2fe) i) 2"-i + 2--i-i,

ft- 1

так как точно половина из 2"" двоичных последовательностей дли- ны т удовлетворяет уравнению

2 и2h-lUzk = U2j+i. ft=l

Полагая в формулах для весов /(т-j)/2, получим теорему 16.34. н

(16.354)

Далее

*16.4. Нумераторы весов Казами для некоторых подкодов РМ-кода второго порядка

16.41. Приведение тождеств Плесе. В случае подкодов РМ-кода второго порядка теорема Казами 16.34 утверждает, что все пепулевые коэффициенты совпадают с Aq, Аг, Anj2, Л/(г) и AN-f(i), ще i = m (mod 2) и / (О = 2"-i + 2("+*)/2-Ч При w = 2"" тождества Плесе принимают вид

(16.411) {А, + А)2- 2 (-2

i = m (mod 2)

0n+i)/2.r

+ 2 (2"+Г = 2" 2 BjFi (N),

i=m (mod 2) 3=0

где BO избежание путаницы с блоковой длиной и = 2" - 1 1-укоро-ченных кодов блоковая длина обозначена через N = 2"\ Если предположить, что А = 1, то = Aff-j для всех /. Так как единичный вектор задает общую проверку на четность для дуального кода, то Bj = О для всех нечетных /. Заменяя г на 2г и / на 2/, перепишем

(16.411) в виде

(16.412) 2(2"-+ 2 2"-+".4/(i))=2" 2 •>0.

i=m (mod 2) з=0

Положим

(16.413) = -

Используя (16.413) при N = 2", запишем равенство (16.412) в виде

(16.414) 2 "Af = N"- 2 BjFiV {N) -iT.

i=m (mod 2) 3=0

Умножая (16.414) на z"" и суммируя по г от 1 до со, получаем, что

(16.415)

lEEEm (mod 2)

= N"B,j

Используя равенство (16.242) и табл. 16.2, можно показать, что (16.416) /(0) дг; 1!ш!1 [1Л<2)+Л(1)]г* ,

[15JV(3,-bl5iV(2,-b(i)]z6

ЛГ2 + ...=

Для ТОГО чтобы исключить Л/(ii), /(12), ...,-4/(1) из уравнения

(16.415), можно умножить (16.415) на [J (1 -2Vz2) и приравнять

коэффициенты при z. Например, если умножить на 1 -2z2 равенство (16.415), то в силу формулы (16.244)

5(z)(l-222) = iV"[z2-f (1 .А),4...2! B2(il-i-...) +

+ А\Б,[-{-...)]-Nz~{m-2N)z-... .

Приравняв коэффициенты при z*, получим

S 2* (2*-2) Af = N{N-2) (iV-2 1) +4! NB,,

ism (mod 2)

если Z?2 = 0.

Это третье уравнение, приведенное в таблице 16.3. Аналогичные выкладки позволяют получить все уравнения табл. 16.3. Эти уравнения представляют собой тождества Плесе (16.414), приведенные к треугольному виду.

16.42. Нечетное т, некоторые БЧХ - коды с малой скоростью. Начнем с РМ-кода первого порядка, отмеченного в первой строке таблицы 16.4. Распределение весов для этого кода было известно еще Риду и Маллеру. 2-укороченный РМ-код первого порядка - циклический. Корнями его проверочного многочлена являются а", а~, а~*, . . ., или, что то же самое, а"-1, а"-2 а"-4 . . ., где /г = 2" - 1. Как показано в первом столбце табл. 16.4, двоичные записи логарифмов этих корней по основанию а образуют циклические сдвиги последовательности 0111... . Этот циклический код представляет собой суженный БЧХ-код со скоростью {т 1)/п, который в свою очередь является 1-укороченным РМ-кодом первого порядка. Хорошо известно, что распределение весов РМ-кода первого порядка имеет вид Aq = = 1, An/2 = = 2iV - 2.

Рассмотрим теперь 1-удлиненный БЧХ-код со скоростью {2т -f 1)/Л, приведенный во второй строке табл. 16.4. Распределение весов для этого кода впервые было найдено Казами. Проверочный многочлен суженного БЧХ-кода имеет 2т корней. Двоичная запись логарифмов по основанию а получается циклическими сдвигами последовательностей 011111111 и 011101111, содержащихся в первом

столбце таблицы. В соответствии с БЧХ-границей минимальное расстояние 1-удлиненного БЧХ-кода со скоростью (2т -f l)/N больше или равно 2"" - 2*"~*, так что Af(i) = О для всех i >> 1. Так как этот код содержит РМ-код первого порядка, то дуальный к нему код образует подкод кода, дуального к РМ-коду первого порядка. Так как на предыдущей линип таблицы - О, то, таким образом, дуальный к РМ-коду первого порядка (последний, па самом деле, есть 1-удлиненпый код Хэмминга) не имеет кодовых слов веса 2, так что код, дуальный к 1-удлиненпому БЧХ-коду со скоростью {2т -f l)/N, тоже не содержит кодовых слов веса 2. Другими словами, В2 = 0. Это позволяет определить Af непосредственно из уравнения (Т2) и Ля/2 - из уравнения (Т1) табл. 16.3. Согласно уравнению (ТЗ), О = О -(- i\B, и мы заключаем, что В = 0.

Прежде чем переходить к БЧХ-коду с большей скоростью, заметим, что Д.ПЯ достаточно больших т имеется много 1-удлиненных БЧХ-кодов с малыми скоростями, представляющих собой подкоды РМ-кода второго порядка. Ясно, что каждая двоичная последовательность длины т, содержащая не менее трех нулей, имеет циклический сдвиг, который начинается с О и содержит следующий О непозже, чем в -j-l-й позиции. Например, если т == 15,

то крайний случай дает последовательность 01111011110111. Пусть у (т -f 1)/2 - {[т/3] -f- 1) -- 2. Образуем v двоичных последовательностей длины т: 011111111111111, 011111101111111, 011111011111111, . . ., 011110111111111. Тогда они и все их циклические сдвиги должны превосходить по меньшей мере один циклический сдвиг любой двоичной последовательности длины т, содержащей не менее трех нулей. Следовательно, если v{m -\- 1)/2 - [т/3] -f 1 ш т - нечетно, то 1-удлиненный двоичный БЧХ-код со скоростью {mv -j- 1)/2" - подкод РМ-кода второго порядка.

Рассмотрим теперь приведенный в третьей строке табл. 16.4 1-удлиненный БЧХ-код со скоростью {Зт -\- i)/N, . Согласно

БЧХ-границе, минимальное расстояние этого кода больше или равно 2"-* - 2<"+ так что Ащ = О для всех I > 3. Так как данный код содержит 1-удлиненный БЧХ-код со скоростью {2т -f 1)/Л, то дуальный к нему код является подкодом дуального к 1-удлиненпому БЧХ-коду со скоростью {2т -\- \)/N. Так как на предыдущей линии таблицы В = 0. то, следовательно, опять получаем 2?4 = О Это позволяет определить Af, из уравнения (ТЗ); Ai) из уравнения (Т2), .4jv/2 из уравнения (Т1). Согласно (Т4), О = О -Ь бШе, откуда заключаем, что В, = 0.

Рассмотрим далее 1-удлиненный БЧХ-код со скоростью (4т -f 1)/Л, т И. Согласно БЧХ-границе, Afi = О для всех г > 5. В силу предыдущих рассмотрений В = 0. Следовательно, можно определить Af из уравнения (Т4), А/ф - из (ТЗ), Aj, -