При построении циклических, кодов ответственным этапом является выбор образующего (порождающего) полинома.
Правила выбора полинома зависят от требуемой корректирующей способности кода, при этом образующий полином должен обеспечивать как можно большее количество остатков при делении на кодовые комбинации. Выработаны и предлагаются следующие общие правила выбора образующего полинома при построении любого циклического кода:
1.Степень образующего полинома должна быть не меньше числа проверочных символов r
2. Любой многочлен g(х) степени (n-к), который делит без остатка двучлен Xn+1 может быть порождающим многочленом (n, к) циклического кода.
3. Образующий полином должен быть как можно более коротким.
4. Число ненулевых членов образующею полинома должно быть не меньше dмин.
Поскольку в циклическом коде опознавателями ошибок являются остатки от деления, то Р(х) должен обеспечивать требуемое число разлитых остатков. Обнаруживающая способность циклического кода определяется не только степенью обнаруживающего полинома. но и числом его членов.
|
|
Чем больше остатков может быть образованно при делении кодовой комбинации на образующий полином, тем выше корректирующая способность кода.
Образующий полином Р(х) циклического кода должен быть примитивным, т.е. входить в качестве сомножителя в разложение
двучлена xn+1= x2^m+1, где n - общее число разрядов в коде; m-любое целое положительное число. Признаком примитивных полиномов является наличие остатка равного единице только для полиномов х=1 и xn, т.е. число различных остатков n-1. В общем случае при построении циклического (n, к)-кода с исправлением 4 ошибок в качестве образующего полинома выбирается произведение из 4 сомножителей старших степеней, входящих в разложение двучлена вида xn+1. В роли сомножителей выступают неприводимые полиномы.
Неприводимые полиномы - это полиномы, которые делятся без остатка только па себя или на единицу.
Не всякий многочлен степени r, входящий в разложение данного двучлена, может быть использован для образования нужного (n, k)-кода.
Чтобы выяснить, какое из произведений может быть использовано в качестве образующего полинома, необходимо для каждого из них построить так называемую дополнительную матрицу. Эта матрица строится путем деления циклических сдвигов единицы с приписанными справа нулями на соответствующее произведение полиномов. При построении дополнительной матрицы Сr,k. по выбранному полиному необходимо также учитывать количество строк в цикле чередования проверочных разрядов и вес каждой строки (количество единиц).
|
|
Для получения возможности исправления требуемого числа ошибок в качестве образующего полинома выбирается то произведение, дополнительная матрица которого имеет все строки с весом, не меньшим, чем dмин.-1
Боуз и Чоудхурн показали, что для любых, целых положительных чисел m и tи существует циклический код элементности
n=2m-1 или m=log2(n-1) (5-2)
с кодовым расстоянием
dмин.>=2t0+1 (5.3)
При этом число проверочных символов r не превышает величины mtu т.е.
r<=mtu. (5.4)
Такой код гарантировано исправляет ошибки кратности tu и менее или обнаруживает ошибки кратности t0 и менее. Кроме того, код обнаруживает все пакеты ошибок, длина которых равна и меньше r.
Соотношение (5,2)-(5.4) используется для выбора образующего полинома.
Прим ер. Требуется построить циклический (n,к)-код. с исправлением в кодовых комбинациях двухкратных ошибок (tи=2). Пусть общее число элементов кодовой комбинации n=15. Согласно (5.2)-(5.4), m=4, r=8.
В этом случае двучлен x2^m+1= xn+1=x15 +1.
Можно показать, что в разложение двучлена х15+1 в качестве сомножителей старшей степени входят полиномы Р1(х4)=х4+х+1 —> 10011; Р2(х4)=х4+х3+1->11001; Р3(х4)=х4+х3+х2+x+1->11111. В учебнике (таблица 5.1) приведены образующие (примитивные) полиномы до 10-й степени.
Из трех возможных парных произведений полиномов четвертой степени получим три полинома восьмой степени r=8
Р1(х4)Рз(х4)= х8+ х7+х6+ х4+1 ->111010001
Р2(х4)Рз(х4)= х8+ х4+х4+ х+1 -> 100010111
Р1(х4)Р2(х4)= х8+ х7+х5+ х4+ х3+х+1 -> 110111011
Чтобы выяснить, какой из трех полиномов восьмой степени может быть использован в качестве образующего, найдем для каждого из них дополнительную матрицу С8.7- (к=15-8=7). Делением единицы с приписанными справа нулями и ее циклических сдвигов на 111010001 10001011 и 110111011 находим соответственные дополнительные матрицы
С8.7= 00011101
С8.7= 10111000
С8.7= 01000010
Для получения возможности исправления двойных ошибок до-полнигеяьные матрицы должны выбираться таким образом, чтобы вес м> каждой строки порождающей матрицы был не менее пяти единиц dмин.>=2tu+1
Так как каждая строка единичной матрицы Е- имеет вес равный единице, вес любой строки дополнительной матрицы должен быть не менее четырех единиц. Это требование, будет выполнено, если в качестве образующего полинома для построения циклического (15, 7)-кода выбрать одно из двух произведений: Р1(х4)Рз(х4) или Р2(х4)Рз(х4)=
В третьей дополнительной матрице С8.7 из семи строк третья, четвертая и пятая не обладают требуемым весом. Поэтому произведение Р1(х4)Р2(х4) не может быть использовано в качестве образующего полинома для построения циклического (.15, 7)-кода.