Математическое введение к циклическим кодам

Так как каждая разрешенная комбинация n-разрядного циклического кода есть произведение двух многочленов, один из которых является образующим, то эти комбинации можно рассматривать как подмножества всех произведений многочленов степени не выше n - 1. Это наталкивает на мысль использовать для построения этих кодов еще одну ветвь теории алгебраических систем, а именно теорию колец.

Как следует из приведенного ранее определения, для образования кольца на множестве n-разрядных кодовых комбинаций необходимо задать две операции: сложение и умножение.

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

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

1) многочлены перемножаются по обычным правилам, но с приведением подобных членов по модулю два;

2) если старшая степень произведения не превышает n-1, то оно и является результатом символического умножения;

3) если старшая степень произведения больше или равна n, то многочлен произведения делится на заранее определенный многочлен степени nи результатом символического умножения считается остаток от деления.

Степень остатка не превышает n - 1, и, следовательно, этот многочлен принадлежит к рассматриваемому множеству k-разрядных кодовых комбинаций.

При анализе циклического сдвига с перенесением единицы в конец кодовой комбинации установлено, что таким многочленом n-й степени является многочлен хⁿ + 1.

Действительно, в результате умножения многочлена степени n-1 на х получим

G(x) = (x^n-1 + x^n-2 + … + x + 1)x = xⁿ + x^n-1 + … + x

Следовательно, чтобы результат умножения и теперь соответствовал кодовой комбинации, образующейся путем циклического сдвига исходной кодовой комбинации, в нем необходимо заменить хⁿна 1. Такая замена эквивалентна делению полученного при умножении многочлена на xⁿ + 1 с записью в качестве результата остатка от деления, что обычно называют взятием остатка или приведением по модулю xⁿ + 1 (сам остаток при этом называют вычетом).

Выделим теперь в нашем кольце подмножество всех многочленов, кратных некоторому многочлену g(x). Такое подмножество называют идеалом, а многочлен g(x)-порождающим многочленом идеала.

Количество различных элементов в идеале определяется видом его порождающего многочлена. Если на порождающий многочлен взять 0, то весь идеал будет составлять только этот многочлен, так как умножение его на любой другой многочлен дает 0.

Если за порождающий многочлен принять 1[g(x) = 1], то в идеал войдут все многочлены кольца. В общем случае число элементов идеала, порожденного простым многочленом степени n-k, составляет 2^k.

Теперь становится понятным, что циклический двоичный код в построенном нами кольце n-разрядных двоичных кодовых комбинаций является идеалом. Остается выяснить, как выбрать многочлен g(x), способный породить циклический код с заданными свойствами.

Дата добавления: 2014-11-25