= xi(хь~1 + . . . + i l ) • Поскольку b-~[>r, |
то |
многочлен |
ошибок может делиться без остатка на Р(х). |
Возможное |
число вариантов многочленов ошибок равно 2Ь—2. При и> делении на образующий многочлен получается 2Г ос татков и только один из них будет нулевым. - П р и 1 количество необнаруживаемых пакетов ошибок состав ляет 1/2г часть от общего числа пакетов.
Основной задачей, решаемой при построении цикли
ческих |
кодов, является |
выбор образующего многочлена, |
исходя |
из |
требуемых |
корректирующих свойств |
кода. |
Для кодов, обнаруживающих двойные ошибки |
( d = 3 ) , |
степень |
образующего многочлена |
г и значность |
кода а |
выбираются |
из условия |
п = 2г—1. |
Лри этом в качестве |
образующего многочлена может быть выбран любой из
|
|
|
|
|
|
|
|
неприводимых многочленов степени |
г |
(см. табл. |
6.10). |
Так, при /-=3 можно построить 'циклический |
код |
(7,4); |
при г—А — код (15,11); при г = 5 — код (63,58). |
|
При |
построении |
'кодов, обнаруживающих |
одиночные, |
двойные |
и тройные |
ошибки ( r f = 4 ) , |
берется образующий |
многочлен вида Р(х) = ' ( х + 1 )Р'(х), |
Где Р'(х) |
— |
обра |
зующий многочлен степени г' для кода с d=3. |
Длина |
кодовой комбинации выбирается из условия |
п = 2 г — 1 ; |
число |
проверочных |
разрядов равно: г = |
г'+\. |
|
|
В |
качестве примера, поясняющего выбор |
образующего |
много |
члена и формирование проверочных элементов, рассмотрим построе ние циклического кода с d = 3 для передачи одиниадцатиэлементпых
|
|
|
|
|
|
|
|
|
|
комбинаций |
(К=Ы). |
При этом число |
проверочных |
разрядов |
г = 4. |
Образующий |
многочлен |
такого (15, '11)-кода может быть |
любым |
из |
трех |
неприводимых |
многочленов |
четвертой степени, например, |
Р(х) |
= х'1+х+\, |
или в двоичной форме 10011. |
|
|
|
Строками порождающей матрицы циклического (п, £)-кода яв |
ляются |
соответственно |
образующие |
многочлены |
Р(х); |
хР(х); |
х2Р(х); |
...; х''-1Р(х), |
дополненные слева |
нулями. Поэтому |
порож |
дающая |
матрица искомого кода будет |
иметь вид |
|
|
|
|
|
|
|
00010011010111I |
|
|
|
|
|
|
|
_ 001001101011110 |
|
|
|
|
|
0 |
5 , 4 ) |
010011010111100 |
|
|
|
|
|
|
|
100110101111000 |
|
|
Нетрудно видеть, что все исходные кодовые комбинации раз личны, имеют вес d и благодаря циклическому сдвигу линейнонеза-
висимы. Кодовое расстояние между любыми парами кодовых комби наций также не меньше d. Остальные разрешенные кодовые комби
нации могут быть получены суммированием по модулю 2 любых со четаний исходных комбинаций.
Проверочная |
матрица |
Ип, п-ь. циклического |
(п, |
£)-кода строит- |
ся ма |
основе |
|
многочлена |
h(x), |
полученного |
делением |
двухчлена |
|
на образующий |
многочлен |
Р(х): |
|
|
|
|
|
Последовательность |
многочленов |
h(x); |
xh(x); |
x2h(x), |
.... |
хп~''~* |
h(x) |
является |
строками |
матрицы |
М размерностью |
(п, |
n—k). |
Первая строка представляет собой многочлен h(x) |
с приписанными |
слева |
(г—1) |
нулями. Остальные |
строки |
получаются |
в результате ци |
клического |
сдвига |
первой. Для |
рассматриваемого примера получим |
|
= |
х |
Л 4 " , ' , = х П + х° + * 7 + *6 + х 3 + х2 |
+ х + 1, |
|
|
|
|
+ х + 1 |
|
|
|
|
|
|
|
или в двоичной |
форме |
100П0.101ФШ, откуда |
|
|
|
|
|
|
|
|
|
|
|
000100110101111 |
|
|
|
|
|
|
|
|
|
|
|
001001101011110 |
|
|
|
|
|
|
|
|
М ( 1 5 , 4 ) |
= |
010011010111100 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
100110101111000 |
|
|
|
|
Цикличность перестановок, определяющая строение рассматри ваемых кодов, а также изложенный выше способ построения комби
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
наций |
циклических кодов |
путем |
деления |
многочлена |
исходной ко |
довой |
комбинации на образующий |
многочлен с приписыванием |
остат |
ка значительно облегчают построение |
кодирующих и декодирующих |
устройств, |
основой которых |
являются |
регистры сдвига |
с |
обратны |
ми связями. |
|
|
|
|
|
|
|
|
|
|
|
|
|
iB [66] рассматривается |
и другой |
способ задания |
цик |
лических |
(п, к)-кодов, |
основанный |
на представлении об |
разующего |
многочлена |
Р(х) |
в |
виде |
произведения |
нес |
кольких |
многочленов |
и нахождении |
Р(х) |
по |
заданным |
значениям |
его корней. |
|
доказывается, что если F(x) — |
В |
теории кодирования |
многочлен |
циклического |
(п, |
/г)-кода и F.(x) |
для некото |
рого значения а равна нулю, то многочлен F(x) |
делится |
на т(х), |
если т(х) |
— неприводимый многочлен мини |
мальной степени и |
т(а)=0. |
|
|
|
|
|
|
|
|
•Пусть |
|
а\\ ач\ |
|
ат |
— корни многочлена |
Р(х), |
все |
различны <и каждый |
из них является |
корнем |
минималь |
ных |
многочленов |
т\(х)\ |
|
лго(х); |
...; |
|
тт(х). |
Тогда |
неко |
торый многочлен |
F(x) |
будет принадлежать циклическо |
му (п, 6)-коду, если |
а,; о2 ; |
|
ат—будут |
его корнями. |
Многочлен F(x) |
в |
силу |
определения |
циклического |
кода должен делиться на каждый из минимальных |
мно |
гочленов, |
|
а следовательно, |
и на их наименьшее |
общее |
кратное НОКТак как многочлен, |
на который |
делится |
любая кодовая комбинация, является образующим мнО' гочленом кода, то
Р (х) = НОК [ту(*), т, {х), .... тт (х)\. |
(6.35) |
Для рассмотренного выше примера минимальный многочлен для а есть т(х)=х* + х+\. Следовательно, в данном случае
Р (х) = т {х) = х* -|- х + 1.
Циклические коды, задаваемые с помощью корней образующего многочлена, получили название кодов Боуза — Чоудхури 1 ) . Ими доказано, что если среди кор
|
|
|
|
|
|
|
|
|
|
|
ней |
образующего |
многочлена циклического (п, |
к)-кода |
имеются |
элементы |
степени |
/?г0; т0+\\ |
ш 0 |
+ 2; |
т0 |
+ |
+ d+Q, |
то |
минимальное |
расстояние этого |
кода |
будет |
не |
менее d. |
|
|
|
|
|
|
|
|
|
Задание |
кодов |
с помощью корней образующего мно |
гочлена |
позволяет |
легко |
определить |
его |
корректирую |
щие свойства. |
|
|
|
|
|
|
|
|
Определение корректирующих свойств |
циклических |
(а, |
к)-кодов |
сводится |
к |
установлению |
максимальных |
значений кратности гарантийно исправляемых или об наруживаемых ошибок или, что то же, к определению
|
|
|
|
|
|
|
|
|
минимального |
кодового расстояния |
d. |
|
|
Свойство |
6. |
Для любых значений |
/ и |
/ существует |
циклический |
код |
длины п =2'—1, |
|
исправляющий все |
ошибки кратности |
/ и менее |
и содержащий не более |
/' = // проверочных |
элементов. |
|
|
|
|
Потребуем, чтобы циклический код длины /г=15 ис |
правлял все |
двойные |
ошибки |
{1=2). |
|
Определим /. Так |
как 15 = 2 4 — 1 , то 1 = 4. |
Тогда |
г=8. |
Таким образом, в ис |
комом коде |
15 элементов, из |
которых |
7 — информацион |
ных и 8 — проверочных. Минимальное кодовое расстоя |
ние такого кода d = |
5. |
|
|
|
|
|
Свойство 6 определяет лишь существование кодов с |
известными |
корректирующими свойствами. |
Нахождение |
кодов, действительно обладающих этими свойствами, за висит от правильного выбора образующего многочлена.
Чтобы найти вид образующего многочлена, обеспечи
вающего d = 5 при |
п=15, г = 8, воспользуемся табл. 6.12, |
') Р. К. Б о у з, Д . |
К- Ч о у д х у р и . Об |
одном классе двоичных |
групповых кодов с исправлением ошибок. |
«Кибернетический сбор |
ник», вып. 2. М., ИЛ, |
1961. |
|
|
|
|
Т А |
Б Л И Ц А |
6.12 |
|
|
|
|
|
ВИД минимальных многочленов для |
|
1 |
1-2 |
f=3 |
г = 4 |
Z=5 |
/=6 |
1<=7 |
/=8 |
1 |
х*+ |
х3+ |
|
Х Б + Х 2 + 1 |
|
xi+x3+l |
х8+х*+ |
|
|
+х+\ |
|
|
|
|
+х*+х+ |
|
|
|
|
|
|
|
- И |
3 |
— |
— |
л - 4 - Ь г 3 Ч - |
х*>+х* + |
|
+х*+х+ |
Л-8 +А-5 -г- |
|
|
|
+х*+х+ |
+ д - 3 + |
+ 1 |
|
|
|
|
+ 1 |
+Д'2 +1 |
+ 1 |
+ 1 |
5 |
— |
— |
— |
xb+xt+ |
|
|
|
|
+х*+х+ |
+х*+х-\- |
+х3~\- |
|
|
|
|
|
|
|
|
|
|
|
+ 1 |
+* 3 + 1 |
|
7 |
— |
— |
— |
— |
х*+х3+\ |
х7+хЧ- |
|
|
|
|
|
|
в которой приведены минимальные многочлены до вось мой степени включительно.
Образующий многочлен находим из выражения
|
|
|
|
Р(х) = |
H O K [ m 1 ( x ) m 3 ( x ) . . . m i ( x ) ] , |
|
|
(6.36) |
где |
i=d—2. |
|
|
|
|
|
|
|
|
|
|
|
Так |
как в рассматриваемом |
коде 1 = 4, a i — d—2 = 3, |
то |
из |
третьей |
колонки |
табл. |
6.12 |
находим: |
т\(х) = |
= х 4 |
+ х + 1; т3(х) |
= х 4 |
+ х 3 |
+ х 2 + х + 1. Отсюда |
|
|
Р (х) = т |
х |
(х) /п (х) - |
(** |
f х + |
1) (** + |
х |
3 |
+ х |
2 |
+ х + 1), |
|
|
|
|
3 |
|
|
|
|
|
|
|
|
или |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Р (х) = X8 |
+ X7 + |
Х° + X1 + 1. |
|
|
|
|
|
|
К о д ы , к о р р е к т и р у ю щ и е п а к е т ы о ш и б о к . |
Выше |
(свойство |
5) |
были |
рассмотрены |
|
условия, |
при ко |
торых циклический |
(я, Л)-код обнаруживает |
пакеты оши |
бок длиной Ь. Рассуждая |
аналогичным |
образом, |
нетруд |
но определить нижнюю границу числа проверочных эле ментов группового (я, &)-кода, исправляющего пакеты ошибок длиной Ь. Обозначим через С число различных сочетаний ошибок в л-элементной комбинации, которые необходимо исправить. Тогда число проверочных элемен тов искомого кода г = п-—к должно быть таково, чтобы обеспечивалось неравенство 2 г ^ С + ' 1 .
