6.2. Определение циклического кода

Среди многообразия групповых кодов особое место занимают циклические (n,k) - коды. Циклические коды отличаются простотой реализации, возможностью построения кода любой длины с известными корректирующими свойствами, рациональным соотношением между избыточностью и корректирующей способностью (в этом отношении они близки к границе Хэмминга).

Определение 1. Циклическим кодом называют, групповой (n, k) – код, обладающий следующим свойством: для любой кодовой комбинации этого кода комбинация, полученная циклическим сдвигом элементовна единицу вправо, также принадлежит этому коду.

Описание циклических кодов основывается на представлении кодовых комбинаций в виде многочленов от одной неизвестной с коэффициентами в виде двоичных элементов 0 и 1, т.е. элементов поля GF(2).Используя такое представление, можно дать следующее, эквивалентное приведенному выше, определение циклического кода.

Определение 2. Циклическим (n, k) – кодом называется код, множество кодовых комбинаций которого представляется совокупностью многочленов степени n-1 и менее, делящихся на некоторый многочлен g(x) степени (n-k) , являющийся сомножителем двучлена .

Доказательство эквивалентности этих двух определений основывающееся на представлении циклического кода как идеала кольца классов вычетов многочленов по модулю двучлена .(см. свойства 3 и 4 кольца). Групповая структура циклических кодов определяется тем, что, во-первых, операция сложения многочленов совпадает с операцией сложения векторов, во-вторых, совокупность многочленов, делящихся на некоторый многочленg(x), должна быть замкнута в отношении операции сложения, т.к., если каждое из слагаемых делится наg(x), то их сумма делится наg(x)и степень суммы не старше степеней слагаемых, в-третьих, нулевая комбинация принадлежит циклическому коду, т.к.0делится без остатка наg(x).

Структура циклического кода не будет раскрыта полностью, если не учитывать, что свойство цикличности эквивалентно заданию действия умножения над кодовыми комбинациями как над многочленами и замкнутости кодовых комбинаций по этому действию. Для обеспечения замкнутости кодовых комбинаций в пределах множества многочленов степени n-1 и менее умножение кодовых комбинаций необходимо производить по модулю двучлена. Из определения 2 следует, что к циклическому коду относятся лишь многочлены степениn-1 и менее, кратные многочлену g(x). Структура циклического кода формируется в результате следующих построений. Бесконечное множество многочленов произвольных степеней путем вычисления остатков от деления на(приведения по модулю) раскладывается на конечное число множеств, обладающих одинаковым остатком, называемых классами вычетов.

При этом каждый многочлен степени от нулевой до (n-1)-ой включительно принадлежит своему определенному классу вычетов и полностью его представляет. Классы вычетов при таком разложении играют ту же роль, что и смежные классы в разложении группы по подгруппе. В данном случае роль подгруппы играет класс вычетов, содержащий все многочлены, кратные, т.е.и т.д. Общее число классов вычетов равно числу всевозможных многочленов степениn-1 и менее, т.е. 2ⁿ.

Разложение бесконечного множества многочленов на классы вычетов по модулю единственно и каждый класс вычетов однозначно определяется любым многочленом, принадлежащим данному классу. Это относится и к первому классу вычетов, содержащему 0 и, который по отношению к остальным классам вычетов рассматривается как единичный элемент, т.е.. (Аналогично тому, как при сложении по модулю 2 принимается 2=0). Полное множество классов вычетов рассматривается как множество всех комбинаций длиныnих представляющих. В качестве кодовых комбинаций рассматриваются те классы вычетов, которые содержат многочлены, кратныеg(x), и совокупность всех многочленов, кратныхg(x), как было показано выше, в свою очередь образует подгруппу (идеал) множества всех классов вычетов многочленов по модулю. Следовательно, классы вычетов многочленов в свою очередь могут быть разложены на смежные классы по подгруппе, образующей циклический код. Так как 0 принадлежит к этой подгруппе, то по отношению ко всем смежным классам разложения классов вычетов по подгруппе, образующей код, справедливо, гдепроизвольный многочлен кольца классов вычетов многочленов по модулю.Нетрудно показать, что g(x) должен быть делителем .

Действительно, поскольку по определению g(x) имеет степень, меньшую, чемn, то можно записать результат делениянаg(x)в виде следующего равенства

, где

- остаток от деления, степень которого меньше степени g(x), аq(x)- частное от деления. Учитывая, что, получаем, а так как мы установили выше, что, то и, т.е. g(x)делитбез остатка. Значит,g(x) – сомножитель двучлена.

Многочлен g(x) принято называть порождающим или образующим многочленом циклического кода.С другой стороны циклический (n, k) – код может быть задан через двойственный(n, n-k)– код, порожденный многочленом Так как ,то ортогонален g(x) и называется проверочным многочленом.

Пример 6.3. Дано .

Найти все циклические (n, k) – коды сn = 7, которые могут быть построены на основе данного разложения. Определим все сомножители, которые и будут являться порождающими многочленами искомых кодов. Возможные сомножителии соответствующие им коды перечислены в следующей таблице.

Сомножитель	Код
	(7,6)
	(7,4)
	(7,4)
	(7,3)
	(7,3)
	(7,1)

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

Однако не любой сомножитель порождает циклический (n, k) – код с требуемыми корректирующими свойствами. Методика выбора порождающего многочлена для построения циклического кода с заданными корректирующими свойствами будет рассмотрена ниже.