5.4.3. Полиномиальные циклические коды

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

Например,  порождает множество полиномов вида

т.е. код (7, 4, 3).

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

На практике используется другой способ получения полиномов  по информационному полиному  и порождающему полиному  [25, 33]:

,

(5.15)

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

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

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

Пусть кодовое слово  получено из  путем циклического сдвига символов влево, а самый левый символ переведен на освободившееся место на правом конце. Если  имеет в качестве левого символа 0, то циклический сдвиг эквивалентен только умножению  на : . Очевидно, если  делится на , то и  также делится на .

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

Ясно, что для делимости  на  необходимо, чтобы многочлен  также делился на  (сложение и вычитание здесь эквивалентны).

В табл. 5.5 приведено разложение полинома  над  на неприводимые многочлены для значений . Более обширные сведения заинтересованный читатель сможет найти в [30]. Таблица позволяет выбирать порождающие полиномы  в зависимости от числа  символов в коде и  информационных символов, поскольку степень  равна .

Любой делитель полинома  или любое произведение делителей может быть взято в качестве порождающего полинома хода. Например, при   и  порождают код (15,11,3) – код Хэмминга с кодовым расстоянием ; код (15,7,5) порождается полиномом ; код (15,5,7) – полиномом ; код (15,4,8) – полиномом  и т.д.

Для  разложение имеет вид: , что определяет лишь два типа кодов этих длин.

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

2. Коды  нечетной длины с повторением, , .

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

Неприводимые полиномы, являющиеся примитивными, подчеркнуты в табл. 5.5.

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

Таблица 5.5. Разложение полинома  на делители

	Делители полинома
7
9
15
17
21
23
25
27
31

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

.

(5.16)

Любая другая комбинация кода может быть получена как взвешенная (с весами  от источника сообщений) сумма строк порождающей матрицы:

.

соответствует произведению матриц

.

Так, для двоичного кода (7, 4, 3) порождающая матрица имеет вид:

.

Очевидна связь между порождающим полиномом  и строками матрицы . Избыточные символы  первой строки в соответствии с (5.15) есть остаток от деления -символьной комбинации 100 ... 0 на , второй –остаток от деления комбинаций 010 ... 0 и т.д.

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

,

где    – символ транспонирования. Эквивалентное уравнение имеет вид:

.

Для двоичного кода (7, 4, 3)

.

(5.17)

Кодирование с помощью проверочной матрицы производится на основе уравнений:

или , ,

где    – элемент -й строки и -го столбца матрицы .

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

Вопросы организации кодеров и декодеров в зависимости от структуры полиномов  и , а также матриц  и  достаточно подробно рассмотрены в монографиях [3, 26]. Однако при больших длинах используемых кодов подобные методы декодирования реализуются слишком громоздко. Кроме того, мажоритарные или пороговые декодеры, основывающиеся на анализе системы оценок каждого символа принятой комбинации, имеют тот недостаток, что необходимую систему оценок удается составить не для всех кодов.

Дальнейшим развитием теории и практики помехоустойчивого приема сигналов являются алгебраические методы декодирования, использующие понятие корней полиномов, соответствующих кодовым комбинациям. Алгебраические процедуры эффективны, в частности, при декодировании кодов БЧХ.