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

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

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

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

.

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

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

. (7.3)

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

Доказательство:Пусть, где. Тогда

.

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

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

,

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

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

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

Следовательно, если , то.

Теорема 7.2.1.Любой кодовый полиномциклического кодаделится без остатка на порождающий многочленэтого кода, т.е.

Доказательство:Предположим противное, т.е. что существует некоторый кодовый многочлен, который представим в виде

,

где остаток от деленияна.

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

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

, (7.4)

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

,

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

соответствует числу проверочных символов.

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

Теорема 7.2.2.Порождающий многочленциклического кодадлиныобязательно делит бином.

Доказательство:Из леммы 7.2.2 следует, что вычет из произведенияпо модулюявляется кодовым полиномом. Учитывая, что, то

,

и значит, как кодовый полином, делится без остатка на . Следовательно, иделится на.

Пример 7.2.1.Для двоичных кодов длиныв качестве порождающих многочленов могут выступать только сомножители биномаЛегко убедиться, что

,

где все множители – неприводимые над многочлены. Следовательно, порождающимикод многочленами могут быть либо множители приведенного бинома, либо их произведение. Отсюда, возможными парами чисел, т.е. возможным числом информационных и проверочных символов, могут быть следующие: (6,1), (4,3), (3,4) и (1,6).

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

Следовательно,

. (7.5)

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

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

Доказательство:Согласно (7.4), любой кодовый полином циклического кода может быть представлен как

,

где – информационный полином степени не выше, а– порождающий многочлен, у которого. Тогда

,

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

Пример 7.2.2.Выбрав в примере 7.2.1 в качестве порождающего многочлена

,

в соответствии с (7.5) находим, что проверочным является многочлен вида

.