7.2. ОПРЕДЕЛЕНИЕ ЦИКЛИЧЕСКОГО КОДА

Код называется циклическим, если он линеен и любой циклический сдвиг кодового слова также является кодовым словом, т. е. если принадлежит то и принадлежит Например, код Хэмминга (1.40) является циклическим. Цикличен также код

Для того чтобы дать алгебраическое описание, сопоставим каждому вектору из некоторое конечное поле многочлен Например, коду соответствуют многочлены

Будем использовать следующее обозначение; если поле, то множество многочленов от с коэффициентами из Множество является кольцом.

Определение. Кольцо (в широком смысле) определяется как множество, в котором возможны сложение, вычитание и умножение. Формально аддитивная абелева группа с умножением, удовлетворяющим условиям: которая содержит единичный элемент 1 такой, что (Такое кольцо иногда называется коммутативным кольцом с единицей.)

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

Умножение на х соответствует циклическому сдвигу. Умножая в многочлен на х, получаем:

так как в имеет место равенство Но этому многочлену соответствует вектор Таким образом, в умножение на соответствует циклическому сдвигу!

Идеалы. Определение. Идеалом кольца называется линейное подпространство такое, что: (i). Если то для всех Условие очевидно, может быть заменено на условие:

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

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

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

Групповая алгебра Часто полезно другое описание кольца Пусть циклическая группа порядка Групповая алгебра группы над полем (см. § 3 гл. 5) состоит из всех формальных сумм вида

Сложение в выполняется покоординатно, а умножение — по модулю многочлена Ясно, что совпадает с

Упражнения. (1). Каким идеалом описывается циклический код

(2). Описать наименьший циклический код, содержащий вектор 0011010.

(3). Показать, что не является полем. [Указание. Элемент не имеет мультипликативного обратного.]

(4). Показать, что многочлен имеет мультипликативный обратный в тогда и только тогда, когда взаимно прост с в кольце

(5). Показать, что в циклическом -коде любые последовательных символов могут быть выбраны в качестве информационных.