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

Систематический циклический код может быть полностью определен своей производящей матрицей, которая строится по следующему правилу. Сначала записывается единичная матрица Е_k для исходного k-элементного кода. Далее одночлен, соответствующей каждой из строк Е_k, умножается на х^n-k и делится на производящий многочлен Р(х). В результате деления получим остатки, каждый из которых соответствует определенной строке матрицы Е_k. Из этих остатков составляется дополнительная матрица R, которая приписывается к матрице Е_k. Таким образом, производящая матрица для циклического (n, k)-кода будет иметь вид G=[RЕ_k], где R-приписанная к Е_k проверочная матрица размерности k * (n-k).

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

Пример. Пусть необходимо построить циклический код, для которого n=7, k=4, n-k=3, а P(x)=1+x+x³. Прежде всего запишем единичную матрицу Е_k:

строкам которой соответствуют одночлены 1, х, х², х³.

Каждая строка умножается на х^n-k = х³тогда получим новую матрицу, в которой каждая строка будет сдвинута на n— k нулей.

Каждый из полученных многочленов делится на производящий многочлен Р(х) и находится соответствующий остаток степени n-k, который и записывается на месте первых нулей в новой матрице.

Найденные остатки многочленов x³, x⁴, x⁵, x⁶ на P(x)=1+x+x³ будут соответственно равны R₁(x)=1+x; R₂(x)=x+x²; R₃(x)=1+x+x²; R₄(x)=1+x².

Теперь составляем проверочную матрицу R, элементами которой являются остатки в двоичной форме записи:

Приписывая эту матрицу к единичной матриц Е_k, получим производящую матрицу для циклического кода

Образующая матрица G позволяет преобразовывать комбинацию исходного кода (a₀, a₁, … a_k-1) в комбинацию циклического кода путем ее умножения на матрицу G. Пусть для рассматриваемого примера кода исходная комбинация равна (1110), т.е. φ (х)= 1+x+x². Умножив ее на матрицу G, т.е. [1110]* G, получим циклическую комбинацию (0101110).

В [7] доказана следующая теорема:

Если V-пространство строк матрицы G=[RЕ_k], где Е_k-единичная матрица размерности k*k, а R-матрица размерности k*(n-k), то V-является нулевым пространством матрицы H=[E_n-kR^T], где E_n-k- единичная матрица размерности (n-k)*(n-k), а R^T-транспорированная матрица R.

По этой теореме двоичный систематический циклический (n,k)-код, производящая матрица которого имеет вид G=[R Е_k], является нулевым пространством проверочной матрицы H=[E_{n- k}R^T] и, следовательно, G*H^T=0.

Так, для нашего примера матрица H с учетом найденного ранее матрицы R будет иметь вид:

Легко проверить, что G*H^T=0.

Для несистематического кода образующая матрица G строится в соответствии с правилом построения кода, а именно, путем умножения многочлена исходной комбинации φ(x) на порождающий многочлен Р(x). Для получения матрицы G составляют единичную матрицу E_k и каждую ее строку, представленную одночленом x_i, умножают на многочлен Р(x). Из коэффициентов полученных многочленов x_i* Р(x) составляют образующую матрицу G несистематического кода. Для рассматриваемого выше примера кода (7,4) с Р(x)=1+x+x³, записав произведения x_i* Р(x), где i=0,1,2,3, получим следующую матрицу G:

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

Выражение (2.9) следует из свойства 2.2 циклических кодов и сравнения (2.4), согласно которому многочлен Р (х) является делителем двучлена хⁿ + 1, где п = 2^n-k — 1. Тогда строки проверочной матрицы Н будут состоять из коэффициентов мно­гочленов хⁱН(х), где i = 0,1,..., (п — k —1). Так, для рассматриваемого примера кода (7, 4) имеем Н(х)= =(x⁷+1)/P(x)=1+x+x²+x⁴.

Записав многочлены Н(х), xH(x), x²H(x), составим проверочную матрицу H:

в которой строки записаны начиная со старшей степени.

Легко проверить, что G*H^T =0.

Следует отметить, что может быть построена проверочная матрица H, единая как для систематического, так и для неси­стематического кода, исходя из свойства 2.1 циклических ко­дов. Из этого свойства следует, что, если некоторый элемент а поля GF(2ⁿ) является корнем многочлена Р (х), то он явля­ется также и корнем многочлена f (х). Отсюда любая комбина­ция циклического кода, представленная многочленом (2.1), удовлетворяет равенству

f(α)≡0, (2.10)

которое может быть получено как произведение [с_ос₁c₂... c_п-1] Н^Т, где H-проверочная матрица вида:

H=[1αα²….α^n-1]. (2.11)

Учитывая, что для рассматриваемого примера кода (7, 4) по­рождающий многочлен Р(х) = 1+х+x³ является примитив­ным и а — его корень, матрица Н будет состоять из ненулевых элементов поля GF (2³), т. е.

H=[1αα²α³α⁴α⁵α⁶].

Заменив элементы αⁱ их двоичными векторами и записав их в виде столбцов получим следующую проверочную матрицу:

Легко проверить, что полученная проверочная матрица Н удовлетворяет равенству G*H^T=0 как для систематического, так и для несистематического циклических кодов (7,4), построенных по многочлену Р(х)=1+х+х³.

Дата добавления: 2015-07-16