Алгебраическая структура и свойства циклических кодов

// Материалы Международной научно - технической конференции «Вторые ержановские чтения». – Актобе. – 2007. – С.508-512.

УДК 681.3.07

алгебраическая структура  и свойства циклических кодов

Евразийский национальный университет им. , г. Астана

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

, полученный i – кратном  циклическом сдвиге, является кодовым словом в S. Этот код легко реализуется на регистре сдвига длины  n с обратной связью, на подобных регистрах сдвига с обратной связью вычисляется синдром, а алгебраическая структура циклического кода естественным образом позволяет эффективно реализовать методы декодирования.

Регистр сдвига в начальном состоянии

…

Регистр сдвига на такте 3

…

Рисунок 1 – Регистр сдвига с обратной связью

Компоненты кодового слова можно рассматривать как коэффициенты многочлена U(X):

.  (1)

Функцию U(X) можно рассматривать как «заполнитель» разрядов кодо­вого слова U, т. е. вектор n – кортежа описывается многочленом степени n – 1 или меньше. Наличие или отсутствие каких-либо членов в многочлене означает наличие 1 или 0 в соот­ветствующем месте n-кортежа. Если –й компонент отличен от нуля, тогда порядок многочлена равен  n – 1.

Алгебраическая структура циклических кодов.

В кодовых словах, выраженных в форме многочлена, циклическая природа кода проявляется следующим образом, т. е. при необходимости можно переходить от векторного представления кодового слова к представлению в виде многочлена и наоборот. Пусть имеется кодовое слово U(X), представлен­ное многочленом порядка (n – 1), тогда Ui(X) –  остаток от деления XiU(X) на – также является кодовым словом.  Другими словами,

,  (2)

умножая обе части уравнения на получим,

,  (3)

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

по модулю  .  (4)

Здесь «х по модулю у» означает остаток от деления х на у. Справедливость формулы (4) покажем для случая i = 1.

.  (5)

К выражению (5) прибавим и вычтем . А поскольку мы пользуемся арифметическими операциями по модулю 2, можем дважды прибавить .

.  (6)

Многочлен    не  делится  на  ,  так  как порядок многочлена равен n – 1. Таким обра­зом, используя уравнение (2), можно записать следующее:

по модулю  .  (7)

Обобщая, приходим к уравнению (4) [1, 2].

Циклический сдвиг вектора кода.

Пусть для п = 4 кодовое слово U = 1101. Выполним третий циклический сдвиг кодового слова, используя уравнение (4), и выразим кодовое слово в форме многочлена.

       Запишем полином в порядке возрастания степени U(X) = 1 + X + X 3.        

Умножим Xi U(X) = X 3U(X) = X 3 + X 4 + X 6,  где  i = 3. Используя деление многочленов,  разделим  X3U(X)  на  X4 + 1  и  найдем остаток.  Остаток равен  X 3 + X 2 + 1. Запишем остаток в порядке возрастания степеней 1 + X 2 + X 3, тогда кодовое слово U (3) =1011 представляет собой три циклических сдвига U = 1101.

Свойства двоичного циклического кода.

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

,  (8)

где g0 и gp должны быть равны 1.

Теорема 1. В каждом циклическом коде существует единственный, отличный от нуля, кодовый многочлен g(X) минимальной степени  p = n – k.

Доказательство. Пусть существуют два многочлена минимальной степени g(X) и отличных от нуля. Из свойства замкнутости линейного векторного кодового пространства следует, что их сумма является кодовым многочленом. Отсюда получаем

Таким образом, приходим к противоречию.

       Теорема 2. Если g(X) – кодовый многочлен наименьшей степени  p, то его коэффициент g0 = 1.

Доказательство. Сдвинем многочлен g(X)  n – 1 раз. Получим многочлен

.  (9)

Этот многочлен также принадлежит коду. А по определению его степень не может быть меньше p, поэтому  g0 = 1.

