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

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

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

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

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

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

Определение 13.6.2. Циклическим ОРМ-кодом порядка и длины над полем называется циклический код, порождающий многочлен которого имеет корни а при всех таких, что

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

Из определения 13.6.1 следует, что модулю имеют одинаковый вес в -ичном разложении. Поэтому если является корнем то и все сопряженные с элементы являются корнями и определение 13.6.2 в самом деле приводит к коду над

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

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

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

и все их циклические сдвиги. Поэтому проверочные частоты появляются при и при всех сопряженных с ними числах. Этот циклический ОРМ-код второго порядка идентичен -коду БЧХ над GF (2). Расширение этого циклического кода представляет собой -код ОРМ.

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

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

и всеми их циклическими сдвигами. Поэтому проверочные частоты появляются при и 11 и при всех сопряженных с ними числах. Получаемый циклический ОРМ-код первого порядка является -кодом, а его расширение представляет собой -код ОРМ. Так как 9 принадлежит тому же классу сопряженных элементов, что и 5, а 13 сопряжено с 11, циклический код идентичен -коду БЧХ.

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

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

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

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

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

преобразование Фурье. Однако конструкция кодера во временной области обычно проще.

Минимально; расстояние циклических ОРМ-кодов должно удовлетворять границе БЧХ. Эту границу устанавливает следующая теорема.

Теорема 13.6.3. Циклический ОРМ-код над порядка и длины представляет собой подкод кода БЧХ с конструктивным расстоянием ; его минимальное расстояние не меньше указанного конструктивного.

Доказательство. В двоичном представлении записывается -разрядным двоичным числом, состоящим из одних единиц. Числа, меньшие имеют менее единиц. Поэтому при и а являются корнями при Следовательно, этот код является подкодом кода с конструктивным расстоянием

Недвоичный циклический ОРМ-код порядка также представляет собой подкод кода БЧХ, конструктивное расстояние которого равно если меньше Если последнее условие не выполняется, то выражение для конструктивного расстояния несколько сложнее, что отражеио в следующей теореме.

Теорема 13.6.4. Пусть где . Циклический ОРМ-код над порядка и длины представляет собой подкод кода БЧХ над с конструктивным расстоянием

его минимальное расстояние не меньше указанного конструктивного.

Доказательство. Рассмотрим -ичное разложение числа Максимальный значащий символ этого числа равен ; остальные символов равны Следовательно,

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

Рис. 13.7. (см. скан) Параметры некоторых обобщенных кодов Рида-Маллера.

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

Теорема 13.6.5. Код, дуальный ОРМ-коду над порядка и длины эквивалентен ОРМ-коду порядка и длины

Доказательство. Пусть ОРМ-код, и пусть — циклический ОРМ-код, получаемый укорочением Доказательство теоремы распадается на три шага. На шаге 1 находится порождающий многочлен кода дуального циклическому ОРМ-коду . На шаге 2 показывается, что проверочные многочлены как так и имеют множителем На шаге 3 производится расширение кодов и до ОРМ-кодов и показывается, что расширенные кода дуальны.

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

и

При всех указанных величины а являются корнями порождающего многочлена Для удобства мы заменили 0 на в интервале изменения (см. примечание на с. 469), так что при всех Из теории циклических кодов следует, что для определения проверочных частот дуального кода нужно заменить на и обратить нестрогое неравенство для «у-ичного веса, заменив его строгим неравенством. Поэтому индексами проверочных частот служат те для которых

Но если

то

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

Соответствующие этим числа являются корнями порождающего многочлена дуального кода

Шаг 2. Число не является корнем ни ни Следовательно, проверочные многочлены как так и содержат множители

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

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

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

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