8.2. Матричное описание циклических кодов

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

все строки матрицы

Очевидно, что строки матрицы линейно независимы, а ранг матрицы совпадающий с размерностью кода, равен Следовательно, по теореме 2.9 пространство строк матрицы есть кодовое пространство.

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

Всякий циклический код может быть следующим образом сведен к этой модифицированной приведенно-ступенчатой форме. Пусть остаток от деления на многочлен :

Тогда векторы

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

где единичная матрица размерности матрица размерности строкой которой является вектор из коэффициентов многочлена Тогда по теореме 3.4 код является также нулевым пространством матрицы

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

Пример. Для двоичного циклического кода, порожденного многочленом

Матрица полученная здесь, построчно эквивалентна матрице, полученной в примере на стр. 158. Она задает даже не эквивалентный, а в точности тот же самый код.

Теперь рассмотрим двойственный код, т. е. код, порождаемый в соответствии с теоремой 6.12 многочленом этого порождающего многочлена

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

Будем снова предполагать, что многочлен принадлежит кодовому пространству тогда и только тогда, когда элементы являются его корнями. Если

то

и это равенство может быть записано при помощи произведения матриц

Это условие в точности эквивалентно условию, состоящему в том, что а — корень . В соответствии с теоремой 6.16 это условие совпадает также с условием, состоящим в том, что многочлен делится на минимальную функцию для элемента Далее, то, что элементы являются корнями многочлена эквивалентно условию, что соответствующий вектор принадлежит нулевому пространству матрицы

Совокупность всех многочленов, среди корней которых содержится элемент совпадает с нулевым пространством матрицы

и поскольку эта совокупность совпадает с совокупностью многочленов, которые делятся на минимальную функцию степени то эти многочлены образуют идеал, размерность которого по теореме 6.11 равна Так как размерность нулевого пространства матрицы (8.9) равна то из теоремы 6.11 или из теоремы 2.15 следует, что размерность пространства строк матрицы равна Заметим, что коэффициенты кодовых многочленов принадлежат полю элемент расширения поля, если только Элементы расширения поля можно рассматривать как векторы с компонентами над основным полем. Следовательно, размерность пространства строк матрицы (8.9) над равна Рассматриваемый ниже пример сделает это более ясным.

Если и определяют один и тот же минимальный многочлен то соответствующие им нулевые пространства совпадают и, следовательно, соответствующие пространства строк определяют одно и то же пространство над полем Поэтому при построении матрицы [см. (8.8)] нужно использовать только один корень каждого неприводимого сомножителя в разложении многочлена

Пример. Рассмотрим снова двоичный циклический код, содержащий вектор тогда и только тогда, когда элементы являются

корнями многочлена Здесь а — корень многочлена следовательно, примитивный элемент . В этом случае

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

или, если подставить, пользуясь табл. 6.1, векторное представление элементов поля:

Далее,

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

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

то

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