Циклические коды

Лекция 14. Циклические коды.

Непрерывные коды.

Из непрерывных кодов, исправляющих ошибки, наиболее известны коды Финка-Хагельбаргера, в которых контрольные символы образуются путем линейной операции над двумя или более информационными символами. Принцип построения этих кодов рассмотрим на примере простейшего цепного кода. Контрольные символы в цепном коде формируются путем суммирования символов, расположенных один относительно другого на определенном расстоянии:

e_ik=c_i+c_k; e_i+1, _k+1=c_i+1+c_{k+1; …}

Расстояние между информационными символами l=k-i определяет основные свойства кодов и называется шагом сложения. Число контрольных символов при таком способе кодирования равно числу информационных символов, поэтому избыточность кода æ=0,5. Важное преимущество непрерывных кодов состоит в их способности исправлять не только одиночные ошибки, но и группы ошибок. Если задержка контрольных символов выбрана равной 2l, то можно показать, что максимальная длина исправляемого пакета ошибок также равна 2l при интервале между пакетами 6l+1. Таким образом, возможность исправления длинных пакетов связана с увеличением шага сложения l, а следовательно, и с усложнением кодирующих и декодирующих устройств.

Цель лекции: ознакомление cциклическими кодами

Содержание:

а) циклические коды;

б) свойства символического умножения;

в) требования, предъявляемые к образующему многочлену;

г) выбор образующего многочлена по заданному объему кода и заданной корректирующей способности;

д) обнаружение одиночных ошибок (d=2);

е) исправление одиночных или обнаружение двойных ошибок (d=3).

Любой групповой код вида (n,k) может быть записан в виде матрицы, включающий k линейно независимых строк по n символов и наоборот.

Среди различных кодов можно выделить также коды, у которых все КК могут быть получены циклическим сдвигом 1-й КК которая называется образующей. Такие коды получили название циклических.

Сдвиг осуществляется справа налево, причем крайний левый символ каждый раз переносится в конец КК.

Исх. КК 001011

Матрица КК

При построении т.о. ЦК оказывается количества КК значение меньше чем количество КК в групповом коде. Как найти общее свойство и обеспечить необходимое количество КК?

При описании ЦК КК можно представить в виде многочленов некоторой переменной х. Показатели степени у переменной х соответствуют NN разрядам (начиная с нулевого), а коэффициентами при х, в общем случае, являются элементы поля GF(q). Поэтому для двоичного ЦК коэффициентами могут быть 0 или 1.

Так, например: КК 001011 –

или.

Наибольшая степень х в слагаемом с ненулевым коэффициентом называется степенью многочлена.

Циклический сдвиг многочлена без переноса “1” в конец КК можно получить простым умножением на х исходной КК:

* х

Если эти КК (001011 и 010110) сложить по m2, то результат сложения будет соответствовать умножению g(x) на (х+1):

001011

Å => х +1,

010110

011101 Å

.

Циклический сдвиг строки матрицы с “1” в старшем разряде равносилен умножению соответствующего многочлена на х c одновременным вычитанием из результата многочлена, т.е. с приведением по m2 ().

Т.о. любая разрешенная КК ЦК могла быть получена в результате умножения g(x) на некоторый другой многочлен с приведением результата по m(), т.е. при соответственном выборе g(x).

1) Любой многочлен ЦК (разрешенная КК) будет делится на него без остатка.

2) Ни один многочлен, соответствующий запрещенной КК на g(x) без остатка не делится, т.е. при делении на g(x) образует остатки.

Это свойство позволяет обнаружить ошибку. По виду остатка можно определить вектор ошибки.

Свойства символического умножения.

1) Многочлен перемножается по обычным правилам, но с приведением подобных членов по m2.

2) Если старшая степень произведения не превышает n-1 то это произведение является результатом символического умножения.

3) Если старшая степень произведения n, то многочлен произведения делится на заранее определенный многочлен степени n и результатом символического умножения считается остаток от деления.

Степень остатка n-1, следовательно этот многочлен принадлежит к множеству n – разрядных КК.

Заранее выбранный элемент многочлен -> (),

Требования, предъявляемые к образующему многочлену.

Согласно определению ЦК все многочлены, соответственно его КК должны делится на g(x) без остатка.

Для этого достаточно, чтобы на g(x) делились без остатка многочлены составляющие образующую матрицу ЦК.

Эти многочлены получаются циклическим сдвигом, что соответствует последнему умножению g(x) на х, с приведением по модулю.

Следовательно, в общем случае многочлен g (x) является остатком от деления производной на многочлен () и может быть записан так:

Т.о. образующий многочлен должен быть делением многочлена ()

т.е входить в разложение многочлена (). С другой стороны при делении g (x) на образующий многочлен g(x) при ошибочном приеме должен образовываться остаток. По виду остатка происходит локализация ошибок и их исправление.

Следовательно, корректирующая способность ЦК будет тем выше, чем больше остатков образует g(x).

Привлекая аналогию из простых чисел, можно сказать, что наибольшее число остатков = может образовывать только неприводимый (простой) многочлен.

Неприводимый многочлен -> аналог простого числа (- делится только на 1 и на самого себя).

Т.о. 2 свойство образующего многочлена:

- делитель многочлена ();

- неприводимость в поле GF(2), где определена операция суммы по m2.

Число 25 - > сложное в поле десятичных чисел.

- 1101 – неприводимый в поле GF2

Å

101

Å

101

10 - остаток