double arrow

Выбор образующего полинома

При построении циклических, кодов ответственным этапом яв­ляется выбор образующего (порождающего) полинома.

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

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 в качестве сомножителей старшей степени входят полиномы Р14)=х4+х+1 —> 10011; Р24)=х43+1->11001; Р34)=х432+x+1->11111. В учебнике (таблица 5.1) приведены образующие (примитивные) полиномы до 10-й степени.

Из трех возможных парных произведений полиномов четвертой степени получим три полинома восьмой степени r=8

Р14)Рз(х4)= х8+ х76+ х4+1 ->111010001

Р24)Рз(х4)= х8+ х44+ х+1 -> 100010111

Р1424)= х8+ х75+ х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)-кода выбрать одно из двух произведений: Р14)Рз(х4) или Р24)Рз(х4)=

В третьей дополнительной матрице С8.7 из семи строк третья, четвертая и пятая не обладают требуемым весом. Поэтому произве­дение Р14)Р2(х4) не может быть использовано в качестве образую­щего полинома для построения циклического (.15, 7)-кода.


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: