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

0001 -> 1000->0100->0010->0001 (right)

0001->0010->0100->1000->0001(left)

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

Циклические коды являются разновидностью систематических кодов.

[pic 1]

[pic 2]

Пример.  Сложить два полинома  и [pic 3][pic 4]

[pic 5]

(x^3+x^2+x)⊕ (x^3+x^2+x)

Результат: [pic 6]

Пример.  Умножить полином  на  полином  [pic 7][pic 8]

[pic 9]

Результат:

.[pic 10]

Пример. Разделить полином  на  полином  . [pic 11][pic 12]

[pic 13]

Результат:  [pic 14]

Если комбинации , то циклический сдвиг так же приводят к разрешенной комбинации.[pic 15]

[pic 16]

Циклическая перестановка соответствует умножению на .[pic 17]

1. [pic 18]
2. [pic 19]

В первом члене нужно заменить  на 1.[pic 20]

1. [pic 21]

Полученный полином является циклическим сдвигом комбинации .[pic 22]

Принцип построения циклических кодов

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

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

На такой многочлен делится без остатка двучлен .[pic 23]

Неприводимые многочлены в теории циклических кодов играют роль образующих полиномов.

Чтобы понять принцип построения циклического кода, умножаем комбинацию простого  кода  на одночлен , а затем делим на образующий полином , степень которого равна . В результате умножения  на  степень каждого одночлена, входящего в , повышается на k. [pic 24][pic 25][pic 26][pic 27][pic 28][pic 29][pic 30][pic 31]

При делении произведения   на образующий полином получается частное  такой же степени, как и .[pic 32][pic 33][pic 34]

Результат умножения и деления можно представить как

[pic 35]

где  – остаток от деления  на .[pic 36][pic 37][pic 38]

Частное  имеет такую же степень‚ как и кодовая комбинация   простого кода‚ поэтому   является кодовой комбинацией этого же-простого  кода.[pic 39][pic 40][pic 41][pic 42]

Следует заметить, что степень остатка не может быть больше степени образующего полинома, т. е. его наивысшая степень может быть равна . Следовательно, наибольшее число разрядов остатка  не превышает числа .[pic 43][pic 44][pic 45]

Пример. Дано  и образующий полином третьей степени . Следовательно, кодовые комбинации циклического кода будут иметь по семь разрядов. Требуется записать произвольную кодовую комбинацию циклического кода (7,4) первым способом. Возьмем произвольную четырех-разрядную комбинацию , то есть .[pic 46][pic 47][pic 48][pic 49]

Найдем произведение

 . [pic 50]

(0111 000)

 [pic 51]

Произведем деление:

[pic 52]

Следовательно, остаток .[pic 53]

Комбинация, принадлежащая циклическому (7,4) коду:   или в двоичной форме: .[pic 54][pic 55]