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

Циклические коды являются разновидностью систематических кодов. Они получили широкое распространение из-за простоты кодирования и декодирования. Все разрешённые кодовые комбинации производящей матрицы могут быть получены циклическим сдвигом одной разрешённой комбинации, называемой образующей для данного кода.

Любой -разрядный код можно представить в виде полинома степени

,

где - основание счисления,

- коэффициенты, принимающие значения «0» или «1», если.

Например, комбинацию 110101 можно записать как

.

Циклический сдвиг эквивалентен умножению многочлена на.

Действительно,

.

Но в кодовой комбинации должно быть всего членов, причём степень полинома не должна превышать. Чтобы удовлетворить этому условию, положим. Тогда получим

,

т.е. получили циклический сдвиг. Если код, выраженный в виде полинома, принадлежит разрешённой кодовой комбинации, то кодовая комбинация, полученная циклическим сдвигом, также принадлежит разрешённой кодовой комбинации. Из условия того, что имеем

. (5.16)

Пусть имеется полином степени. Среди полиномоввыделим полиномы, которые делятся только лишь на самого себя и на 1. Такие полиномы называются простыми или неприводимыми.

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

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

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

Каноническая форма производящей матрицы размерности(5.10) состоит из зеркального отражения единичной подматрицы размерности, ( матрица отражения [Марпл]), и проверочной подматрицы размерности.

. (5.23)

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

Пример 5.5. Пустьn= 7,k= 4,r= 3. Первоначальное значение производящей матрицы имеет вид

Выберем образующий полином

Таблица 5.6
Номер строки	1	2	3	4
Код остатка	011	110	111	101

, который дает 7 остатков при делении кода ошибки на образующий полином. Разделим коды строк производящей матрицына код образующего полинома. В результате имеем четыре остатка, значения которых приведены в таблице 5.6. После замены нулей в проверочной части матрицы соответствующими кодами остатков получим каноническую форму производящей матрицы

.

Полученная производящая матрица состоит из четырёх строк (кодов). Все остальные =11 кодов, кроме кода 0000000, могут быть получены линейной комбинацией строк производящей матрицы.