13.6. ОБОБЩЁННЫЕ коды РИДА -МАЛЛЕРА 4б9

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

Краткий список сверточных кодов, которые могут быть декодированы мажоритарно, приведен на рис. 13.6. Эти коды получены поиском на ЭВМ.

13.6. ОБОБЩЕННЫЕ КОДЫ РИДА-МАЛЛЕРА

Коды Рида - Маллера первоначально были введены нами как двоичные; теперь же мы перейдем к изучению кодов Рида-Маллера над произвольным полем Галуа GF (q). Хотя класс обобщенных кодов Рида-Маллера (ОРМ) содержит подклассы мажоритарно декодируемых кодов, он также содержит большое число кодов, которые не имеют практического интереса. Все они описываются одной и той же общей теорией.

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

Корни кодовых слов определяются довольно сложным и даже несколько загадочным образом. Определим вес целого числа в (7-ичном разложении.

Определение 3.6.1. Пусть / - целое число, -ичное разложение которого имеет вид

/ = /о -f jig + -I-----f

Весом j в q-тном разложении называется сумма (в смысле суммы целых чисел)

1 (/) = /о + il + /2 Н----+ /т-1-

Определение 13.6.2. Циклическим ОРМ-кодом ) порядка г и длины п = q - 1 над полем GF (q) называется циклический код, порождающий многочлен g- (х) которого имеет корни а при всех j = \ , (f - 1, таких, что

О < и;/) < (9 - 1) /п - г - 1.

Расширение этого циклического кода до кода длины п = (f-путем добавления символа простой проверки на четность называется ОРМ-кодом порядка г.

) Альтернативное определение заключается в выборе g (х) с корнями а, где / удовлетворяют соотношению О Шд (/) < ((? - 1) m - / - 1; по сравнению с принятым нами определением первое строгое неравенство заменено нестрогим. Тогда ОРМ-код получается удлинением циклического ОРМ-кода путем добавления вектора, состоящего из одних единиц, к G, а не к Н. При нашем определении коды Хэмминга являются циклическими ОРМ-кодами.

Из определения 13.6.1 следует, что / и jq (по модулю q - 1) имеют одинаковый вес в -ичном разложении. Поэтому если Р является корнем g (х), то и все сопряженные с Р элементы являются корнями g(x), и определение 13.6.2 в самом деле приводит к коду над GF (q).

При 9 = 2 ОРМ-код сводится к коду, эквивалентному коду Рида-Маллера; это тот же код, но с перестановкой компонент (поэтому он и называется обобщенным кодом Рида-Маллера). Эгот код при мажоритарном декодировании может исправлять 2т-г~1 - 1 ошибок. Циклические коды Рида-Маллера порядка т --2 являются кодами Хэмминга, так как в них все /, для которых W2 (j) = 1,. являются корнями g- (х);это/, равное 1 или числам, сопряженным с 1. Коды Хэмминга служат простейшим примером ОРМ-кодов.

Поучительно построить некоторые двоичные ОРМ-коды. Выберем /п = 5 и г = 2. Длина этого кода равна 31, и при мажоритарном декодировании он может исправлять три ошибки. Проверочные частоты KOfia маркированы всеми отличными от нуля /, для которых

Щ (j) < 2,

т. е. теми /, двоичное представление которых содержит не более двух единиц. Это двоичные числа

0 0 0 0 1

0 0 0 1 1

0 0 10 1

и все их циклические сдвиги. Поэтому проверочные частоты появляются при / = 1, 3 и 5 и при всех сопряженных с ними числах. Этот циклический ОРМ-код второго порядка идентичен (31,16,7)-коду БЧХ над GF (2). Расширение этого циклического кода представляет собой (32,16,8)-код ОРМ.

Далее выберем /п = 5 и г = I. Эгот код может исправлять мажоритарным способом семь ошибок. Индексы проверочных частот теперь удовлетворяют соотношению

W2 (/) < 3.

Эти индексы записываются двоичными числами

0 0 0 0 1 0 0 0 1 1 0 0 10 1 0 0 111 0 10 11

и всеми их циклическими сдвигами. Поэтому проверочные частоты появляются при / = 1, 3, 5, 7 и П и при всех сопряженных с ними числах. Получаемый циклический ОРМ-код первого порядка является (31,6,15)-кодом, а его расширение представляет собой (32,6,16)-код ОРМ. Так как 9 принадлежит тому же классу сопряженных элементов, что и 5, а 13 сопряжено с 11, циклический код идентичен (31,6,15)-коду БЧХ.

Отсюда следует, что как к (31,16)-коду БЧХ, так и к (31,6)-коду БЧХ применимо мажоритарное декодирование. Иная ситуация возникает при m = 6 и г = 2. Этот код Рида-Маллера при мажоритарном декодировании может исправлять семь ошибок. Индексы проверочных частот удовлетворяют соотношению

(}) < 3.

Эти индексы записываются двоичными числами.

О 0;0 00 1 00 0"0 1 1 0 0 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 10 11 0 0 1 10 1 0 10 10 1

и всеми их циклическими сдвигами. Поэтому проверочные частоты появляются при / = 1, 3, 5, 7, 9, 11, 13 и 21 и при всех сопряженных с ними числах. Этот циклический ОРМ-код второго порядка является (63,22,15)-кодом. Существует также (63,24)-код БЧХ, исправляющий семь ошибок. Указанный двоичный ОРМ-код имеет меньшую скорость, но зато может быть декодирован мажоритарно. Расширением этого циклического ОРМ-кода является (64, 22, 16)-код ОРМ.

Определим циклический ОРМ-код через спектр кодовых слов. Циклический ОРМ-код порядка г и длины п = q"" - 1 над полем GF (q) представляет собой множество слов, спектральные компоненты Cj которых равны нулю при всех /, удовлетворяющих неравенству

О < и; (У) < (9 - 1) /п - / - 1.

Кодирование в частотной области производится следующим образом: спектр во всех указанных частотах полагается равным нулю, оставшиеся частоты заполняются информацией в соответствии С ограничениями сопряженности, а затем производится обратное