Б4. Аналогия между циклическими и линейными кодами

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

Порядок а равен

Возьмем элементов мультипликативной группы поля:

и образуем многочлен

Тогда

Действительно, все различны и являются корнями в силу

Так как не может иметь более корней, то все его корни

Многочлен называется дополнительным для

Для кольца многочленов над можно рассмотреть фактор-множество Это множество имеет структуру кольца, но не будет полем, так как многочлен не является неприводимым.

Каждый элемент фактор-кольца представляется многочленом степени не больше :

или -выборкой из элементов

Заметим, что

или

Поэтому, если соответствует -выборка то соответствует выборка -выборка и т. д. В частности, если

— примитивный многочлен степени то имеем (по модулю

Векторы, компоненты которых совпадают с коэффициентами многочленов из определяют -мерное подпространство пространства .

Заменим последовательность многочленов (Б4.11) матрицей :

Ее ранг равен Подпространство, порожденное векторами-строками циклическое в том смысле, что если оно содержит вектор то оно содержит также

Пусть — дополнительный многочлен для

Тогда имеем

и матрица

аналогично определяет -мерное подпространство пространства Если изменить порядок столбцов в матрице

то, как легко проверить, получаем соотношение

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

Примеры. 1) Покажем, что циклический код, построенный с помощью многочлена

над фактически совпадает с кодом Хэмминга (3,4). Имеем

Построим матрицу для

Она приводится к канонической форме, если к первой строке прибавить третью, затем к новой первой строке прибавить четвертую, а затем ко второй прибавить четвертую:

Аналогично для имеем

или

получается из если поменять местами первую и третью строки и затем прибавить к третьей строке первую.

Очевидно, что представляют собой матрицы линейного кода Хэмминга:

и

2) Мы попытаемся определить вид многочленов, которые при построении по ним линейного кода позволяют обнаружить:

а) простую ошибку,

б) нечетное число ошибок,

в) две ошибки,

г) три ошибки.

Заметим, что если передаваемое слово определяется многочленом а принимаемое — многочленом то

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

определяется двоичной последовательностью

при передаче которой 2-й, 4-й и 6-й символы изменяются:

то многочлен

представляется в виде

и полином ошибок равен

Поэтому для выявления ошибки данного типа необходимо, чтобы не делился на так как, по определению, многочлены, соответствующие кодовым словам, делятся на

а) Если ошибка простая, то имеет вид

В качестве достаточно взять полином, не делящий никакой одночлен например

б) Многочлен вида можно записать в виде

Очевидно, что

Следовательно, если многочлен соответствующий кодовому слову, делится на

то

Каждый такой обладает четным числом ненулевых коэффициентов, и любое нечетное число ошибок можно обнаружить.

в) В случае двух ошибок полином ошибок можно записать в виде

или

Тогда достаточно в качестве взять примитивный многочлен степени Действительно, этот многочлен

будучи примитивным, не может делить многочлен при

г) Наконец, для обнаружения трех ошибок нужно взять многочлен вида

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