15.3. Коды Рида — Маллера — слабые коды с легким декодированием

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

Обобщение кодов Рида — Маллера на недвоичный случай было дано Казами, Лином и Питерсоном [1967а].

15.31. Определения. -укороченным обобщенным кодом Рида — Маллера порядка с блоковой длиной (обозначается через ОРМ-код) называется циклический код над порождающий многочлен которого задается равенством

где — сумма цифр в -ичном представлении числа примитивный элемент поля

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

РМ-кодом порядка называется ОРМ-код порядка над

15.32. Свойства ОРМ-кодов,

15.321. РМ-код порядка является -удлиненным БЧХ-кодоле с конструктивным расстоянием

Доказательство, Если то

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

Доказательство. Полагая получаем, что но если

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

Доказательство.

15.324. Число информационных символов -кода порядка равно

Доказательство. Существует точно чисел таких, что

15.325. Число информационных символов порядка равно

где число разбиений числа на слагаемых, каждое из которых не превосходит

Доказательство. Количество целых чисел таких, что для всех к и равно нулевого порядка — код с повторением.

5.327. ОРМ-код первого порядка — -удлиненный регистровый код максимальной длины.

15.328. ОРМ-код порядка есть -удлиненный БЧХ-код, исправляющий одну ошибку.

15.329. ОРМ-код порядка содержит точно

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

пространства над . А именно

где есть -мерное аффинное подпространство в над Если то общая проверка на четность задается равенством если то

Утверждение 15.329 является непосредственным следствием теорем 11.64, 11.61 и 11.52. Читатель, пропустивший отмеченные звездочкой разделы в гл. 11, должен принять это предложение без доказательства.

Свойство 15.329 показывает, что минимальное расстояние каждого РМ-кода (и некоторых ОРМ-кодов) не превосходит границы 15.322 для БЧХ-кодов. Используя теорему 11.61, можно доказать, что минимальное расстояние каждого ОРМ-кода не превосходит границы для БЧХ-кодов. Так как доказательство этого факта аналогично доказательству теоремы 11.66, то оно опускается.

Согласно 15.327 и 15.328, класс ОРМ-кодов содержит некоторые хорошие коды как для малых, так и для больших скоростей. Однако при умеренных скоростях ОРМ-коды становятся плохими. При четном минимальное расстояние РМ-кода порядка с блоковой длиной равно код содержит проверочных символов, а -удлиненный БЧХ-код с блоковой длиной и расстоянием только проверочных символов. При РМ-код со скоростью 1/2 обеспечивает такое же минимальное расстояние, как и БЧХ-код со скоростью, стремящейся к 1. Даже при умеренных разница весьма существенна. РМ-код третьего порядка длины 128 имеет скорость 64/128, а -удлиненный БЧХ-код длины 128, исправляющий 7 ошибок, имеет скорость 78/128. Минимальное расстояние обоих кодов равно 16.

Тем не менее имеются две причины, благодаря которым РМ-коды занимают важное место в алгебраической теории кодирования: (1) изучение РМ-кодов дало дополнительную информацию о некоторых связанных с ними БЧХ-кодах; (2) скорость РМ-кодов незначительно меньше скорости сравнимых БЧХ-кодов, но зато РМ-коды допускают более легкий алгоритм декодирования.

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

Пусть характеристическая функция множества определенная равенствами:

Здесь и по определению

Определим, далее, покомпонентное произведение как слово, задаваемое умножением соответствующих компонент

15.34. Теорема. Каждое кодовое слово двоичного РМ-кода порядка может быть записано в виде многочлена степени не выше от переменных

Замечания. В качестве свободного члена многочлена выбирается единичный вектор 1.

Казами, и Питерсон доказали также теорему 15.34 для недвоичных ОРМ-кодов. В недвоичном случае в качестве выбираются некоторые специальные кодовые слова РМ-кода первого порядка; эти слова не могут быть определены соотношением (15.331), но их произведение определяется формулой (15.332).

Доказательство, Слово

— характеристическая функция -мерного подпространства пространства над Если то по теореме 11.64 (или свойству 15.329) слово (15.341) является кодовым словом РМ-кода порядка Число слов вида (15.341) равно согласно 15.324, оно совпадает с числом информационных символов РМ-кода порядка Для доказательства того, что все слова вида (15.341) линейно независимы, заметим, что характеристическая функция любого элемента из скажем, может быть представлена в виде многочлена от степени Таким образом, слов вида (15.341) линейно

независимы, и этих слов, степени которых образуют базис векторного пространства РМ-кода порядка

Теорема. Каждый с блоковой длиной инвариантен относительно любой подстановки, переводящей все аффинные подпространства пространства над в аффинные подпространства. Группа всех таких подстановок трижды транзитивна, и ее порядок равен

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

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

Рис. 15.3 Некоторые подстановки, сохраняющие РМ-коды длины 16.

Для иллюстрации теоремы 15.35 на рис. 15.3 приведен пример некоторых подстановок, сохраняющих РМ-код с блоковой длиной 16. Для записи подстановок используется описание поля приведенное в столбце 7 таблицы 4.1.