50. Циклический код. Основные сведения. Построение циклического кода.
Множество кодовых комбинаций называется циклическим кодом, если циклический сдвиг любой комбинации на любое число разрядов влево или вправо дает комбинацию из этого же множества. Циклический код является частным видом группового кода. Он обладает всеми свойствами, присущими групповому коду. Кроме того, имеет дополнительную особенность − цикличность. Кодовая комбинация β разделимого циклического кода представляется в виде блока длины n = m+ k ,
При
описании циклических кодов наиболее
удобной является запись дво-ичной
комбинации циклического кода β
в виде многочлена
β(х)
некоторой фиктивной переменной х.
Двоичная комбинация m-разрядного
первичного кода записывается аналогично
в виде информационного
многочлена m(x).
В
теории циклического кодирования над
полиномами и соответствующими им
комбинациями вводятся операции сложения,
умножения
и
деления.
Операция
умножения
(деления)
многочленов
включает
их перемножение (деление) по обычным
правилам с дальнейшим приведением
подобных членов по модулю 2. Например,
Построение циклического кода основано на использовании так называемого образующего или порождающего полинома р(х). Он должен быть неприводимым многочленом, т.е. делиться только сам на себя и на единицу. Образующий полином выбирается в разложении двучлена xn +1 на неприводимые многочлены [8, 9]. Старшая степень р(х) определяется числом контрольных символов k.
называется
проверочным.
Его высшая степень совпадает с числом
информационных разрядов m первичного
кода. Кодовые комбинации циклического
кода помимо общих для групповых
кодов свойств удовлетворяют двум условиям: 1) без остатка делятся на образующий полином, т.е.β(x) = 0 по модулю р(х) (2.3)
многочлены
β(х) и h(x) перемножаются по обычным
правилам с приведении ем подобных по
модулю 2. Если старшая степень полученного
произведения не превышает (n-1), то оно
является результатом умножения по
модулю(xn +1). В противном случае результат
умножения делится на двучлен xn +1 и
получившийся при этом оостаток является
результатом умножения по модулю (xn +1).
На названных выше двух свойствах основано
обнаружение и исправление ошибок при
передаче циклического кода по каналу
связи. Эти же свойства лежат в основе
его построения и технической реализации
кодирующих устройств. Циклический
сдвиг кодовой
комбинации β
на i шагов влево (вправо)
Построение
циклического кода.
Прежде чем строить циклический код,
нужно знать его параметры m, d, k и n=m+k
(см.п.2.7). Тогда построение кода по сути
дела сводится к выбору образующего
полинома p(x). Образующий полином следует
искать по таблице разложения двучлена
xn +1 на неприводимые сомножители (см.
[8,9]). Полином р(х) должен удовлетворять
двум
условиям:1)
степень
полинома равна k;
2)
число
ненулевых членов ≥
d . Если в разложении двучлена xn +1 нет
требующегося полинома, то до-
пускается выбор в качестве образующего полинома произведения двух или более неприводимых многочленов этого разложения. При этом, естественно, должны выполняться два выше названных условия. Однако такой выбор дает код с меньшей мощностью кодовых ккомбинаций. Выбранный полином необходимо проверить на соответствие требуемой корректирующей способности. С этой целью единица с нулями делится на образующий полином. Полученные остатки должны удовлетворять трем требованиям: 1) число различных остатков ≥ m; 2) число единиц каждого остатка (его вес) ≥ d −1; 3) остатки должны отличаться друг от друга в числе разрядов ≥ d − 2 . При выполнении этих требований полином р(х) обеспечивает построение (n,m) циклического кода с кодовым расстоянием d. Если в расположении двучлена xn +1 не удается найти многочлен степени k и длины ≥ d , то прибегают к построению укороченного циклического кода. Допустим, что m=3, d=3, k=3 и n=6. В разложении двучлена
Строим
образующую матрицу кода (n1, m1 ) , где m1=
n1- k . В нашем случае n1 = 7 , m1 = 7 − 3 = 4 и
матрица кода (7,4) найдена в примере 1. В
полученной матрице вычеркиваем n1- n −
первых строки столько же столб цов
слева. В итоге получим образующую матрицу
укороченного циклического кода (6,3):
В ряде случаев может получиться, что образующий полином имеет степень k и число членов ≥ d , но его применение не обеспечивает заданной корректирующей способности, т.е. при делении 1000… на р(х) не получаются требуемые остатки. В этом случае необходимо повышать степень k(увеличивать число контрольных символов) до тех пор, пока не будет достигнута заданная корректирующая способность.