Каждый многочлен кодового слова в подпростран­стве имеет вид U(X) = m(X) g(X), где U(X) - многочлен степени п - 1 или меньше. Тогда, многочлен сообщения m(X) будет иметь следующий вид:

.  (10)

       Теорема 3. Пусть g(X) – многочлен минимальной степени  p. Тогда, чтобы U(X) является кодовым многочленом необходимо и достаточно, чтобы он был кратен  g(X).

Доказательство. Докажем достаточность. Пусть U(X) = m(X) g(X). Тогда

.  (11)

Так как степень многочлена g(X) не превосходит p, а степень многочлена m(X) не превосходит  n – 1 – p, произведение  m(X) g(X) не содержит членов степени, большей  n – 1, то  Xi g(X) можно рассматривать как  i – кратный сдвиг многочлена g(X). Таким образом

.  (12)

Так как любой циклический сдвиг g(X) также является кодовым многочленом, то  U(X) представляет собой линейную комбинацию кодовых слов, т. е. является кодовым словом.

       Необходимость. Пусть

,  (13)

где p(X) – возможный остаток от деления U(X) на g(X). Решим это уравнение относительно p(X)

.  (14)

Правая часть (14) представляет собой сумму двух кодовых многочленов, следовательно, и p(X) является кодовым многочленом. Так как по определению степень p(X) меньше степени минимального многочлена g(X), многочлену  p(X) соответствует нулевое кодовое слово.

       Для поиска  порождающих многочленов важным является следующее утверждение:

Теорема 4. Порождающий многочлен g(X) циклического кода (n, k) делит без остатка.

Доказательство. Умножим g(X) на  Xk, тогда получим многочлен степени  n = k  + p.  Этот же результат можно получить, если к циклическому сдвигу gk(X) прибавить для устранения лишней  «1»  при  X0  и компенсации недостаточной компоненты  Xn. Получаем

.  (15)

Представим (15) как результат деления на

,  (16)

где является остатком. Так как циклический сдвиг сам является кодовым многочленом, то согласно теореме 3, существует такой многочлен  m(X), что

.  (17)

Подставим (17) в (16) и переставляя слагаемые, получим

.  (18)

Таким образом, g(X) делит без остатка.

       Вывод: U будет считаться действительным кодовым словом из подпространства S тогда и только тогда, когда U(X) делится на g(X) без остатка.

       Справедливо обратное утверждение.

       Теорема 5. Если некоторый многочлен g(X)  степени  n – k  делит  без остатка, то g(X) порождает некоторый циклический (n, k) – код.

Доказательство. Вначале докажем, что всевозможные произведения g(X) на многочлены, степень которых не превышает  k  – 1, образуют некоторый линейный (n, k) – код и что этот код является циклическим.

  Все произведения  g(X)  на  многочлен,  степень  которого  не превышает  k  – 1, запишем в следующем виде

.  (19)

В соответствии (19), всем возможным наборам двоичных коэффициентов от m0  до mk-1 соответствует различных кодовых слов. Полученный код является линейным, так как сумма двух любых кодовых слов также принадлежит коду.

       Теперь покажем, что этот код является циклическим.

       Рассмотрим произведение

 

.  (20)

Из (20) следует, что для многочлена  , соответствующего сдвигу U(X), справедливо

.  (21)

Так как g(X) делит U(X) и , он также является делителем . Таким образом, циклический сдвиг любого кодового слова также принадлежит коду.

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

СПИСОК ЛИТЕРАТУРЫ

ифровая связь. Теоретические основы и практическое применение. Изд. 2-е, испр.: Пер. с англ. – Издательский дом «Вильямс», 2004. – 1104 с. ил. сновы кодирования. Москва: Техносфера, 2004. – 288 с. , , Мощицкий информации (двоичные коды). Харьков, издательское объединение «Вища школа», 1978, 252 с.