Циклические коды. Необходимое и достаточное условие цикличности.

Циклический код является частным случаем линейного кода, когда любая циклически сдвинутая кодовая комбинация является также кодовой комбинацией. Непосредственная проверка выполнения этого условия для линейных кодов представляющих практический интерес неосуществима, т.к. велика мощность кода: , где - основание кода, - число информационных символов (). К циклическому коду можно прийти как к частному случаю другого кода – полиномиального. Полиномиальный код задается наиболее просто образующим многочленом , степени , - длина кодовой комбинации. Множество многочленов степени меньшей делящихся на является множеством кодовых комбинаций. Полиномиальный код это тот же линейный код только иначе представленный. Вместо -символьных последовательностей (векторов) их многочленная запись по формальной измененной . Формальная переменная используется по сути для указания номера позиции в -разрядной комбинации, где имеется ненулевой символ. В пользу перехода к многочленному представлению можно указать по крайней мере три аргумента:

- при в среднем на 50% «экономится» длина записи;

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

- упрощается процедура кодирования, вместо матричного умножения, умножение (или деление) многочленов.

Найдем необходимые и достаточные условия цикличности полиномиального кода. Пусть - кодовый вектор, его многочленная запись . Циклически сдвинутый вектор , его многочленная запись .

Очевидно: . (*)

- должен быть кодовым многочленом, т.е. делящимся на , это левая часть выражения (*). Первое слагаемое справа также делится на , т.к. а(х) – кодовый многочлен по условию. Значит обязано делиться на второе слагаемое, чтобы был кодовым. Показано тем самым чтобы полиномиальный код был циклическим необходима делимость двучлена на образующий многочлен . Достаточность следует также из (*): если () делится на , то и правая часть (*) делится на , т.е. - кодовый многочлен.

Отсюда следует, что задавая код в качестве можно брать только делители двучлена . Циклические коды существуют для любого . Сколько различных кодов длины может быть задано зависит от значения , иначе от многообразия множителей (простых), на которые разлагаются . При знак «-» и знак «+» эквивалентны. Два кода находятся предельно просто, т.к. из школьного курса известна формула для суммы членов геометрической прогрессии со знаменателем х.

, т.е.

Первый код - это код с проверкой на четность, второй код - это код с повторением.

Для задания циклических кодов надо уметь разлагать на простые множители двучлены .

Рассмотрим пример. Пусть нас интересуют коды длины . Разложение: получается методом проб (в общем случае есть специальная методика разложения). Из разложения следует (см. таблицу):

(n,k)	g(x)	Комментарии
(7,6)	x+1	Код с проверкой на четность
(7,5)	-	Не существует, т.к. нет g(x) второй степени
(7,4)		Код Хэмминга
(7,4)		Аналогичен по характеристикам предыдущему
(7,3)		Одинаковы по характеристикам
(7,3)
(7,2)	-	Не существует
(7,1)		Код с повторением