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

Описание циклических кодов и их построение удобно проводить с помощью многочленов (или полиномов). Запись комбинации в виде полинома понадобилась для того, чтобы отобразить формализованным способом операцию циклического сдвига исходной кодовой комбинации. Так, n-элементную кодовую комбинацию можно описать полиномом (n − 1) степени, в виде:

A_n−1(x) = a_n−1 xⁿ⁻¹ + a_n−2 xⁿ⁻² + … + a₁ x + a₀,

где a_i = {0, 1}, причем a_i = 0 соответствуют нулевым элементам комбинации, a_i = 1 — ненулевым.

Запишем полиномы для конкретных 4-элементных комбинаций:

1101 ⇔ A₁(x) = x³ + x² + 1
1010 ⇔ A₂(x) = x³ + x

Операции сложения и вычитания выполняются по модулю 2. Они являются эквивалентными и ассоциативными:

· G₁(x) + G₂(x) ⇒ G₃(x)

· G₁(x) − G₂(x) ⇒ G₃(x)

· G₂(x) + G₁(x) ⇒ G₃(x)

Примеры

· G₁(x) = x⁵ + x³ + x

· G₂(x) = x⁴ + x³ + 1

· G₃(x) = G₁(x) ⊕ G₂(x) = x⁵ + x⁴ + x + 1

Операция деления является обычным делением многочленов, только вместо вычитания используется сложение по модулю 2:

· G₁(x) = x⁶ + x⁴ + x³

· G₂(x) = x³ + x² + 1

x⁶ + x⁴ + x³ | x³ + x² + 1 +------------x⁶ + x⁵ + x³ | x³ + x²------------ x⁵ + x⁴ x⁵ + x⁴ + x² ------------ x²

Циклический сдвиг кодовой комбинации

Циклический сдвиг кодовой комбинации — перемещение ее элементов справа налево без нарушения порядка их следования, так что крайний левый элемент занимает место крайнего правого.

Основные свойства и само название циклических кодов связаны с тем, что все разрешенные комбинации бит в передаваемом сообщении (кодовые слова) могут быть получены путем операции циклического сдвига некоторого исходного кодового слова.

Допустим, задана исходная кодовая комбинация и соответствующий ей полином:

a(x) = a_nxⁿ⁻¹ + a_n−1xⁿ⁻² + … + a₂x + a₁

Умножим a(x) на x:

a(x) · x = a_nxⁿ + a_n−1xⁿ⁻¹ + … + a₂x² + a₁x

Так как максимальная степень x в кодовой комбинации длиной n не превышает (n − 1), то из правой части полученного выражения для получения исходного полинома необходимо вычесть a_n(xⁿ − 1). Вычитание a_n(xⁿ − 1) называется взятием остатка по модулю (xⁿ − 1).

Сдвиг исходной комбинации на i тактов можно представить следующим образом: a(x) · xⁱ − a_n(xⁿ − 1), то есть умножением a(x) на xⁱ и взятием остатка по модулю (xⁿ − 1). Взятие остатка необходимо при получении многочлена степени, большей или равной n.