Да (k=<\2) .используется образующий многочлен пятой степени Р(х) = х 5 + х4 + х2+\, т. е. число проверочных эле ментов будет равно пяти (/" = 5). Определим значения проверочных элементов для 'Комбинации 010001011001
|
G (х) = х 1 0 |
+ х е + х* + Xs |
+ |
1. |
|
Помножим многочлен сообщения |
G(x) |
на Xs и полу |
ченное произведение разделим на Р(х). |
Путем последо |
вательного деления найдем частное Q(x)=xi0 |
+ x9 + x&-\-\ |
и остаток R(x) = х 4 + х 2 |
+ 1. |
|
|
|
|
Кодовый |
многочлен |
F(x) |
получают сложением остат |
ка R(x) с |
x5G(x) |
|
|
|
|
|
F(x) |
= х 1 5 - I - х11 |
-|- х 9 |
+ хв + х 5 |
+ |
х 4 |
+ x 2 - j - 1, |
Отсюда передаваемая в канал связи комбинация цик лического 17-элементного кода будет иметь вид
010001011001 |
10101 |
информационные |
проверочные |
элементы |
элементы |
Под влиянием помех в канале принятая последова тельность элементов может отличаться от переданной, т. е. кодовый многочлен F(x) преобразуется в многочлен Н(х). Так как многочлены складываются по модулю 2, то Н(х) можно представить как сумму двух многочле нов:
|
|
|
H(x) |
= F(x) |
+ E{x), |
|
|
|
(6.32) |
где Е(х) |
— |
многочлен |
ошибок, |
содержащий |
столько |
членов, сколько элементов в |
принимаемой |
комбинации |
не совпадает с переданной. |
|
|
|
|
|
|
Пусть |
в |
переданной |
кодовой |
|
комбинации |
01000101100110101 |
F(x)=xis |
+ xu+x* + x*+x5 |
+ xl |
+ |
x2+] |
искажен |
седьмой |
элемент |
и |
она |
принята, |
как |
01000111100110101 |
Н(х)=\х15 |
+ хг* + х * ° + х 9 + х8 + х 5 |
+ х 4 + |
+ х 2 + 1 . |
Нетрудно |
видеть, что комбинацию |
Н(х) |
мож |
но рассматривать |
как сумму |
по модулю |
2 |
комбинаций: |
^01000101100110101
^00000010000000000
01000111100110101
F{x)=x1&+xn+ |
|
x9+xs+x5+x4+x2 |
+ l |
®£(*) = |
х10 |
|
|
Н{х)=х1Ь+х11-fx1"+х°+х8+х5 |
-4-х4 |
+ х 2 + 1 |
Основным критерием наличия в принимаемом сооб
щении |
Н(х) |
ошибки является его неделимость без |
ос |
татка |
на образующий многочлен Р(х). |
Если Н(х) |
де |
лится |
на Р(х), |
то принятое сообщение |
рассматривается |
как правильное, даже если и произошла ошибка (случай
необнаруженной ошибки). Так как |
H(x)=f(x)+E(x), |
то |
неделимость |
И(х) |
на Р(х) |
определяется . тем, |
что |
Е(х) |
не делится |
на |
Р(х). |
|
|
|
|
Корректирующая |
способность |
циклического |
кода |
полностью определяется видом образующего многочлена Р(х). Поэтому правильный выбор образующего много члена является основной задачей, решаемой при пост
роении циклического |
кода. |
|
|
|
Рассмотрим некоторые основные свойства цикличе |
ских кодов. |
|
|
|
|
|
Свойство |
1. Циклический код, образующий |
многочлен |
которого |
Р(х) |
содержит больше |
одного члена, обнару |
живает все одиночные ошибки. |
|
|
|
При |
одиночной |
ошибке в !-м разряде |
многочлен |
ошибки |
будет иметь вид Е(х)—х1 |
и для |
обнаружения |
ошибки |
не должен |
делиться без |
остатка |
на |
Р(х). Оче |
видно, что А"' не делится без остатка на многочлен, со держащий более одного члена. Простейшим таким мно гочленом является (х+\).
Свойство 2. Циклический код, образованный много членом Р(х)=х+1, обнаруживает не только одиночные ошибки, но и любое нечетное число ошибок.
Для обнаружения ошибок при образующем много члене Р(х) = х+\ кодовый многочлен F(x) должен де литься на Р(х) без остатка, т. е.
|
F(x) |
= (x+l)Q(x) |
= |
xQ{x)+Q(x). |
|
|
|
Если |
Q(x) |
содержит |
пг членов, |
то |
xQ(x) |
также |
со |
держит m членов. Из общего числа |
Ъп |
членов |
в |
Q(x) |
и |
xQ(x) nil |
пара |
членов, имеющих |
одинаковые |
степени, |
при суммировании по модулю 2 дадут нули. Тогда в
функции F(x) |
останется |
2(m—т,) |
членов, т. е. |
четное |
число. Отсюда |
следует, |
что кодовый многочлен |
любой |
комбинации циклического кода, образованного много членом Р(х)=х+1 содержит четное число членов.
При нечетном числе ошибок многочлен ошибок Е(х) будет содержать нечетное число членов и, следователь но, не будет делиться на Р(х).
Свойство 3. Циклический код, образованный много членом Р(х), обнаруживает все одиночные и двойные ошибки, если значность «ода л меньше или равна сте
пени / двучлена |
х1+1, |
где |
/ — наименьшее |
число, |
при |
котором х'+ |
\ делится |
на |
Р(х) |
без |
остатка. |
|
|
|
|
Для обнаружения двойных ошибок необходимо, что |
бы |
многочлен |
ошибок |
Е(х) |
=x{ |
+ xj |
не делился |
на |
Р(х) |
при |
любом |
I, |
j<n. |
|
'Полагая |
i<j, |
преобразуем |
|
Е(х): |
|
|
|
|
|
|
|
Е{х) = |
|
|
х1(\+х^). |
|
|
|
|
|
Так |
как |
|
— i ) <n^Zl, |
то |
xi_i+\ |
|
не |
делится |
на |
Р(х) |
и, |
следовательно, |
код |
обнаруживает |
все |
|
двойные |
ошибки. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
•Все одиночные ошибки обнаруживаются согласно до |
казанному |
выше, так |
как |
Р(х) |
имеет больше, |
чем один |
член. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Согласно табл. 6.2 число проверочных разрядов си |
стематического (п, /?)-кода, |
обнаруживающего |
двойные |
ошибки |
(d = 3), |
определяется |
из |
выражения |
|
2т^п+1. |
Очевидно, что наибольшая экономичность кода |
обеспечи |
вается при п = 2г—1. |
Поэтому при построении циклических |
кодов |
значительный |
интерес |
представляют |
|
значения |
/=*2Г —1. В этом случае существует, по крайней мере,
один многочлен |
Р(х) |
степени |
г, |
на |
который |
двучлен |
\+х'-~~' |
делится |
без |
остатка. |
|
|
|
|
Таким образом, можно утверждать, что для любого г |
существует циклический код |
длиной |
п=2г—1, |
образо |
ванный многочленом |
Р(х) |
степени г, который обнаружи |
вает все |
одиночные и двойные |
ошибки. |
|
В общем случае двучлен вида |
х 2 _ 1 |
+ 1 является наи |
меньшим |
общим |
кратным |
для |
всех |
неприводимых') |
многочленов степени |
г. |
|
|
|
|
|
В табл. 6.11 приведены все неприводимые многочле ны до шестой степени включительно и некоторые много
|
|
|
|
|
|
|
|
члены от седьмой до десятой степени. |
|
|
|
Свойство |
4. Циклический |
код, |
образованный |
много |
членом вида Р(х)=\(х+,\)Р,(х), |
|
позволяет |
обнаружить |
все одиночные, двойные и тройные ошибки, если |
степень |
г' неприводимого |
многочлена Р'(х) |
такова, |
что |
двучлен |
2Г —1 будет |
больше или 'равен числу |
элеметов |
кода п. |
') Неприводимым |
называется |
многочлен, |
делящийся без остат |
ка только на единицу |
и на себя. |
|
|
|
|
|
Т А Б Л И Ц А 6.11
Вид неприводимого многочлена
Х+1
х*+х+\
х3+хг+ 1 х*+х+\
xi |
+ x+ 1 |
|
.v''+.v3 +l |
|
х^+хл+х-+х+\ |
х5+х2+1 |
|
х*+х3+\ |
|
х5+х3+х2 |
+ х+\ |
х5 |
+ х'' + |
х-+х+\ |
х5 |
+ |
х'' + х3 |
+ х+ 1 |
Х 5 + А - 4 + Х 3 |
+ А - 2 + 1 |
А - 6 + Х 3 + 1 |
|
xe |
+ |
xs+\ |
|
xe + xi+xz |
+ x+ 1 |
х 6 + . с 1 + д:3 + х + I |
хв+х5 |
+ хг |
+ х+ 1 |
А - 6 + А 5 + А - 3 |
+ А-2 + 1 |
А 6 |
+ А - 5 + А 4 + Х - Н |
А"6 |
+ А - 5 + А - 4 + А 2 + 1 |
А 7 |
+ А - ° + 1 |
ха |
+ х*+х3 + х°-+\ |
А-8 +А-° + А 5 + А''+ 1
А-9 + А 4 + 1 А-° + А - 5 + 1
А-1 0 + А 3 + 1
А^ + А " 1 - ! - !
П=1=2Г— I
1
3
7
15
31
63
127
255
511
1023
Справедливость данного следствия вытекает из пре дыдущего. Сомножитель (х+\) обнаруживает одиноч ные и тройные ошибки, а Р (х) — двойные.
Рассматриваемый циклический код позволяет также обнаружить ,все кодовые комбинации, в которых имеются две пары двойных смежных ошибок. Многочлен ошибок такого .вида равен:
|
Е (х) = х1 + x i + l + х1 + x i + l . |
|
(6.33) |
После преобразований получим Е(х) =-(x+\)i(xi |
+ |
xi). |
Этот многочлен |
не делится на Р(х) — (х+ |
1)Р'(х) |
без |
остатка, так |
как х^ + х1 ие делится на Р'(х), |
что |
было |
показано при рассмотрении свойства 3. |
|
|
|
Свойство |
5. |
Циклический код,, образованный |
много |
членом степени г, обнаруживает любой пакет ошибок длиной г и менее ' ) .
Пакету |
ошибок |
длиной г |
соответствует |
многочлен |
ошибок |
вида |
Е(х) |
— х*+ ... |
+ . . . - f x ' |
при |
/—1 = |
=т—'1. |
Вынося |
за скобку х1, |
получим |
|
|
|
|
|
|
|
|
£ ( * ) = * ' ( / - ' + . . . + |
1). |
|
|
(6.34) |
Поскольку степень многочлена, стоящего в скобках, |
меньше г, то многочлен Е(х) |
не делится на образующий |
многочлен |
Р(х), |
степень |
которого т, что и |
|
обеспечивает |
обнаружение |
пакетов ошибок |
длиной |
т и |
менее. |
|
Оценим, чему равна часть необнаруживаемых паке |
тов ошибок, если длина |
пакета 6 =•/"+• 1. |
|
|
|
Многочлен |
ошибок, |
соответствующий |
данному слу |
чаю, имеет вид |
|
|
|
|
|
|
|
|
|
|
|
|
Е(х) |
= х'(хГ + |
... 4- 1). |
|
|
|
|
Деление Е(х) |
на Р(х) |
без остатка |
возможно |
только, |
если Е(х) |
—xiP(x). |
|
В о всех остальных |
случаях в |
резуль |
тате деления получится остаток степени ."(,г—1), количе ство вариантов которого в зависимости от вида много члена ошибок не превышает 2Г —4. Таким образом, ко личество пакетов ошибок длиной ( r + l ) , необнаружи ваемых циклическим кодом, составляет 1/2г~! часть всех
пакетов длиной |
( i r + 4 ) . |
что Ь>г+Л. |
|
|
Теперь предположим, |
Для |
пакета оши |
бок длиной b |
многочлен |
ошибок |
имеет |
вид Е(х) = |
') Пакетом ошибок длиной b будем называть группу из b еди ничных элементов, начинающуюся и кончающуюся ошибочными еди ничными элементами, в которой число правильных единичных эле ментов, разделяющих два соседних ошибочных единичных элемента, всегда меньше данного числа Ь.