Шаг 3. Теперь расширим W и и получим два ОРМ-кода. Проверочные матрицы этих расширенных кодов равны

где Н и Н - проверочные матрицы кодов Wn W. Если временно исключить из рассмотрения первые строки каждой из матриц, получим, что все строки левой матрицы ортогональны всем строкам правой матрицы; это вытекает из справедливости этого утверждения для Н и Н. Далее, строка, целиком состоящая из единиц, ортогональна самой себе, поскольку длина кода кратна д. И наконец, строка, целиком состоящая из единиц, ортогональна любой другой строке обеих матриц, так как л; - 1 является делителем обоих проверочных многочленов. Поэтому левая и правая матрицы ортогональны, а размерности расширенных циклических кодов в сумме равны q". Доказательство закончено. □

Непримитивные ОРМ-коды могут быть также определены очевидным образом. Этим определением мы завершаем параграф.

Определение 13.6.6. Пусть b делит q" - 1. Циклическим непримитивным ОРМ-кодом порядка г и длины п = (q" - l)/b над полем GF (q) является циклический код, порождающий многочлен которого имеет корни а при всех / = 1, (q" - 1)/Ь, таких, что О < (6/) < (q - \) т - г ~ \ .

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

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

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

Определение 13.7.1. Пусть г, s и m - любые положительные целые числа, и пусть q = р*, где р - простое число. Евклидово-геометричестм кодом над GF (р) порядка г и длины п = q" называется код, дуальный подкоду над подполем ОРМ-кода над GF (q) порядка,- 1) (т - г - 1) и длины q".

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

Теорема 13.7.2. Пусть а - примитивный элемент GF(q"). Евклидово-геометрисческий код над GF (р) с параметрами г и s и длиной д" - это расширенный циклический код, порождаемый многочленом, корнями которого являются ai при всех j, удовлетворяющих неравенствам О <: j q" ~ \ и.

О < max Wg {Ip) <. {q-\){m - r~ 1).

0<i<s

Доказательство. Подкод над подполем GF (р) циклического ОРМ кода порядка [q - ) [т - г - 1) обладает порождающим многочленом с корнями а/ при О < / < f?" - 1, если / удовлетворяет неравенству

Ц) <.{q-\) m-{q-\){m-r~\)-\ = {q-\){r + \)-\

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

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

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

является корнем этого взаимного многочлена, если а"- является корнем h (х), т. е. если

Щ {п - /•) >{q-\)(r + \)-\

при всех /, которые являются р-сопряженными с /числами. Но, как было установлено при доказательстве теоремы 13.6.5, ш,(п]- /) = ((7 - I) m - Wg (/). Следовательно,

Wgii) < (9 - 1) (m -г - 1)

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

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

Wiii) < т - г - \,

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

Наша цель - доказать, что евклидово-геометрические коды могут декодироваться мажоритарно в г -- 1 шагов и что с/д = = (9"- - l)l{q - I). Мы опишем декодер на геометрическом языке, языке евклидовой геометрии, который мы сейчас введем.

Евклидова геометрия размерности т над полем GF (q) (она обозначается через EG (m, q)) состоит из q" точек (векторное пространство GF" (q)) вместе с некоторыми подмножествами, называемыми плоскостями (или аффинными подпространствами )), рекуррентное определение которых следует ниже. 0-плоскостью (нульмерным аффинным подпространством) называются точки EG (m,q).MMH являются 9" векторов /n-мерного векторного про-

1) Векторное подпространство должно содержать начало координат векторного пространства. Аффинное подпространство получается сдвигом векторного подпространства (т. е. является его смежным классом).