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



Скачать 85.46 Kb.
Дата08.11.2012
Размер85.46 Kb.
ТипДокументы
// Материалы Международной научно- технической конференции «Вторые ержановские чтения». – Актобе. – 2007. – С.508-512.

УДК 681.3.07

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

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

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

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


















gif" name="object10" align=absmiddle width=37 height=21>



Регистр сдвига на такте 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 = nk.
Доказательство. Пусть существуют два многочлена минимальной степени 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) – кода.

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


  1. Скляр Б. Цифровая связь. Теоретические основы и практическое применение. Изд. 2-е, испр.: Пер. с англ. – Издательский дом «Вильямс», 2004. – 1104 с. ил.

  2. Вернер М. Основы кодирования. Москва: Техносфера, 2004. – 288 с.

  3. Березюк Н.Т., Андрущенко А.Г., Мощицкий С.С. Кодирование информации (двоичные коды). Харьков, издательское объединение «Вища школа», 1978, 252 с.

Похожие:

Н. Н. Ташатов алгебраическая структура и свойства циклических кодов iconОпределение циклических кодов
Определение циклических кодов. Линейный код называют циклическим, если для любого кодового слова [xn xn-1] циклическая перестановка...
Н. Н. Ташатов алгебраическая структура и свойства циклических кодов iconФрактальные вычисления
В основе фрактальных вычислений лежит алгебраическая структура фрактоид. Целенаправленное изменение размерности фрактоида, позволяет...
Н. Н. Ташатов алгебраическая структура и свойства циклических кодов iconЕ. В. Головко Контактные языки Лекции
Переключение кодов в сопоставлении с другими контактными явлениями. Смешение кодов. Социолингвистические особенности использования...
Н. Н. Ташатов алгебраическая структура и свойства циклических кодов iconПринцип построения циклических кодов
Код, в котором кодовая комбинация, полученная путем циклического сдвига разрешенной кодовой комбинации является также разрешенной...
Н. Н. Ташатов алгебраическая структура и свойства циклических кодов iconАлгебраическая структура и модель вычислений для арифметики ограниченных целых неотрицательных чисел

Н. Н. Ташатов алгебраическая структура и свойства циклических кодов iconПрограмма спецкурса " Коды и схемы "
...
Н. Н. Ташатов алгебраическая структура и свойства циклических кодов iconРешение любой задачи, помеченной (*) автоматический зачет по курсу
Практическое знакомство с методами генерации помехозащищенных кодов. Кодов обнаружения ошибок и кодов исправления ошибок
Н. Н. Ташатов алгебраическая структура и свойства циклических кодов iconБилет №13 Логические величины, операции, выражения. Логические выражения в качестве условий в ветвящихся и циклических алгоритмах
Для того чтобы понять работу ветвящихся и циклических алгоритмов, рассмотрим понятие логического выражения
Н. Н. Ташатов алгебраическая структура и свойства циклических кодов iconДата 14. 10. 2009 Класс 8с Учитель Алескерова И. Г
«Алгебраическая дробь и ее свойства. Сложение и вычитание алгебраических дробей», закрепить вычислительные навыки
Н. Н. Ташатов алгебраическая структура и свойства циклических кодов iconУдк 669 квазикристаллы: открытие, структура, свойства, применение, получение
Квазикристаллы интерметаллидные соединения, атомная структура которых характеризуется наличием осей симметрии 5, 8, 10 и 12 порядков....
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org