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

Разрешенную кодовую комбинацию Ц.К. можно рассматривать как элемент подмножества множества многочленов степени не выше (n – 1). Для анализа Ц.К. используется аппарат теории колец.

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

Обе коммутативны, то есть:

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

ассоциативны, то есть: ;

и связаны законом дистрибутивности: Математическое введение в циклические коды

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

Чтобы наше замкнутое множество многочленов (n – 1) степени образовало кольцо, определим правила выполнения этих операций:

1. В качестве операции сложения выберем, как и в групповом коде, операцию сложения по модулю два без переноса в старший разряд, то есть .

2. Операция умножения по обычным правилам не проходит, так как нарушается условие замкнутости: Математическое введение в циклические коды. Поэтому вводится операция символического умножения по следующим правилам:

  • умножение осуществляется по обычным правилам с приведением подобных членов путем сложения по модулю два;
  • если полученный многочлен имеет степень меньше чем (n – 1), то он и принимается за результат умножения, если же степень больше чем (n – 1), то он делится на двучлен c записью в качестве результата умножения остатка от деления.

Так получается и при сдвиге с переносом единицы из старшего разряда в младший. Имеем:

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

После сдвига, соответствующего умножению на x, получим: Математическое введение в циклические коды, что недопустимо, так как x7 имеет степень более разрешенной xn–1, в данном случае соответствует x6.

Поделим на многочлен Математическое введение в циклические коды.

Получим в остатке R(x):

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

В качестве результата умножения принимаем R(x), что соответствует переносу единицы из старшего разряда в младший.

При выбранных операциях и все множество многочленов степенью ≤ (n – 1) образуют кольцо. Подмножество многочленов в кольце, кратных образующему многочлену g(x), называется идеалом, порождаемым g(x).

Количество элементов в идеале зависит от вида g(x).

  1. Если g(x) = 0, то в идеале всего один элемент «0».
  2. Если g(x) = 1, то в идеал входят все элементы кольца.
  3. Если g(x) многочлен степени m = nk, то число элементов в идеале – 2k. Эти элементы и есть искомый нами Ц.К.

Поэтому построение Ц.К. сводится к выбору образующего многочлена g(x) с заданными корректирующими способностями.

Требования к образующему многочлену циклического кода

Разрешенная кодовая комбинация Ц.К. должна делиться на g(x) без остатка. Для этого необходимо, чтобы на g(x) делились все многочлены образующей матрицы кода. Каждая строка матрицы получается циклическим сдвигом образующего многочлена g(x) с приведением по модулю Математическое введение в циклические коды. Поэтому i-тую строку матрицы ƒi(x) можно записать:

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

где c = 1, если максимальная степень многочлена больше (n – 1);

c = 0, если имеет степень < n.

Математическое введение в циклические коды делится на g(x) без остатка.

Поэтому, чтобы ƒi(x) делилось на g(x) без остатка, необходимо, чтобы делилось на g(x) тоже без остатка.

Если мы выбрали g(x) так, что он является делителем двучлена Математическое введение в циклические коды, то любой элемент кольца либо делится на g(x) без остатка и тогда входит в идеал, либо образует некоторый остаток – ri(x), который и является опознавателем ошибки. http://peredacha-informacii.ru/ Чем больше остатков, тем больше ошибок может исправлять выбранный образующий многочлен g(x).

Наибольшее число остатков дает неприводимый многочлен степени «m», когда m; n и k связаны между собой условиями: m = nk, а n = 2m – 1. Рассмотрим выбор g(x) в разных условиях.