Циклические коды. Кодовые полиномы. Полиномиальная арифметика

Линейный блоковый код U длины называется циклическим, если наряду с любым своим кодовым словом u=(u₀, u₁, … , u_n–2, u_n–1) (для циклических кодов элементы удобнее нумеровать, начиная с нуля, а не единицы) он содержит и его циклический сдвиг u₁=(u_n–1, u₀, u₁, … , u_n–3, u_n–2). Другими словами, циклический код содержит все циклические сдвиги всех своих кодовых слов.

Продуктивным инструментом изучения и построения циклических кодов служит полиномиальное представление (повторяющее z-преобразование в теории дискретных систем). Кодовый полином, отвечающий кодовому вектору u=(u₀, u₁, … , u_n–2, u_n–1), определяется равенством

.

Коэффициенты u₀, u₁, …, u_n–1 кодового полинома – попросту элементы кодового слова (для q-ичного кода – элементы поля GF(q)), тогда как z – формальная переменная, служащая не для обобщенного представления произвольного элемента поля GF(q), а лишь для указания своей степенью позиции того или иного кодового символа как коэффициента полинома. Обозначим по соглашению z⁰ как 1. Например, полином u(z)= z⁷+z⁵+z²+1 означает, что в соответствующем кодовом векторе uединицы стоят на позициях 0, 2, 5, 7, в то время как, все остальные элементы равны нулю: u=(10100101).

Рассмотрим основные правила арифметики формальных полиномов с коэффициентами из GF(q) (полиномов над GF(q)).

Сложение двух полиномов a(z), b(z) и умножение полинома a(z) на скаляр a (элемент основного поля GF(q)) вводятся без затруднений:

,

устанавливая взаимно-однозначное соответствие векторного пространства и множества полиномов. Последние могут сами трактоваться как векторы пространства с описанными операциями сложения и умножения на скаляр.

Возьмем, к примеру, двоичные (т.е. над GF(2)) полиномы a(z)=z⁴+z²+z, b(z)=z⁶+z³+z²+1. Тогда их сумма a(z)+b(z)=z⁶+z⁴+z³+z+1.

Определим степень deg(f(z)) полинома f(z) как максимальный показатель в нем переменной z, имеющей ненулевой коэффициент. Например, для только что упомянутых полиномов deg(a(z))=4, deg(b(z))=6. Очевидно, deg(a(z)+b(z))£max{deg(a(z)), deg(b(z))}, deg(aa(z))=deg(a(z)), a¹0.

Новой операцией, не участвовавшей в определении векторного пространства, но критически важной для множества полиномов, является умножение последних. Распространяя на формальные полиномы правило дистрибутивности, а также коммутативность типа z^m·a=az^m, произведение полиномов можно определить равенством, полностью заимствованным из «школьной» алгебры полиномов с действительными коэффициентами: a(z)=a_mz^m+a_m-1z^m–1 +…+a₀, b(z)=b_lz^l+b_l-1z^l–1+…+b₀

При вычислении коэффициента c_i (являющегося, кстати, сверткой последовательностей коэффициентов сомножителей) a_t и b_i-t полагаются равными нулю, если их индексы выходят из диапазонов tÎ{0,1, …, m}, i–tÎ{0,1,…, l}. Заметим также, что deg(a(z)b(z))= deg(a(z))+deg(b(z)).

Для прежнего примера a(z)=z⁴+z²+z, b(z)=z⁶+z³+z²+1 произведение a(z)b(z)=z¹⁰+z⁸+z⁶+z⁵+z⁴+z³+z²+z.

В абстрактной алгебре структура, в которой элементы можно складывать, вычитать и умножать, называется кольцом(если, вдобавок, любой ненулевой элемент обратим по умножению, т.е. деление также присутствует, кольцо становится полем). Понятно, что множество полиномов над GF(q) является кольцом. Другим, более простым примером кольца служит множество целых чисел. В таком кольце с операцией умножения связан известный алгоритм деления с остатком. Возьмем некоторое положительное целое d. Тогда любое целое a можно записать как

где неотрицательное целое r , меньшее d , называется остатком (от деления a на d), q – частным, a – делимым, а d – делителем. Поскольку в кольце полиномов присутствует операция умножения, в нем можно по аналогии с кольцом целых чисел ввести деление полиномов с остатком. Формальные полиномы, разумеется нельзя упорядочить по признаку «больше–меньше», однако для введения понятия остатка можно опираться на сравнение степеней полиномов. Возьмем полином d(z) и представим произвольный полином a(z) соотношением

В этом равенстве, возможном для любых a(z), d(z), мы можем вновь именовать полиномы a(z), d(z), q(z) и r(z) делимым, делителем, частным и остатком соответственно.

Для вычисления частного и остатка при полиномиальном делении можно прибегнуть к алгоритму «длинного деления в столбик», переносящему на полиномы школьное правило деления целых чисел.

Пример 5.1.1Разделим с остатком полином a(z)=z⁶+z³+1 на полином d(z)=z⁴+z²+1 над GF(2). Алгоритм деления «в столбик» дает:

В теории циклических кодов важнейшая роль принадлежит остатку.

Часто используемая символика

означает, что полиномы a(z) и r(z) имеют один и тот же остаток от деления на d(z), или, поскольку deg(r(z)) меньше, чем deg(d(z)), то r(z) является остатком a(z). Если r(z)=0, т.е. a(z)=d(z)q(z)=0 mod(d(z)), то говорят, что a(z) делится на d(z) , или d(z) делит a(z) , или d(z) является делителем a(z), или, наконец, a(z) кратно d(z) . Уместно также говорить, что a(z) факторизуется на множители меньшей степени.

Полином, который не факторизуется на множители меньшей степени, называется неприводимым, в противоположность приводимому.

Так, например, полином z²+1 приводим в поле CF(2), тогда как z²+z+1 – неприводим. Неприводимые полиномы, не делясь ни на какие полиномы меньшей ненулевой степени, играют в полиномиальном кольце ту же роль, что и простые числа в кольце целых чисел.