Итак, циклический код полностью задается многочленом g(X), на который делится многочлен Xn— 1. С другой стороны, этот же код может быть полностью определен условием, что он является нулевым пространством идеала, порожденного многочленом h(X) = (Xn—l)lg(X)
. Если g(X)—многочлен степени г, то по теореме 6.11 размерность кода равна k = n — r. Элемент {f{X)} принадлежит коду тогда и только тогда, когда многочлен f(X) делится на g(X).
Многочлен h(X) называется проверочным многочленом для кода С, порожденного многочленом g (X). Поскольку Хп — 1 делится на h (X), то многочлен h (X) может быть использован в качестве многочлена, порождающего циклический код. Этот последний код эквивалентен коду, двойственному к коду С, и в теории циклических кодов его обычно называют просто кодом, двойственным к коду С.
В фирму по разработке программ обязательно нужен качественный принтер. Часто необходимо распечатать код и не только. Отличные версии принтеров и сканеров посмотрите на сайте АйЛовеПринтер.ру.
Пример. Пусть задан многочлен X7—1 = (X—1)(Х3-(-Х+ 1) (A3-f Х2 + 1)
над полем Галуа GF(2). Многочлен g(X) = X3 -f- X2 -f- 1 порождает циклический (7,4) -код. Элементы
{X3g {X)} = (1 1 0 1 0 0 0),1101000
{X2g{X)} = {0 1 10100), 0 110 100
{Xg{X)} = {00 1 10 10), 00 1 10 1 0
fe W >= (000 1 1 0 1), _0 0 0 1 1 0 1
можно выбрать в качестве базисных векторов, и, следовательно, матрицу G можно выбрать в качестве порождающей матрицы для этого кода. Этот код является нулевым пространством идеала, порожденного многочленом h (X) = (X — 1) (X3 + X + 1) = X* + X3 -f -fA^-hli
{A-2ft(A0} = (l 110 100), {Xh{X)} = {0 \ 110 10), {А (Я)} = (001 1101).
Поскольку, как указывалось в разд. 6.4, условия равенства нулю произведения многочленов и скалярного произведения соответствующих векторов не совпадают, то рассматриваемый код является нулевым пространством матрицы Н, образованной векторами {X2h(X)}, {Xh(X)} и {h(X)}
, компоненты которых записаны в обратном порядке:
(8.2)
-00 10 1 1 Г Н= 0101110 .10 11 1 00
Легко проверить, что GHr = 0. Этот код эквивалентен (7,4)-коду Хэмминга, что вытекает из того факта, что все столбцы матрицы Н различны.
Другой способ задания циклических кодов основан на использовании корней (которые, возможно, лежат в расширении поля) многочлена g{X), порождающего идеал. Предположим, во-первых, что все корни щ, а2, ov многочлена g(X) различны. Тогда циклический код полностью определяется следующим условием: вектор {f(X)} принадлежит кодовому пространству тогда и только тогда, когда аь аг, аГ — корни многочлена f(X). Связь этого метода задания циклического кода с предыдущим устанавливается теоремой 6.16. Если обозначить через тг-(Х) минимальную функцию для oii, то вектор {f(X)} является кодовым вектором тогда и только тогда, когда многочлен f(X) делится на т1{Х), т2(Х), ...
тг(Х) и, следовательно, на их наименьшее общее кратное. Поэтому код является идеалом, порожденным многочленом. |