= О, 1, q - 1

ности плоскости в EG (т, q) является кодовым словом ОРМ-кода, содержащимся в GF" (q).

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

Теорема 13.7.7. Евклидово-геожтрическим кодом г-го порядка и длины п = q"* над GF (р) является наибольший линейный код над GF (р), содержащий в своем нуль-пространстве векторы инцидентности всех (г -j- \)-плоскостей в EG {т, q).

Доказательство. Достаточно доказать, что ОРМ-код, который содержит код, дуальный евклидово-геометрическому коду, является наименьшим линейным кодом над GF (cj), содержащим все векторы инцидентности. Это следует из того, что компоненты вектора инцидентности могут принимать лишь значения нуль или единица, и поэтому все его компоненты всегда лежат в подполе GF (р). Следовательно, вектор инцидентности принадлежит коду, дуальному евклидово-геометрическому коду, если он принадлежит ОРМ-коду, содержащему этот дуальный код.

Вектор инцидентности принадлежит ОРМ-коду, если он принадлежит циклическому ОРМ-коду и его символ расширения правилен. Но вектор инцидентности (г -- 1)-плоскости содержит 9+ ненулевых компонент, которые прибавляются к нулю по модулю р; поэтому его символ расширения всегда правилен. Необходимо лишь доказать, что вектор инцидентности, у которого последняя компонента опущена, принадлежит циклическому ОРМ-коду. Иначе говоря, нужно доказать, что преобразование Фурье каждого вектора инцидентности f имеет компоненту Fj-, равную нулю, если

(/) < (9 - 1) m - (9 - 1) (т - г - 1) - 1, или, что то же самое,

(/) < (9 - 1) С- + !)•

Для доказательства достаточно вычислить F-и показать, что при всех таких / оно равно нулю, хотя при других / может быть отличным от нуля.

Шаг 1. Используя введенное в теореме 13.7.4 определение, представим (г-j- 1)-плоскость как множество [\г+\-\-yi\r + + V«V iVr-i Н-----h VtoVo}, где индексы

to = 0. 1. 9 - il = О, 1, q - \,

маркируют q элементов поля GF (q), а Vg, v+i - фиксированное множество независимых точек на (г + 1)-плоскости. Если элемент поля а принадлежит указанному множеству, то i-я компонента вектора инцидентности f равна единице; в противном случае она равна нулю. Поэтому спектральная компонента

может быть записана как сумма тех слагаемых, у которых Д равно единице; слагаемые, в которых ft равно нулю, можно опустить:

9-1 g-l 9-1

Pi= .li Х li (Vr+i + yiVr -Ь yi, iVr-i +----h ynVoy;

здесь Vo, Vr+i можно считать элементами GF (9+)- Необходимо определить те значения /, при которых Fj равны нулю. Используя полиномиальное разложение, получим

«0=0 1-=0 h

где под суммированием по h понимается суммирование по всем

наборам фо, hy, Ar+i), таким, что Hq + hy +----Ь Ar+i = /.

Затем переменим порядок суммирования и рассмотрим слагаемое вида (yiV)y где h фиксировано.

Шаг 2. Суммирование ?=оТ/ проводится по всем элементам поля GF (q), и поэтому сумма может быть выражена через примитивный элемент а. При h, отличных от нуля,

9-1 9-

«=о к=0

Величина в правой части равна h-й компоненте преобразования Фурье вектора, состоящего только из единиц. Эта компонента равна нулю во всех случаях, кроме случая, когда h кратно q - 1. В этом последнем случае она равна q - 1 (mod р), или -1. Для h, равного нулю,

I;y?= Si =0(modp);

j-.=0 i=0

no определению считалось, что у" = 1 при всех у, принадлежащих GF (q).

Ненулевые слагаемые в сумме, определяющей Fj, - это слагаемые, соответствующие тем hi, I = О, г, которые являются не-

нулевыми кратными q - 1; остальные слагаемые равны нулю и могут быть опущены. Сумма принимает вид

где суммирование производится по {h, K+i), таким, что hi, I = О, г, суть ненулевые кратные q - 1, hr+i О и

Шаг 3. По теореме Лукаса (теорема 13.3.3) в равенстве для Fj полиномиальные коэффициенты равны нулю в тех слагаемых, в которых hi, 1 = 0, г + 1, не является q-ичяъш потомком /; поэтому если hi входит в сумму, то hi, I = О, г + I, является р-ичным потомком / и, следовательно, q-ичпъш потомком /. Это получится из теоремы Лукаса, если записать

/! /I (/-ftp)!

П (/-ftp)! {!-ho-hi)\

~~ Ло-(/-Ло)! Л1Г(/-Ло-Л1)! Л2!...Лг+1! "" "

Кроме того, любая сумма hi, входящих в сумму, равна р-ичному потомку / и, следовательно, q-тяому потомку /.

Резюмируем условия, которым удовлетворяют слагаемые, вносящие вклад в величину F/.

(i) mihii;

(ii) hi, t = О, г, должны быть ненулевыми кратными q - 1 и hri0;

(iii) каждая позиция в (у-ичном разложении / равна сумме соответствующих позиций[ (7-ичных разложений hi.

Для заверщения доказательства необходимо показать, что при /, удовлетворяющем неравенству

Щ (/) < (9 -1) + 1).

таких слагаемых нет.

Шаг 4. Рассмотрим q-ячяo& разложение некоторого целого k:

k = ko + hq + kq + • • • + Кг-гЯ"-.

Тогда k (mod q - 1) можно вычислить следующим образом:

= o + i7 + n,-ir-.

k = ko + ki-----hm-i = (mod (7- 1)