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

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

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

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

Теорема 13.8.2. Проективно-геометрический код над с параметрами и длиной является циклическим кодом, порождаемым многочленом, корни которого расположены в точках причем таковы, что и

где примитивный элемент поля

Доказательство аналогично доказательству теоремы 13.7.2.

На рис. 13.10 приведены параметры некоторых проективно-геометрических кодов. Проективно-геометрические коды

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

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

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

Проективная геометрия содержит точек и определяется ненулевыми точками из Таких ненулевых точек и они разбиваются на множеств, каждое из которых включает одну точку В каждую точку проектируется точек (этим и объясняется название проективной геометрии).

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

Проективная геометрия размерности над полем это множество таких точек вместе

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

Содержащая и -плоскость определяется следующим образом. Пусть не имеет значения, какие именно элементы выбираются (см. зздачу 13.9). Тогда -плоскость (или линия), содержащая и образуется точками являющимися образами точек рхуд в где и — произвольные элементы поля, не равные одновременно нулю. Выбрать можно способами, поэтому отображение состоит из точек Отсюда следует, что число Точек -плоскости в равно

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

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

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

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

Теорема 13.8.4.

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

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

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

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

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

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

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

Вектор инцидентности принадлежит непримнтивному циклическому ОРМ-коду, если компонента преобразования Фурье равна нулю при

или

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

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

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

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

где суммирование производится по всем удовлетворяющим разложению Переменим порядок суммирования и рассмотрим сумму

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

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

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

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

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

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

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

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

ЗАДАЧИ

(см. скан)

ЗАМЕЧАНИЯ

Четкая формулировка того, что класс мажоритарно декодируемых кодоп образует специальный подкласс кодов, пепраалпющих ошибки, принадлежит Месеи [1963]. Он установил общие принципы обращении с такими кодами, до этого

мажоритарное декодирование использовалось в некоторых частных случаях. Первы, кто использовал мажоритарное декодирование был Рид [1954], применивший его для декодирования кодов Рида-Маллера. В своей работе Месси интересовался сверточными кодами и определил класс мажоритарно декодируемых сверточных кодов. Дальнейшее развитие теории сверточных кодов принадлежит Робинсону и Бернстайну [1967], а также Ву [1976].

Нахождение конструктивных классов мажоритарно декодируемых блоковых кодов оказалось более трудным, и здесь работа продвигалась более медленно. Решающим вкладом явилось применение конечных геометрий при построении кодов, первоначально предложенное Рудолфом [1964, 1967] и реализованное Кослесником и Мирончиковым [1968], а также Касами, Лином и Питерсоном [1968], установившими, что коды Рида-Маллера являются циклическими (если исключить проверочный символ) и могут быть обобщены на произвольные алфавиты. Обощенные коды Рида-Маллера были введены в работе Касами, Лина и Питерсона [1968] и разрабатывались Уэлденом [1967, 1968], Касами, Лином и Питерсоном в их второй статье [1968], Геталсом и Дельсартом и Мак-Вияльямс [1970]. Простой метод построения, описанный в § 13.4. принадлежит Лину и Марковскому [1980]. Конечно-геометрические коды подробно обсуждались в обзорной статье Геталса [1975].