13.7. ЕВКЛИДОВО-ГЕОМЕТРИЧЕСКИЕ КОДЫ

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

Несколько классов кодов, описываемых на языке конечных геометрий, являются мажоритарно декодируемыми — это евклидово-геометрические кода и проективно-геометрнческие коды. Мы введем эти классы кодов, используя терминологию кодов Рида-Маллера. Первоначально они были введены иначе, а именно на основе теории конечных геометрий; этим и объясняются их названия. В этом параграфе мы рассмотрим евклидово-геометрические коды, а в следующем — проективно-геометрические коды. Ограничимся изучением лишь кодов над простым полем Существенную роль играют три поля Галуа: поле символов евклидово-геометрического кода, поле символов ОРМ-кода, представляющее собой расширение для и поле локаторов

Определение 13.7.1. Пусть любые положительные целые числа, и пусть где простое число. Евклидово-геометрическим кодом над порядка и длины называется код, дуальный подколу над подполем ОРМ-кода над порядка и длины

Эквивалентное определение: евклндово-геометрическим кодом называется расширение циклического кода над (также называемого евклндово-геометрическим кодом) длины он определяется следующей теоремой.

Теорема 13.7.2. Пусть а. — примитивный элемент Евклидово-геометрисческий код над с параметрами и длиной это расширенный циклический код, порождаемый многочленом, корнями котюрого являются а! при всех удовлетворяющих неравенствам и

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

или если этому неравенству удовлетворяет любое -сопряженное с Обратно, а является корнем проверочного многочлена если

для всех которые являются -сопряженными с числами. Но, согласно теории циклических кодов, порождающий многочлен дуального кода является взаимным к многочлену Поэтому а

Рис. 13.8. Параметры некоторых евклидово-геометрических кодов и нскогорых кодов БЧХ.

является корнем этого взаимного многочлена, если является корнем т. е. если

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

при всех которые являются -сопряженными с числами. Отсюда следует утверждение теоремы.

Простейшим примером евклидово-геометрического кода служит код . В этом случае

если является корнем Это как раз код Рида-Маллера порядка Евклидово-геометрические коды представляют собой обобщение кодов Рида-Маллера. Параметры других евклидово-геометрических кодов приведены на рис. 13.8.

Наша цель — доказать, что евклидово-геометрические коды могут декодироваться мажоритарно в шагов и что Мы опишем декодер на геометрическом языке, языке евклидовой геометрии, который мы сейчас введем.

Евклидова геометрия размерности над полем (она обозначается через состоит из точек (векторное пространство вместе с некоторыми подмножествами, называемыми плоскостями (или аффинными подпространствами), рекуррентное определение которых следует ниже. 0-плоскостью (нульмерным аффинным подпространством) называются точки Ими являются векторов -мерного векторного

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

Приведем более формальное определение.

Определение 13.7.3. Евклидовой геометрией называется векторное пространство вместе со всеми подпространствами и сдвигами подпространств

Из этого определения непосредственно вытекает следующая теорема.

Теорема 13.7.4. t-плоскость содержит ровно точек и сама имеет структуру евклидовой геометрии Можно представить -плоскость как множество точек

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

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

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

Рис. 13.9. (см. скан) Евклидова геометрия при

Теорема 13.7.5.

(i) содержит различных -плоскостей, где .

(ii) При любых таких, что каждая -плоскость содержит точно различных -плоскостей из

Доказательство, (i) Можно построить -мерное подпространство, выбирая упорядоченное множество линейно независимых точек в Это можно сделать

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

подпространству. В самом деле, число множеств, приводящих к одному и тому же -мерному подпространству, равно

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

различных -мерных подпространств. Каждое подпространство имеет смежных классов, и поэтому существует -плоскостей.

(ii) Заданная -плоскость может быть расширена до -плоскости выбором последовательности независимых точек, не принадлежащих -плоскости. Это можно сделать

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

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

Определение 13.7.6. Вектором инцидентности подмножества множества элементов, маркированных индексом называется вектор размерности компонента которого равна единице, если элемент, маркированный индексом принадлежит этому подмножеству, и нулю в противном случае.

В нашем определении ОРМ-кода элементы используются для нумерации компонент векторного пространства размерности (которое само содержит векторов). Иначе говоря, элементы векторного пространства используются для индексации компонент векторного пространства Вектор инцидентности подмножества это вектор в Если определяет структуру евклидовой геометрии то вектор инцидентности плоскости в является вектором в Как мы увидим, вектор

инцидентности плоскости в является кодовым словом ОРМ-кода, содержащимся в

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

Теорема 13.7.7. Евклидово-геометрическим кодом порядка и длины над является наибольший линейный код над содержащий в своем нуль-пространстве векторы инцидентности всех -плоскостей в

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

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

или, что то же самое,

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

Шаг 1. Используя введенное в теореме 13.7.4 определение, представим -плоскость как множество где индексы

маркируют элементов поля фиксированное множество независимых точек на -плоскости. Если элемент поля а принадлежит указанному множеству, то компонента вектора инцидентности равна единице; в противном случае она равна нулю. Поэтому спектральная компонента

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

здесь можно считать элементами Необходимо определить те значения при которых равны нулю. Используя полиномиальное разложение, получим

где под суммированием по понимается суммирование по всем наборам таким, что Затем переменим порядок суммирования и рассмотрим слагаемое вида где фиксировано.

Шаг 2. Суммирование проводится по всем элементам поля и поэтому сумма может быть выражена через примитивный элемент а. При отличных от нуля,

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

по определению считалось, что при всех у, принадлежащих

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

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

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

Шаг 3. По теореме Лукаса (теорема 13.3.3) в равенстве для полиномиальные коэффициенты равны нулю в тех слагаемых, в которых является -ичным потомком поэтому если входит в сумму, то является -ичным потомком следовательно, -ичным потомком Это долучится из теоремы Лукаса, если записать

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

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

(ii) , должны быть ненулевыми кратными

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

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

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

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

Тогда к можно вычислить следующим образом:

так как по модулю число можно заменить единицей. Следовательно,

Если равно ненулевому кратному то и равно ненулевому кратному

Рассмотрим -ичные разложения Каждая позиция в -ичном разложении равна сумме соответствующих позиций в ичных разложениях Поэтому

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

Теорема доказана.

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

Теорема 13.7.8. Пусть Евклидово-геометрический код порядка и длины над может быть декодирован мажоритарно в шагов при числе ошибок, не превышающем

Доказательство. Доказательство проводится рекуррентно; показывается, что из множества проверочных равенств, основанных на векторах инцидентности -плоскостей, можно получить проверочные равенства, основанные на векторах инцидентности -плоскостей. Отсюда следует, что проверочные равенства, основанные на векторах инцидентности -плоскостей, как установлено теоремой 13.7.7, в нгагов сводятся к проверочным равенствам для отдельных символов. При этом надо рассуждать следующим образом.

Из определения -плоскости в конечной геометрии следует, что векторы инцидентности всех -плоскостей, которые содержат данную -плоскость, определяют множество проверок, которые согласуются в сумме ошибочных символов, связанных с точками этой -плоскости. Через любую точку, не принадлежащую заданной -плоскости проходит ровно одна -плоскость, содержащая Следовательно, используя мажоритарное решение, можно получить новую проверку, которая соответствует вектору инцидентности -плоскости Это же может быть сделано для всех -плоскостей, содержащих заданную -плоскость, которая в свою очередь определяет множество проверок, согласующихся в данной -плоскости.

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

Этим доказательство теоремы завершается.