11.5. КОДЫ МДР, ПОЛУЧЕННЫЕ ИЗ КОДОВ РИДА-СОЛОМОНА

Пусть ненулевые элементы поля GF(q). Расширенный -код описанный в § 10.3, имеет следующую проверочную матрицу:

К этому коду всегда можно добавить еще один проверочный символ и получить -код МДР с проверочной матрицей вида

Чтобы показать это, мы должны проверить, что любые столбцов матрицы линейно независимы, т. е. образуют невырожденную матрицу. В самом деле, любые из первых столбцов образуют матрицу Вандермонда (лемма 17 гл. 4) и поэтому линейно независимы.

Аналогично, если столбцов включают один или оба последних столбца матрицы то, разлагая определитель полученной матрицы по этим столбцам, мы вновь придем к определителю матрицы Вандермонда.

В действительности существуют циклические коды с такими же параметрами.

Теорема 9. Для любого существует циклический код МДР над полем GF(q).

Доказательство. Мы рассмотрим только случай для нечетных доказательство аналогично. Чтобы исключить тривиальные случаи, предположим, что —1. Рассмотрим многочлен над полем Циклотомические смежные классы, образующиеся при умножении на и приведении по модулю равны:

Так, например, если то мы имеем следующие циклотомические смежные классы:

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

где — примитивный корень степени из единицы. Здесь действительно, если примитивный элемент то можно положить

Упражнение. (8). Показать, что при этом значении а элемент принадлежит полю

Рассмотрим теперь циклический код с порождающим многочленом

Этот многочлен имеет последовательных нулей следовательно, согласно границе

БЧХ минимальное расстояние кода равно по крайней мере Так как то построенный нами код — код МДР. Этим способом строятся требуемые коды для всех четных значений

Аналогично код с порождающим многочленом

который имеет 21 последовательных корней

представляет собой -код МДР. Этим способом строятся требуемые коды для всех нечетных значений

Пример. Коды длины над Пусть примитивный элемент поля примитивный элемент поля примитивный корень девятой степени из единицы. Тогда, как следует из рис. и

Следовательно,

Код над полем с проверочным многочленом вырожден (так как делит см. лемму 8 гл. 8). Это — [9, 2, 6]-код с порождающим идемпотентом или в обычных обозначениях.

Три других кода размерности 2 являются -кодами. Их порождающие идемпотенты легко находятся и имеют следующий вид:

Коды, имеющие эти идемпотенты, являются минимальными кодами (§ 8.3) и состоят из девяти циклических сдвигов своих идемпотентов и пропорциональных им векторов. Код с

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

Упражнение. (9). Найти порождающие идемпотенты и весовые спектры этих кодов.

Случай четное число. Известны только два случая, когда можно добавить еще один проверочный символ, а именно когда или

Теорема 10. Существуют (трижды) расширенные коды РС (а следовательно, МДР).

Доказательство. Воспользуемся матрицей

в качестве порождающей матрицы либо проверочной. Любые три столбца ее линейно независимы, так как все элементы различны.