6.3. Построение порождающей и проверочной матриц циклических кодов.

Любой циклический (n, k) – код может быть задан в соответствии с определением 2, порождающим многочленомg(x) или проверочным многочленом.

Знание этих многочленов позволяет построить порождающую матрицу и матрицу проверок. Для циклического (n, k) – кода существует простой способ нахожденияkлинейно независимых кодовых комбинаций, образующих порождающую матрицу. Этот способ состоит в следующем. Записывается порождающий многочленg(x). В соответствии с определением 2 комбинация, соответствующая порождающему многочлену, принадлежит циклическому (n, k) – коду. В соответствии с определением 1 циклические сдвиги комбинации, соответствующейg(x), также должны принадлежать этому же коду. Алгебраически сдвиг соответствует умножению кодовой комбинации нах. Так как степеньg(x)равнаn-k, то подобным образом мы можем получить кодовые комбинации

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

.

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

Аналогичным образом по проверочному многочлену можно построить матрицу проверок

.

Пример 6.4.Для циклического (7,4) – кода с порождающим многочленом(см. пример 6.3.) построить порождающую матрицу.

Находим

Следовательно, порождающая матрица для данного кода имеет вид:

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

Свойство 6.1. Произведение кодовой комбинации циклического кодана произвольный многочлендает кодовую комбинацию этого же циклического кода.

Действительно , а любое произведение такого вида равно нулю, т.е. принадлежит кодовому подпространству (раздел 6.2).

Более элементарное доказательство:

.

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

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

Коэффициент при хв произведенииравен

.

Слагаемые, содержащие , появляются вследствие слагаемых в произведении, которые содержат. Но так как, т.е., то. Равенство дляможно представить в виде скалярного произведения:

.

В этом произведении первый вектор соответствует а(х). Второй вектор содержит коэффициентыb(х), расположенные в обратном порядке и сдвинутые циклически наj+1 элемент вправо.

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

.

Учитывая эту специфику необходимо при матричном описании кода коэффициенты матрицы проверок записывать в обратном порядке. В этом случае будет выполнено условие

Пример 6.5. Построить матрицу проверок для циклического (7,4) – кода из предыдущего примера.

Для построения матрицы проверок найдем проверочный многочлен

Отсюда

В силу того, что условие равенства нулю произведения многочленов и скалярного произведения соответствующих им векторов не совпадают, для выполнения равенства при построении матрицыкомпоненты векторов, соответствующихh(x), xh(x) и x²h(x)записываем в обратном порядке

.

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

Вообще говоря, циклические коды Хэмминга строятся на основе порождающих многочленов степени m, являющихся сомножителями двучленов и не являющихся сомножителями никаких двучленов меньшей степени. Корни этих многочленов имеют порядок 2^m-1, т.е они являются примитивными элементами поляGF(2^m).Это означает, что порождающий многочлен кода Хэмминга порождает полеGF(2^m).

Условимся в любом циклическом коде первые n-kэлементов кодовой комбинации, то есть коэффициенты прииспользовать в качестве проверочных элементов, а последниеkэлементов, то есть коэффициенты при, - в качестве информационных (рис. 6.1).

a₀a, ….., a_n-1 = a₀x⁰+a₁x¹+ …. + a_n-1xⁿ⁺¹

x⁰ x¹ x² x^n-k-1 x^n-k x^n-2 x^n-1

a0

a1

a2

… … … … ..

an-k-1

an-k

… … … …

an-2

an-1

Избыточные элементы Информационные элементы

Рис 6.1

Структура кодовой комбинации циклического кода

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

Всякий циклический (n, k) – код приводится к этой форме следующим образом.

Пусть есть многочлен степениk-1, соответствующий комбинации простогоk – элементного кода, которую необходимо закодировать циклическим (n, k) – кодом. В комбинации циклического (n, k) – кода этуk- элементную комбинацию необходимо поместить на позиции информационных элементов, для чего помножим многочленна. В результате получаем многочлен, степень которого равна n-1. Так как по определению циклического кода каждая кодовая комбинация должна делиться на порождающий многочленg(x)степениn-k, то проверим выполнение этого условия. В общем случае в результате деления получим частноеq_i(x)степениk-1 и остаток, степень которого не превышаетn-k-1. Результат деления представим в следующем виде:

.

Рассмотрим многочлен . Коэффициенты приэтого многочлена являются коэффициентами остатка, а коэффициенты при степеняхэлементами первичной кодовой комбинации.

С другой стороны

,

то есть многочлен делится наg(x). Итак,и есть искомая кодовая комбинация циклического (n, k) – кода. Отсюда получаем правило построения порождающей матрицы циклического (n, k) – кода в канонической форме:

,

где I_k– единичная матрица размерности, соответствующая информационным элементам кодовых комбинаций,;

- матрица размерности ,j-я- строка, которой соответствует остатку от делениянаg(x).

Матрица проверок строится на основании матрицыпо правилу

.

Пример 6.6.Построить порождающую матрицу и матрицу проверок в канонической форме для циклического (7,4) – кода с порождающим многочленом. Находим частное и остаток от делениянаg(x)и записываем результат деления в форме равенства

I₃

R_4x3

О

R_4x3

I₄

кончательно получаем

.

Из рассмотренного примера видно, что проверочная матрица циклического (n, k) – кода содержит в качестве столбцов остатки от деленияна порождающий многочленg(x).Сравнение столбцов найденной проверочной матрицы с элементами поляGF(2³)показывает их полное совпадение с ненулевыми элементамиGF(2³).Результаты рассмотренного примера будут использованы для обоснования эквивалентности различных столбцов вычисления синдрома.