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

В циклических кодах результат деления двучлена (хⁿ+1) на порождающий полином g(х) дает проверочный полином h(х) степени , т.е.

h(х) = (хⁿ+1)/ g(х) , (23)

где - коэффициенты формальной переменной «х», могут быть равны «0» или «1».

Для циклических кодов должно выполняться условие:

g(x)∙h(x)=х^п+1=0 (24)

Пример 12 Определить, является ли полином g(х) = х³+х+1 порождающим для циклического кода (7;4). Если является, найти проверочный полином для этого кода.

Составим двучлен хⁿ+1=х⁷+1 и разделим его на полином g(х).

Так как R(x)=0, полиномом g(х) = х³+х+1 является порождающим; проверочный полином h(х) = х⁴+х²+ х+1.

Найти порождающие полиномы и параметры циклических кодов (k, r, d₀) при заданном n можно, разложив на множители двучлен вида (хⁿ+1). Например, двучлен (х⁷+1) раскладывается на следующие многочлены:

х⁷+1=(х+1) ^. (х³+х²+1) ^.(х³+ х+1).

Путем комбинирования полученных трех сомножителей можно образовать шесть делителей для двучлена хⁿ+1, которые можно использовать как порождающие полиномы:

g₁(х) = х+1; r = 1; n = 7; k = 6;

g₂(х) = х³+ х+1; r = 3; n = 7; k = 4;

g₃(х) = х³+ х²+1; r = 3; n = 7; k = 4;

g₄(х) = g₁(х)^. g₂(х) = х⁴+ х³+х²+1; r = 4; n = 7; k = 3;

g₅(х) = g₁(х) ^.g₃(х) = х⁴+ х²+х+1; r = 4; n = 7; k = 3;

g₆(х) = g₂(х)^. g₃(х) = х⁶+ х⁵+х⁴+х³+х²+х+1; r = 6; n = 7; k = 1.

Коды, задаваемые образующими полиномами g₂(х) и g₃(х), относятся к классу циклических кодов Хэмминга. Коды, задаваемые полиномами g₄(х), g₅(х), g₆(х), являются двойственными кодами Хэмминга и называются кодами максимальной длины (КМД).

Для циклических кодов Хэмминга (корректируют одну ошибку, d₀=3) выполняется равенство:

n=2^r-1, (25)

В общем случае для циклических кодов должно выполняться условие n≤2^r-1.

Дата добавления: 2015-08-13