U.S. ПРОЕКТИВНО-ГЕОМЕТРИЧЕСКИЕ КОДЫ 487

с наборами подмножеств, называемых /-плоскостями (/ = О, 1, т).

Содержащая Vq и V- 1-плоскость определяется следующим образом. Пусть Vq Vq hv-i Vi, не имеет значения, какие именно элементы выбираются (см. задачу 13.9). Тогда 1-плоскость (или линия), содержащая Vq и Vi, образуется точками PG (т, q), являющимися образами точек Роо + Pii в GF"+ (q), где Ро и Pi - произвольные элементы поля, не равные одновременно нулю. Выбрать Ро и Pi можно - 1 способами, поэтому отображение состоит из (q - \)l{q - 1) точек PG (m, q). Отсюда следует, что число точек 1-плоскости в PG (т, q) равно q + \.

Аналогично плocкocть, содержащая Vj, г = О, 1, t, определяется следующим образом. Пусть v- Vi при i -= О, t. Точки множества Vj должны быть линейно независимыми над GF"+ (q), так как множество Vi образуется различными точками из PG (т, q). Тогда f-плоскость, содержащая Vo. •••> Vt,-это множество точек PG (т, q), которые являются образами точек

PoVo + PiVi + ••• +P(V,

в GF" (q), где ро, Pf - произвольные элементы поля, не равные одновременно нулю. Величины ро, р( можно выбрать q+ - 1 способами, поэтому образ состоит из (д+ - l)/(q - 1) точек из PG (т, q). Отсюда следует, что {t + 1)-плоскость содержит q* -f q*- + • • +<7 + 1 точек.

Теорема 13.8.3. t-плоскость в PG (т, q) содержит точек и сама имеет структуру проективной геометрии PG

Доказательство. Утверждение о числе точек немедленно следует из равенства , -{q+ - \)l{q - 1). Утверждение о структуре/-плоскости вытекает из описания структуры PG (/, q). П

Теорема 13.8.4.

m-f 1 1

(i) PG (m, q) содержит [ j различных t-плоскостей при t = О, 1, т.

(ii) При любых s и t, таких, что О <: s < / < т, каждая

г /7.-S ]

s-плоскость содержится точно в различных t-плоскостях

b PG (m, q).

Доказательство по существу совпадает с доказательством теоремы 13.7.5. □

В приведенной ниже теореме проективно-геометрические коды определяются альтернативным способом. Эта теорема аналогична теореме 13.7.7 и доказывается точно так же. Она будет использована при доказательстве того, что проективно-геометрические коды мажоритарно декодируемы, точно так же как теорема 13.7.7

t!q).

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

Теорема 13.8.5. Проективно-геометрический код порядка г и длины п = (cf - \)l{q - 1) над GF (р) - это наибольший линейный код над GF (р), содержащий в своем нуль-пространстве векторы инцидентности всех г-плоскостей в PG (т, q).

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

Вектор инцидентности i принадлежит непримитивному циклическому 0РД1-К0ДУ, если компонента Fj преобразования Фурье равна нулю при

Щ ((<? - 1) /) < (9 - 1) m - (9 - 1) - / - 1) - 1.

((д - 1) /) <(q-l)(r+ 1).

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

Шаг 1. Представим /--плоскость как образ множества

{Tr,Vr + Yv ,Vr-iH----+Y.„Vo},

где индексы i, iy, ij. маркируют"9 элементов поля GF (q), а Vq, Vr - фиксированное множество независимых точек в /-плоскости. Точку, в которой все коэффициенты у равны нулю, исключать не обязательно, так как она не дает вклада в Fj. Вектор инцидентности f содержит в /-й компоненте единицу, если элемент поля a принадлежит этому множеству, и нуль в противном случае. Положим / = (q - 1) / при / = О, ...,(<?" - \)l{q - - 1) - 1 и вычислим спектральные компоненты Fj-.

Fp=Tc"fi =

= 1> T Ti (Y.-Л + Y.V-1-1 + • • • + Y/„o)", £„=0 t,=o /,,=0

где Vo, , Vj. i считаются элементами GF (q). Нужно определить те значения при которых эти компоненты равны нулю. Полиномиальное разложение дает

где суммирование производится по всем h, удовлетворяющим разложению Ло + 1 + ••• +К = /• Переменим порядок суммирования и рассмотрим сумму J]?=o {УгТ•

Шаг 2. В Hiyl суммирование проводится по всем элементам поля, и поэтому сумма может быть выражена через примитивный элемент а. Отсюда так же, как и при доказательстве теоремы 13.7.7, заключаем, что вклад в Fj- вносят лишь те слагаемые, в которых hi является ненулевым кратным q - 1. Поэтому

где суммирование проводится по (h, К), таким, что hi, I = = О, г, являются ненулевыми кратными q - \ v.

£ Л, = /.

Шаги 3 и 4. Как и при доказательстве теоремы 13.7.7, из теоремы Лукаса вытекает, что при всех I величина hi является q-m-ным потомком следовательно,

w,(i)=tw,{hi).

Но, как показано при доказательстве теоремы 13.7.7, Wq {hi) являются ненулевыми кратными q - 1 тогда и только тогда, когда hi есть ненулевое кратное q - 1. Следовательно, если Fj-отлично от нуля, то

Si , [t (Г) {q-\){r+ 1).

Это доказывает теорему. □

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

Теорема 13.8.6. Пусть q = р- Проективно-геометрический код г-го порядка длинып = (о - 1)/(0 - 1) над GF {р) может быть мажоритарно декодирозан в г шагоз при числе ошибок, не превышающем {q"-+ - 1)/[2 {q - 1)].