Требования, предъявляемые к образующему многочлену
Согласно определению циклического кода все многочлены, соответствующие его кодовым комбинациям, должны делиться на g(x) без остатка. Для этого достаточно, чтобы на g(x) делились без остатка многочлены, составляющие образующую матрицу кода. Последние получаются циклическим сдвигом, что соответствует последовательному умножению g(x) на х с приведением по модулю xn + 1.
Следовательно, в общем случае многочлен gi(x) является остатком от деления произведения g(x)·хi на многочлен xn + 1и может быть записан так:
gi(x)=g(x)xi + c(xn + 1)
где с =1, если степень g(x) хi превышает п-1; с = 0, если степень g(x) хi не превышает п-1.
Отсюда следует, что все многочлены матрицы, а поэтому и все многочлены кода будут делиться на g(x) без остатка только в том случае, если на g(x) будет делиться без остатка многочлен xn + 1.
Таким образом, чтобы g(x) мог породить идеал, а, следовательно, и циклический код, он должен быть делителем многочлена xn + 1.
Поскольку для кольца справедливы все свойства группы, а для идеала - все свойства подгруппы, кольцо можно разложить на смежные классы, называемые в этом случае классами вычетов по идеалу.
Первую строку разложения образует идеал, причем нулевой элемент располагается крайним слева. В качестве образующего первого класса вычетов можно выбрать любой многочлен, не принадлежащий идеалу. Остальные элементы данного класса вычетов образуются путем суммирования образующего многочлена с каждым многочленом идеала.
Если многочлен g(x) степени m = n-kявляется делителем xn + 1, то любой элемент кольца либо делится на g(x) без остатка (тогда он является элементом идеала), либо в результате деления появляется остаток r(х), представляющий собой многочлен степени не выше m-1.
Элементы кольца, дающие в остатке один и тот же многочлен ri(x), относятся к одному классу вычетов. Приняв многочлены r(х) за образующие элементы классов вычетов, разложение кольца по идеалу с образующим многочленом g(x) степени m можно представить табл. 4.12, где f(x)-произвольный многочлен степени не выше n-m-1.
Таблица 4.12.
| g(x) | x·g(x) | (x+1)·g(x) | … | f(x)·g(x) | |
| r1(x) r2(x) … … rn(x) | g(x) + r1(x) g(x) + r2(x) … … g(x) + rn(x) | x·g(x) + r1(x) x·g(x) + r2(x) … … x·g(x) + rn(x) | (x+1)·g(x) + r1(x) (x+1)·g(x) + r2(x) … … (x+1)·g(x) + rn(x) | … … … … … | f(x)·g(x) + r1(x) f(x)·g(x) + r2(x) … … f(x)·g(x) + rn(x) |
Как отмечалось, групповой код способен исправить столько разновидностей ошибок, сколько различных классов насчитывается в приведенном разложении. Следовательно, корректирующая способность циклического кода будет тем выше, чем больше остатков может быть образовано при делении многочлена, соответствующего искаженной кодовой комбинации, на образующий многочлен кода.
Наибольшее число остатков, равное 2m - 1 (исключая нулевой), может обеспечить только неприводимый (простой) многочлен, который делится сам на себя и не делится ни на какой другой многочлен (кроме 1).