Во - вторых,известно,что двучлен типа (X^n + 1) = (X^2^z-1 + 1), в разложении которого в качестве сомножителя должен входить образующий многочлен,обладает тем свойством,что он является общим кратным для всех без исключения неприводимых полиномов степени z и разлагается на множители из всех неприводимых полиномов,степени z,которых делят без остатка число z.
Однако не всякий полином степени P,входящий в разложение двучлена
X^n + 1,может быть использован в качастве образующего полинома.Необходимо,чтобы для каждой из однократных ошибок обеспечиваля свой, отличный от других,остаток от деления принятой кодовой комбинации на образующий полином.Это будет иметь место при условии,если выбранный неприводимый полином степени P,являясь делителем двучлена
X^n + 1,не входит в разложение никакого другого двучлена X^l + 1, степень которого l < n.
В этом случае пользуются таблицами неприводимых многочленов.
ПРИМЕР.Выбрать образующий полином для построения циклического кода, содержащего k = 4 информационных символа и обеспечивающего исправление однократных и обнаружение двукратных ошибок.
p = n - k = > log 2 (n + 1).
p=[log 2 {(k + 1) + [log 2 (k + 1)]}] = [log 2 (5 + [log 2 5])]=3.
n = k + p = 7.
Образующий полином K(X) должен быть степени p=3 и входить в качестве сомножителя в разложение двучлена X^n + 1 = X^(2^z-1) + 1.
Так как n = 7,то составляющие сомножители двучлена должны быть неприводимыми полиномами,степени которых являются делителями числа
z = 3.К числам,на которые z = 3 делится без остатка,относятся 1 и
3.Следовательо,сомножителями двучлена X^7 + 1 должны быть неприводимые полиномы первой и третьей степеней.
Пользуясь таблицами неприводимых полиномов получим
X^7 + 1 = (X + 1)(X^3 + X + 1)(X^3 + X^2 + 1).
Ни один сомножителей степени 3 не входит в разложение другого двучлена X^n + 1 степени n < 7.Поэтому каждый из этих сомножителей может быть выбран в качестве образующего полинома.
ОПРЕДЕЛЕНИЕ ДВОЙСТВЕННОГО МНОГОЧЛЕНА.
Полином P(*)(X) = X^deg P(X) * P(X^-1) называется действенным (обратным) пелиному P(X).
ПРИМЕР.P(X) = X^4 + X^3 + 1.
P(*)(X) = X^4(X^-4 + X^-3 + 1) = X^4 + X + 1.
Двойственный многочлен неприводимого многочлена также неприводим,а двойственный многочлен примитивного многочлена примитивен.Поэтому в таблицах приводится либо сам многочлен,либо двойственный многочлен.
/* Для тог,чтобы проверить,является ли многочлен f(X) степени m
примитивным,применяется следующая последовательность операций:
1.Находятся вычеты 1,X,X^2,X^3,...,X^(2^m-1) по модулю f(X).
2.Эти вычеты умножаются и приводятся по модулю f(X) для того,чтобы построить вычет X^2^m - 1.Если результат отличается от 1,то многочлен отвергается. Если результат равен 1,то проверка продолжается.
3.Для каждого сомножителя r в разложении числа 2,m - 1 вычет для
X^r образуется перемножением подходящей комбинации вычетов,найденных на первом этапе.Если все эти вычеты не равны 1,то многочлен является примитивным.*/
Втаблицах полиномы даны в восьмеричном представлении,например,
0 - 000,3 - 011,7 - 111.Например,3525 обозначает многочлен 10-й степени:011101010101 или X^10 + X^9 + X^8 + X^6 + X^4 + X^2 + 1.
Образующие полиномы кодов,способных исправлять ошибки любой кратности,можно определять,пользуясь следующим правилом Хэмминга:
1.По заданному числу информационных разрядов k определяется число проверочных разрядов p,необходимое для исправления однократных ошибок,и находится образующий полином.
2.Рассматривая полученный (n,k) - код как некорректирующий n - разрядный код,определяют дополнительные разряды для обеспечения исправления одной ошибки в этом коде,и находят соответствующий образующий полином.
3.Повторяется данная процедура столько раз,пока небудет получен код,исправляющий независимые ошибки до данной кратности включительно.
Однако код,построенный таким образом,является неоптимальным с точки зрения числа избыточных разрядов.В этом отношении более совершенен код Боуза - Чоудхури - Хоквингема(БЧХ),обеспечивающий минимальное число проверочных символов при заданном k.БЧХ - коды будут рассмотрены позже.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.