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

Матричное представление циклических кодов

I. АЛГЕБРАИЧЕСКИЕ ОСНОВЫ ТЕОРИИ ЦИКЛИЧЕСКИХ КОДОВ | Поля Галуа и их свойства | Сложение многочленов | Умножение многочленов | Деление многочленов | ЦИКЛИЧЕСКИЕ КОДЫ, ИСПРАВЛЯЮЩИЕ ПАЧКИ ОШИБОК (КОДЫ ФАЙРА) | ЦИКЛИЧЕСКИЕ КОДЫ БЧХ | Принципы исправления ошибок кодами БЧХ | ЦИКЛИЧЕСКИЕ КОДЫ РИДА—СОЛОМОНА | Кодированиеи декодирование кодов PC |


Читайте также:
  1. I. АЛГЕБРАИЧЕСКИЕ ОСНОВЫ ТЕОРИИ ЦИКЛИЧЕСКИХ КОДОВ
  2. III. Регистры и уровни рекламных кодов
  3. Артикуляция визуальных кодов
  4. В этих работах даётся истинное представление о Космосе, раскрывается подлинная история нашей страны, с абсолютной точностью показаны ритмы революционных переходов.
  5. В. Оформление и представление на кафедру ВКР
  6. ВАШЕ ПРЕДСТАВЛЕНИЕ О ПЕРЕДАЧЕ ПОЛНОМОЧИЙ
  7. Ваше представление о себе

Систематический циклический код может быть полностью определен своей производящей матрицей, которая строится по следующему правилу. Сначала записывается единичная матрица Еk для исходного k-элементного кода. Далее одночлен, соответствующей каждой из строк Еk, умножается на хn-k и делится на производящий многочлен Р(х). В результате деления получим остатки, каждый из которых соответствует определенной строке матрицы Еk. Из этих остатков составляется дополнительная матрица R, которая приписывается к матрице Еk. Таким образом, производящая матрица для циклического (n, k)-кода будет иметь вид G=[RЕk], где R-приписанная к Еk проверочная матрица размерности k * (n-k).

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

Пример. Пусть необходимо построить циклический код, для которого n=7, k=4, n-k=3, а P(x)=1+x+x3. Прежде всего запишем единичную матрицу Еk:

 

 

строкам которой соответствуют одночлены 1, х, х2, х3.

Каждая строка умножается на хn-k = х3тогда получим новую матрицу, в которой каждая строка будет сдвинута на n— k нулей.

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

Найденные остатки многочленов x3, x4, x5, x6 на P(x)=1+x+x3 будут соответственно равны R1(x)=1+x; R2(x)=x+x2; R3(x)=1+x+x2; R4(x)=1+x2.

Теперь составляем проверочную матрицу R, элементами которой являются остатки в двоичной форме записи:

 

Приписывая эту матрицу к единичной матриц Еk, получим производящую матрицу для циклического кода

Образующая матрица G позволяет преобразовывать комбинацию исходного кода (a0, a1, … ak-1) в комбинацию циклического кода путем ее умножения на матрицу G. Пусть для рассматриваемого примера кода исходная комбинация равна (1110), т.е. φ (х)= 1+x+x2. Умножив ее на матрицу G, т.е. [1110]* G, получим циклическую комбинацию (0101110).

В [7] доказана следующая теорема:

Если V-пространство строк матрицы G=[RЕk], где Еk-единичная матрица размерности k*k, а R-матрица размерности k*(n-k), то V-является нулевым пространством матрицы H=[En-kRT], где En-k- единичная матрица размерности (n-k)*(n-k), а RT-транспорированная матрица R.

По этой теореме двоичный систематический циклический (n,k)-код, производящая матрица которого имеет вид G=[R Еk], является нулевым пространством проверочной матрицы H=[En- kRT] и, следовательно, G*HT=0.

Так, для нашего примера матрица H с учетом найденного ранее матрицы R будет иметь вид:

Легко проверить, что G*HT=0.

Для несистематического кода образующая матрица G строится в соответствии с правилом построения кода, а именно, путем умножения многочлена исходной комбинации φ(x) на порождающий многочлен Р(x). Для получения матрицы G составляют единичную матрицу Ek и каждую ее строку, представленную одночленом xi, умножают на многочлен Р(x). Из коэффициентов полученных многочленов xi* Р(x) составляют образующую матрицу G несистематического кода. Для рассматриваемого выше примера кода (7,4) с Р(x)=1+x+x3, записав произведения xi* Р(x), где i=0,1,2,3, получим следующую матрицу G:

 

Также, как и для систематического кода, несистематический циклический код должен представлять собой нулевое пространство по отношению к некоторой проверочной матрице H, которая может быть построена по проверочному полиному

 

 

Выражение (2.9) следует из свойства 2.2 циклических кодов и сравнения (2.4), согласно которому многочлен Р (х) является делителем двучлена хn + 1, где п = 2n-k — 1. Тогда строки проверочной матрицы Н будут состоять из коэффициентов мно­гочленов хiН(х), где i = 0,1,..., (пk —1). Так, для рассматриваемого примера кода (7, 4) имеем Н(х)= =(x7+1)/P(x)=1+x+x2+x4.

Записав многочлены Н(х), xH(x), x2H(x), составим проверочную матрицу H:

 

в которой строки записаны начиная со старшей степени.

Легко проверить, что G*HT =0.

Следует отметить, что может быть построена проверочная матрица H, единая как для систематического, так и для неси­стематического кода, исходя из свойства 2.1 циклических ко­дов. Из этого свойства следует, что, если некоторый элемент а поля GF(2n) является корнем многочлена Р (х), то он явля­ется также и корнем многочлена f (х). Отсюда любая комбина­ция циклического кода, представленная многочленом (2.1), удовлетворяет равенству

 

f(α)≡0, (2.10)

которое может быть получено как произведение [сос1c2... cп-1] НТ, где H-проверочная матрица вида:

H=[1αα2….αn-1]. (2.11)

Учитывая, что для рассматриваемого примера кода (7, 4) по­рождающий многочлен Р(х) = 1+х+x3 является примитив­ным и а — его корень, матрица Н будет состоять из ненулевых элементов поля GF (23), т. е.

H=[1αα2α3α4α5α6].

Заменив элементы αi их двоичными векторами и записав их в виде столбцов получим следующую проверочную матрицу:


 

 

 

Легко проверить, что полученная проверочная матрица Н удовлетворяет равенству G*HT=0 как для систематического, так и для несистематического циклических кодов (7,4), построенных по многочлену Р(х)=1+х+х3.

 


Дата добавления: 2015-07-16; просмотров: 124 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Реализация операций умножения и деления многочленов в поле двоичных чисел| Принципы обнаружения и исправления ошибок циклическими кодами

mybiblioteka.su - 2015-2024 год. (0.007 сек.)