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

k = Wg (k) (mod d - 1).

Если k равно ненулевому кратному q - 1, то и (k) равно ненулевому кратному q - 1.

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

Щ (/) =11Щ {hi),

у)

причем при / = О, ...,/ Wg (hi) являются ненулевыми кратными 9 - 1. Следовательно, если Fj отлично от нуля, то

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

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

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

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

Из определения /-плоскости в конечной геометрии следует, что векторы инцидентности всех /-плоскостей, которые содержат дан-

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

проверок.

2(9-1)

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

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

Проективно-геометрические коды образуют класс кодов, похожий на класс евклидово-геометрических кодов. Отличие состоит лишь в том, что они строятся из непримитивных циклических ОРМ-кодов длины (q" - \)l{q - 1), а не из ОРМ-кодов длины cf". Построение проводится так же, как и ранее. Существенную роль играют три поля: GF (р) - поле символов кода с простым р, GF (q) с q = р - поле символов непримитивного ОРМ-кода и GF (q) - поле локаторов.

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

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

Теорема 13.8.2. Проективно-геометрический код над GF (р) с параметрами г us и длиной {q" - \)l{q - 1) является циклическим кодом, порождаемым многочленом, корни которого расположены в точках р, причем j таковы, что О < / <: (q" - \)(q - 1) и

О < max (j (q - 1) p) (q - I) (m - r - 1),

0<t<s

где q = p, P == a- ы a - примитивный элемент поля GF (q). Доказательство аналогично доказательству теоремы 13.7.2. □

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

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

рые могут быть использованы на г-м шаге, равно , . Следо-

г m-t+l

вательно, на каждом шаге проводится не менее и корректирующая способность алгоритма равна

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

тарно декодируемы в г шагов. Осталось построить мажоритарный декодер и доказать, что ймд = 1 + - 1)!(д - 1).

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

Проективная геометрия PG (т, q) содержит - \)l{q - 1) точек и определяется ненулевыми точками из GF"+ (q). Таких ненулевых точек - 1, и они разбиваются на (9"+ - \)/(q - 1) множеств, каждое из которых включает одну точку PG (т, q). В каждую точку PG (т, q) проектируется q - 1 точек 0"+ (q) (этим и объясняется название проективной геометрии).

Правило образования этих множеств следующее: для любого ненулевого вектора v в GF"+ (q) и любого ненулевого элемента К поля GF (q) \ hXv принадлежат одному множеству V; иначе говоря, они отображаются в одну и ту же точку PG (т, q). Число таких ненулевых % равно q - 1, и поэтому в множестве содержится q - 1 векторов. Следовательно, точки проективной геометрии отождествляются с ((?"+ - \)l{q - 1) различными одномерными подпространствами из (jf+i (q).

Проективная геометрия PG {т, q) размерности т над полем Е (q) - это множество таких (9"+ - \)l{q - 1) точек вместе