1 Основные сведения о циклических кодах

1.1 Определение и основные свойства циклических кодов

Важнейшим недостатком СБЛК, как отмечалось выше, является высокая трудоемкость их построения при длине кодовой последовательности n≥31 двоичный символ и коррекции ошибок кратностью t_ош≥3 двоичных символа. Поиск более простых принципов построения СБЛК привел к открытию нового широкого класса групповых линейных блоковых кодов, получивших название циклических кодов (ЦК). Основоположником ЦК является Прейндж [1]. Дальнейшее развитие теория построения ЦК получила в работах Боуза, Чоудхури, Хоквингейма, Файра, Рида-Соломона, Гоппы и др.

Циклические коды являются подклассом в классе линейных блоковых кодов, удовлетворяющих определенным требованиям. Свое название данные коды получили по причине того, что основной операцией построения кодовых последовательностей (F_i(x)) является цикл, а точнее циклическая перестановка двоичных символов разрешенных кодовых последовательностей [1,2].

В соответствии с [1,2,3] циклическим кодом называется линейный блоковый код, который представляет собой конечное множество, замкнутое относительно операции циклического сдвига кодовых последовательностей, образующих данный код. С математической точки зрения ЦК является идеалом в линейной коммутативной алгебре многочлена (полинома) n-го порядка по модулю двучлена xⁿ-1 над полем коэффициентов. Это означает, что кодовые последовательности ЦК имеют длину “n” двоичных кодовых символов и описываются полиномами степени (n-1), в которых коэффициентами при соответствующих степенях формальной переменной, обозначаемой через “x”, являются двоичные символы кодовой последовательности. Формальная переменная “x”, которая носит название оператора Хаффмана или оператора задержки и не оказывает никакого влияния на свойства кода. Таким образом, кодовую последовательность ЦК в общем виде можно записать так:

F_i(x)=c_n-1⋅x^n-1+ c_n-2⋅x^n-2 +…+c₁⋅x¹+ c₀⋅x⁰,

где x – форменная переменная,

n-1, n-2 ,…, 1, 0 – показатели степеней, в которые возводятся основания кодов, и одновременно порядковые номера, которые занимают двоичные символы (разряды) кодовой последовательности, начиная со старшего и заканчивая нулевым;

c_i – коэффициенты формальной переменной, которые могут принимать или быть равными логической 1 (ненулевой член F_i(x)) или логического 0 (нулевой член F_i(x)).

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

ЦК относятся к групповым линейным кодам, если они образуются путем умножения каждой последовательности равнодоступного (простого) кода, выраженных в виде многочлена Q(x) с максимальной степенью (k-1), на некоторой полином P(x) степени l=n-k. Приведение подобных членов производится по модулю два; порядок поля кодирования преобразуется с K_раз=2^k до K_общ=2ⁿ, но число разрешенных кодовых последовательностей кода при этом остается равным K_раз=2^k, и они образуют циклическую подгруппу группы K_общ=2ⁿ, отличающуюся тем, что все элементы подгруппы имеют общее свойство делимости на полином P(x), получивший название образующего или порождающего полинома.

В соответствии с [1,2,3] в качестве образующего полинома P(x) используются полиномы, обладающие следующими свойствами:

• во-первых, образующий полином P(x) должен быть делителем двучлена x_n+1;

• во-вторых, образующий полином не должен раскладываться на сомножители более низких степеней, и делиться без остатка на самого себя и на 1, т.е. на x₀;

• в-третьих, максимальная степень образующего полинома должна быть равной l=n-k, т.е. соответствовать количеству проверочных символов используемого кода.

В соответствии с [9] к основным свойствам ЦК относятся:

1. Вес (w_к.п.) разрешенной кодовой последовательности ≥ d₀.

2. Вес проверочной части w_пр.ч. разрешенной кодовой последовательности ≥ d_0-1.

3. Сдвиг кодовых символов разрешенной кодовой последовательности влево или вправо на один, два,…, (k-1) символ вновь приводит к разрешенной кодовой последовательности.

4. Разрешенная кодовая последовательность без ошибок F_р'(x) при делении на полином P(x) дает нулевой остаток, т.е. F_р'(x)/P(x)=R(x)=0 и R(x) не равно 0 – при наличии ошибок;

5. Сумма по модулю два символов двух, трех,…, (k-1) разрешенных кодовых последовательностей вновь образует разрешенную кодовую последовательность.

6. Двучлен вида xⁿ+1 должен делиться на порождающий полином P(x) без остатка (имеется в виду обычная операция деления многочленов).

7. Если все операции над полиномами (кодовыми последовательностями) проводятся в двоичном поле Галуа (GF(2)), т.е. действия над коэффициентами полиномов осуществляется по модулю два, а умножение полиномов производится по модулю образующего полинома P(x), то применение указанных операций не приводит к кодовым последовательностям, длина которых больше длины заданного кода, т.е. “n”.

8. Результат деления двучлена xⁿ+1 на образующий полином P(x) дает полином, который носит название проверочного полинома и обозначается как h(x), т.е. h(x)=(xⁿ+1)/P(x) и который в теории и практике помехоустойчивого кодирования играет важную роль. Произведение h(x)⋅P(x)=xⁿ+1=0, а потому многочлены h(x) и P(x) рассматривается как ортогональные и операция деления (xⁿ+1)/P(x) используется в основе построения алгоритмов декодирования.

9. Двучлен ЦК вида xⁿ-1 можно разложить на множители

xⁿ-1=(x-1)(x^n-1+ x^n-2+…+1),

которые можно использовать в качестве образующих полиномов ЦК с n=const, k=var и d₀=var.

Известно [2,3,4,5], что корректирующая способность групповых СБЛК существенно зависит от вида (структуры) образующего полинома, т.е. от количества ненулевых членов данного полинома и его максимальной степени l=n-k. В соответствии с этим можно отметить следующие свойства ЦК:

1. обнаруживающих ошибки:

• ЦК, образующий полином которого имеет более одного члена и не имеет общего множителя “x”, обнаруживает все одиночные ошибки и любое нечетное число ошибок. Простейшим образующим полиномом ЦК, обладающими данными свойствами, является полином вида P(x)=1+x;

• ЦК, образующий полином которого имеет вид P(x)=1+x^c, обнаруживает любое нечетное число ошибок. Доказательство этого утверждения становится ясным, если образующий полином представить в следующем виде:

P(x)=1+x^c=(1+x)⋅(1+x+x²+…+x^c-1).

2. обнаруживающих и корректирующих ошибки:

ввиду того, что полином P(x)=1+x^c нацело делится на 1+x, то согласно предыдущему свойству ЦК обеспечивает обнаружение любого нечетного количества ошибок;

• ЦК, образующий полином которого имеет максимальную степень l=n-k, обнаруживает любой пакет ошибок длиной t_{пак.обн.}=l и менее двоичных символов или корректирует пакеты ошибок длиной t_{пак.исп}=l/2 двоичных символов;

• количество пакетов длиной l+1, не обнаруживаемых ЦК, составляет 1/2^l-1 части всех пакетов (l+1) двоичных символов. Количество пакетов ошибок длиной более l+1, не обнаруживаемых ЦК, составляет часть всех пакетов ошибок длиной от (l+2) до “n” двоичных символов включительно.