Помехоустойчивые циклические коды. Никитин Г.И. - 7 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

7
1.3. Порождающие полиномы циклических кодов
Формирование разрешённых кодовых комбинаций ЦК B
i
(X) основано на пред-
варительном выборе так называемого порождающего (образующего) полинома G(X),
который обладает важным отличительным признаком: все комбинации B
i
(X) делятся
на порождающий полином G(X) без остатка, т. е.
),)X(R()X(A
)X(G
)X(B
i
i
0==
остаткепри
(4.1)
где А
i
(Х) — информативный полином (кодовая комбинация первичного кода, преоб-
разуемого в корректирующий ЦК).
Поскольку, как отмечалось выше, ЦК относятся к классу блочных разделимых ко-
дов, у которых при общем числе символов n число информационных символов в А
i
(Х)
равно k, то степень порождающего полинома определяет число проверочных симво-
лов r = n - k.
Из этого свойства следует сравнительно простой способ формирования разре-
шённых кодовых комбинаций ЦК — умножение комбинаций информационного кода
А
i
(Х) на порождающий полином G(X):
B
i
(X) = A
i
(X)·G(X). (4.2)
В теории циклических кодов доказывается, что порождающими могут быть толь-
ко такие полиномы, которые являются делителями двучлена (бинома) X
n
+1:
).)X(R()X(H
)X(G
X
n
0
1
==
+
остаткепри (4.3)
Возможные порождающие полиномы, найденные с помощью ЭВМ, све-
дены в обширные таблицы. Так, в [6] приведены таблицы G(X) с записью полино-
мов в восьмеричной системе счисления (mod 8). В этом случае весовые коэффи-
циенты k
i
представляют три двоичных знака в соответствии со следующим кодом:
111 - 7 101 - 5 011 - 3 001 - 1
110 - 6 100 -4 010 - 2 000 - 0
(4.4)
Двоичные символы являются весовыми коэффициентами порождающих
полиномов, коэффициенты восьмеричной системы счисления расположены слева
от них с учётом того, что 0 ≤ k
i
≤ 7 (при mod 8). Например, 3425 обозначает много-
член 10-й степени, В двоичной записи числу 3425 (mod 8) эквивалентно число
011100010101 и соответствующий многочлен равен X
10
+ X
9
+ X
8
+ X
4
+ X
2
+ 1. Как
видно из этого примера, восьмеричная система счисления для записи многочле-
нов выбрана, в частности, из соображений экономии длины записи (бумаги) в три
раза при больших объёмах табулированных значений, что подчёркивает извест-
ный недостаток двоичной системы счисления.
Некоторые из порождающих полиномов приведены в табл. 1.
Следует отметить, что с увеличением максимальной степени порождающих
полиномов r резко увеличивается их количество. Так, при r = 3 имеется всего два
полинома, а при r = 10 их уже несколько десятков.
Первый порождающий полином минимальной степени r=1, удовлетворяющий
условию (4.3), формирует код с проверкой на чётность при двух информативных
символах и одном проверочном, обеспечивающем обнаружение однократной
ошибки, поскольку минимальное кодовое расстояние d
min
= 2. В общем случае ко-
эффициент избыточности КПЧ минимален:
,
nn
r 1
==κ (4.5)
а относительная скорость кода – максимальна и равна

Страницы