Определение циклического кода. Порождающий полином

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

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

Линейный блоковый код длины называется циклическим, если наряду с любым своим кодовым словом он содержит также циклический сдвиг этого слова. Иными словами, циклический код содержит все циклические сдвиги всех своих кодовых слов.

Лемма 3.2.1.

Пусть некоторому слову циклического кода сопоставлен полином . Тогда его циклическому сдвигу будет соответствовать полином , являющийся вычетом полинома по модулю бинома , т.е. .

Доказательство:

Добавим и вычтем в соотношении для и сгруппируем его слагаемые следующим образом

.

Откуда непосредственно следует утверждение леммы 3.2.1.

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

. (**)

Лемма 3.2.2.

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

Доказательство:

Пусть , где . Тогда

.

Отсюда на основании леммы 3.2.1, ясно, что каждое слагаемое последнего выражения является кодовым полиномом, отвечающим некоторому циклическому сдвигу исходного слова . Учитывая же свойства линейного подпространства, т.е. тот факт, что умножение на скаляр и сложение кодовых слов вновь дают кодовое слово, следует, что вычет по модулю также соответствует кодовому слову.

Следствие.

Если степень полинома удовлетворяет неравенству

,

то само произведение отвечает полиному некоторого слова циклического кода.

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

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