Файл: Зелигер Н.Б. Основы передачи данных учеб. пособие.pdf

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

210 разрешенных кодовых комбинаций циклического кода. Так, для нахождения кодовой комбинации '11000:1010010001, полученной в предыдущем примере (стр. 72) делением полинома xhG(x) = xll-\-xi0-f-x:7-j-x5 на образующий полином Р(х) = = хй+ х * + х 2+Л, достаточно сложить по модулю два 1, 3, 6 и 10-ю строки мат­ рицы А 15, 10.

73

+ л' 7 + х8 + j: 9 + ^ 10 + jc12 + ^14. Просуммируем по модулю два полином:

Мы видим, что в полиноме ошибок ненулевые степени имеют

принятой кодовой комбинации ошибки отсутствуют или не обна­

Так как F(x) делится на Р(х) без остатка, то остаток Я(х), по­

щий полином Р(х), как и ранее, примем Р(х) = 1+ jc2 -|-x4 + x5. Ос­

принятой кодовой комбинации. Легко убедиться, что число ошибок в принятой кодовой комбинации равно весу полинома ошибок.

ВЫ БОР О Б Р А ЗУЮ Щ ЕГО ПОЛИНОМА

Для построения циклического (п, т)-кода, обеспечивающего обнаружение или исправление ошибок заданной кратности, преж­ де всего следует выбрать образующий полином Р(х) степени k — = п —т. Обнаруживающая способность циклического кода опреде­ ляется степенью образующего полинома и числом его членов.

Из теории кодирования известно, что образующий полином дол­ жен входить в качестве сомножителя в разложение двучлена я" + 1 .

74

рых делится без остатка число k. Пользуясь этими свойствами дву­

членов вида X2*- 1 +ІІ, можно выбрать необходимый образующий полином Р(х).

Пример. Требуется построить циклический (п, т)-кая е поправлением и ко­ довых комбинациях одиночных ошибок.

Пусть общее число элементов п кодовой комбинации равно 15. Число про­

вой и третьей степеней. Пользуясь таблицами для неприводимых полиномов (27],

(113], получим: хІ5+1 = і(х+1) (х2+х+!1)'(х1+ х -И )і(х 4-І-л3-Ы)і(х4+А3+ х г+ х -Н ).

Из всех сомножителей разложения ідвучлена а 15+11 требуется выбрать длин

из сомножителей четвертой степени (А=4). Для ответа на вопрос, какой из трех сомножителей четвертой степени может быть использован в качестве образующе­ го полинома, найдем для каждого из них дополнительную матрицу провероч­

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

Так как каждая строка единичной матрицы Ац имеет вес, равный едини­ це, то вес любой строки дополнительной матрицы должен быть не менее двух единиц. Это требование будет выполнено, если в качестве образующего полипома для построения циклического і(І1б, іШ)-жода выбрать один из двух сомно­ жителей: Pt.(х4) = х 4+ х + 1 или Р2 (хк) — хк+ х 3+' 1.

Рассматривая дополнительную матрицу А411, можно заметить, что цикл

чередования ее проверочных строк равен 5, в то время как для (15, М)-кода этот цикл должен быть равен Ы. Кроме того, из 5 строк матрицы только пер­ вая строка имеет необходимый вес (м >2), вес же остальных строк является

•недостаточным ( ш = 1 ) . Поэтому сомножитель Р»(х4) = а 4і+ а 3+ а 2+ а -(-1 «е может

быть использован в качестве образующего полинома для построения циклическо­ го (1і5, Ы)-кода.

Зная дополнительные матрицы А4 u и А4 ц можно построить определяю­

щие матрицы для даух эквивалентных циклических і(і15, 41)-кодов. Выбрав в качестве образующего полинома сомножитель /5і(х4) = х 4+х-НІ, можно построить определяющую матрицу (15, 111)-кода.

75

матрицы не изменяет корректирующей способности циклического кода, но приводит к увеличению его относительной избыточностиТак, относительная избыточность (9—5)/5 укороченного (9,5)-кода пс сравнению с относительной избыточностью (15—11)/11 (15, II)- кода увеличивается в 2 , 2 раза.

Матрицы А\ ,, и А'І п отличаются одна от другой только по­

рядком чередования строк с проверочными элементами. Переста­ новка проверочных элементов в дополнительной матрице приводит

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

В общем случае при построении циклического (п, т )-кода с исправлением в кодовых комбинациях Ь ошибок в качестве обра­ зующего полинома степени k выбирается произведение из о со­

Чтобы выяснить, какой из трех полиномов восьмой степени может быть ис­ пользован в качестве образующего, найдем для каждого из них дополнитель­ ную матрицу проверочных элементов Ай,т(т = 15—8=7). Делением единицы с

7 6

приписанными справа нулями на ІіЫОІОООІ, 100010111 и 110111011 находим со­ ответственные дополнительные матрицы:

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

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

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

Выбрав в качестве образующего полинома произведение Рі(хі)Рз(хі), мож­ но построить определяющую матрицу циклического (15,7) -кода, исправляющего все двойные н одиночные ошибки:

0 0 0 0 0 0 1 1 1 0 1 0 0 0 1

0 0 0 0 0 1 0 0 1 I 1 0 0 1 1

0 0 0 0 1 0 0 1 1 1 0 0 1 1 0

0 0 0 1 0 0 0 0 0 0 1 1 1 0 1

0 0 1 0 0 0 0 0 0 1 1 1 0 1 0

0 1 0 0 0 0 0 0 1 1 1 0 1 0 0

1 0 0 0 0 0 0 1 1 1 0 1 0 0 0

КО Д И Р У Ю Щ Е Е УСТРОЙСТВО

Из (2.36) следует, что полином комбинации F(x) циклического (п, т)-кода, может быть образован умножением полинома G(x), отображающего неизбыточный от-элементный код, на xh и прибав­ лением к этому произведению остатка R(x) от деления xhG(x) на образующий полином Р(х).

77