Порождающая матрица циклического кода

Лекция для 1 и 2 группы:

Порождающая матрица циклического кода

Знание порождающего многочлена позволяют легко построить порождающую матрицу G_ц циклического кода. В качестве строк этой матрицы обычно берутся коэффициенты k многочленов g(X), Xg(X),…, X^{k-1 g}(X). Поскольку степени этих многочленов различны, то строки матрицы G_ц линейно независимы. Матрица G_ц  записывается так:

Складывая строки матрицы G_ц  по две, по три и, наконец, все вместе получим все оставшиеся  2^k – k – 1 ненулевые комбинации циклического кода.

Пример:

Построить порождающую матрицу циклического (7, 4) – кода с порождающим многочленом g(X) = X³ + X +1. Заметим, что

k = r + 1 = 4.

Многочлены строк:

При сравнении матрицы G_ц  с матрицей G линейного кода видно, что они не совпадают. Однако используя элементарные операции над строками, матрицу G_ц можно привести к матрице G_. К элементарным операциям над строками матрицы относятся следующие 3:

1. перемена местами любых 2-х строк матрицы;
2. умножение любой строки матрицы на ненулевое число   (в нашем случае таким числом является 1, т.е. умножение любой строки на 1 не меняет ее);
3. прибавление по модулю два любой строки, умноженной на ненулевое число, к любой другой строке.

В теории матриц доказано, что если одна матрица получается из другой в результате последовательного применения элементарных операций над строками, то пространство строк этих двух матриц совпадает. Следовательно, матрица G, полученная из матрицы G_ц, порождает тот же циклический код, что и матрица G_ц. Однако матрица G больше характеризует циклический код как линейный, т.к. зная расположение в ней коэффициентов C_ji, сразу можно записать правило формирования проверочных символов, если циклический код рассматривать как линейный.