ЦИКЛИЧЕСКИЕ КОДЫ

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

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

Вектор сообщения можно записать следующим образов:

                        (1)

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

                   (2)

При делении на  получим:

                                       (3)

где  - остаток, записанный в виде:

                          (4)

Данный остаток также можно записать следующим образом:

                                          (5)

Если прибавить  к уравнению (3), а затем использовать сложение по модулю 2, то получим:

                                    (6)

Данное кодовое слово можно записать через члены полинома:

.(7)

А полином кодового слова будет соответствовать вектору кода

                              (8)

где  - бит четности - , а  - бит сообщения - .

Алгебраическое описание циклического кода дается следующей теоремой.

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

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

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

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

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

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

Рассмотрим код, порожденный многочленом . Существует ровно 24 различных многочленов степени меньше 4, которые при умножении на многочлен  дают многочлен степени меньше 7. Перепишем эти многочлены: и соответственно, циклический код, порожденный многочленом есть код  = {0000000, 0001101, 0011010, 0010111, 0110100, 0111001, 0101110, 0100011, 1101000, 1100101, 1110010, 1111111, 1011100, 1010001, 1000110, 1001011}.

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

Таким образом, многочлен  степени , который является делителем многочлена , порождает циклический -код. В порождающую матрицу этого кода можно записать векторы, соответствующие классам  [3].

Пример: Действительно, код, рассмотренный в предыдущем примере, имеет базисные векторы 0001101, 0011010, 0110100, 1101000, соответствующие классам вычетов , т. е. имеет размерность 4. Порождающая матрица имеет вид:

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

Пример: Для циклического (7,4)-кода, порожденного многочленом  . Порождающая матрица для кода, порожденного многочленом , имеет вид:+

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

Список литературы:

1.Вернер М. Основы кодирования. Учебник для ВУЗов. — М.: Техносфера, 2004. – 288 с.

2.Виснадул Б.Д. Основы компьютерных сетей. — М.: Форум: Инфра - М, 2007. – 272 с.

3.Таненбаум Э. Компьютерные сети. Учебное пособие. 4-е изд. — СПб.: Питер, 2003. – 992 с.: ил.