Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Циклические коды

Читайте также:
  1. А. Полициклические антидепрессанты
  2. Ациклические упражнения в оздоровительной физической культуре
  3. КУЛЬТУРНО-ИСТОРИЧЕСКИЕ (ЦИКЛИЧЕСКИЕ) КОНЦЕПЦИИ
  4. КУЛЬТУРНО-ИСТОРИЧЕСКИЕ (ЦИКЛИЧЕСКИЕ) КОНЦЕПЦИИ
  5. Линейные, разветвленные, циклические
  6. Полициклические ароматические углеводороды
  7. Понятие «Новая история» и проблемы периодизации. Циклические и линейные схемы исторического процесса. Их характеристика.
  8. Тема: Циклические алгоритмы. Цикл с предусловием.
  9. Циклические (конъюнктурные) и сезонные колебания
  10. Циклические алгоритмы

Циклическим кодом называется линейный код, который представляет собой конечное множество, замкнутое относительно операции циклического сдвига кодовых векторов, образующих его. Пусть дан n -мерный вектор v = a 0 a 1an -1 с координатами из конечного поля F. Его циклическим сдвигом называется вектор v' = a n­ -1a0a1an -2.

Рассмотрим n -мерное арифметическое пространство над полем Галуа GF (2). Каждому вектору a 0 a 1an -1 из GF (2) можно сопоставить взаимно однозначно многочлен a 0+ a 1 x +…+ an -1 xn -1 с коэффициентами из GF (2). Сумме двух векторов a 0 a 1an -1 и b 0 b 1bn -1 ставится в соответствие сумма соответствующих им многочленов, произведению элементов поля на вектор - произведение многочлена, соответствующего этому вектору, на элемент.

Рассмотрим некоторый многочлен g (x) из описанного линейного пространства. Множество всех многочленов из этого подпространства, которые делятся без остатка на g (x), образует линейное подпространство. Линейное подпространство определяет некоторый линейный код.

Линейный код, образованный классом многочленов C (g (x)), кратных некоторому полиному g (x), называемому порождающим многочленом, называется полиномиальным.

Покажем, как связаны полиномиальные коды C (g (x)) и циклические коды. Пусть a = a 0 …an -1 – некоторое кодовое слово, а соответствующий кодовый многочлен a (x) = a 0+...+ an -1 xn -1. Циклическому сдвигу a ' соответствует кодовый многочлен a '(x) = an -1+ a 0 x +…+ an -2 x n-1, который можно выразить через первоначальный:

 

Поскольку полиномиальный код должен делиться на g (x), то для того, чтобы он был циклическим, многочлен a '(x) должен делиться на g (x). Из этого соображения можно сформулировать следующую теорему. Полиномиальный код является циклическим тогда и только тогда, когда многочлен g (x) является делителем многочлена xn –1. В этом случае многочлен g (x) называется порождающим многочленом циклического кода.

В теории кодирования доказывается следующая теорема: если многочлен g (x) имеет степень nk и является делителем xn –1, то C (g (x)) является линейным циклическим (n, k)-кодом.

Многочлен xn –1 разложим на множители xn –1 = (x –1)(xn -1+ xn -1+…+1). Следовательно, циклические коды существуют при любом n. Число циклических n -разрядных кодов равно числу делителей многочлена xn –1. Для построения циклических кодов разработаны таблицы разложения многочленов xn –1 на неприводимые многочлены, то есть на такие, которые делятся только на единицу и на самого себя.

Рассмотрим, например, какие коды можно построить на основе многочлена x 7–1 над полем GF (2). Разложение многочлена на неприводимые множители имеет вид

 

Поскольку можно образовать шесть делителей многочлена x 7–1, комбинируя неприводимые делители, существует шесть двоичных циклических кодов. (n, k)-код определяется, во-первых, значением n, а во-вторых, значением k = ns, s – степень многочлена-делителя xn –1, определяющего код. Ниже приведены делители полинома и соответствующие им значения k:

x – 1, s =1, k =6;

x 3 +x 2+1, s =3, k =4;

x 3 +x +1, s =3, k =4;

(x –1)(x 3 +x 2+1)= x 4+x2+x+1, s =4, k =3;

(x –1)(x 3 +x +1)= x 4+x3+x2+1, s =4, k =3;

(x 3 +x 2+1)(x 3 +x +1)= x 6+ x 5+ x 4+ x 3+ x 2+ x, s =6, k =1.

(7, 6)-код имеет лишь один проверочный символ, а (7, 1)-код – лишь один информационный. Они являются соответственно кодом с проверкой на чётность и кодом с повторением.

Как и обычный линейный код, циклический код может быть задан порождающей матрицей. Следовательно, задача состоит в том, чтобы найти такую матрицу, то есть найти k линейно независимых кодовых комбинаций, образующих её. Воспользуемся для этого свойством замкнутости циклического кода относительно операции циклического сдвига. Заметим, что циклический сдвиг вправо на один разряд эквивалентен умножению многочлена g (x) на x. Тогда порождающую матрицу можно построить, взяв в качестве строк порождающий многочлен и k его циклических сдвигов:

 

Например, рассмотрим один из делителей многочлена x 7–1, а именно полином g (x)=1+ x + x 3. Ему соответствует кодовая комбинация 1101000 (выписаны коэффициенты при степенях 0, 1, …, 6 порождающего многочлена, так как кодовая комбинация содержит 7 символов). Тогда порождающая матрица (7,4) имеет вид

 

Рассмотрим теперь, как с помощью порождающего многочлена g (x) = 1+ x + x 3 осуществляется кодирование (7, 4)-кодом. Возьмём, например, 4-разрядное слово (0101), которому соответствует многочлен f (x) = x + x 3. Перемножив эти два многочлена:

f (x) g (x) = (x + x 3)(1+ x + x 3) = x + x 2+ x 3+ x 6,

получим кодовую комбинацию 0111001. Аналогично можно получить кодовые слова для всех 4-разрядных двоичных слов. Однако получившийся код, как видно, не является разделимым, что неудобно для практических нужд.

Чтобы закодировать сообщение h (x) циклическим кодом C (g (x)), который является разделимым, нужно разделить многочлен xn - k h (x) на g (x) и прибавит остаток от деления к многочлену xn - k h (x).

Для примера рассмотрим кодовую комбинацию 1101. Этому вектору соответствует полином h (x)=1+ x + x 3. Тогда xn - k h (x)= x 3+ x 4+ x 6. Разделим получившийся многочлен на g (x) = 1+ x + x 3, получим остаток, равный 0. Тогда кодовый вектор равен 0001101.




Дата добавления: 2015-01-05; просмотров: 55 | Поможем написать вашу работу | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2024 год. (0.008 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав