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

Циклические коды БЧХ

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


Читайте также:
  1. Азотсодержащие гетероциклические соединения
  2. Брана и циклические мультивселенные
  3. Задание 4.Циклические вычислительные процессы. Решение задач, содержащих вычисление конечных сумм и произведений
  4. КОРРЕКТИРУЮЩИЕ КОДЫ. ЦИКЛИЧЕСКИЕ КОДЫ
  5. Основы термодинамики. Адиабатический процесс. Циклические процессы
  6. Укороченные циклические коды
  7. Циклические алгоритмы

Коды Боуза—Чоудхури—Хоквингема(БЧХ-коды) представ­ляют собой большой класс циклических кодов, исправляющих независимые ошибки кратности t именее. Для кодов БЧХ ха­рактерны все основные свойства циклических кодов. Чаще все­го коды БЧХ описывают с помощью корней порождающего мно­гочлена Р (х) степени 2t. В качестве корней Р (х) выбирают 2t последовательных элементов аj,aj+1..., аj+2i-1 поля Галуа GF (р'п), где 1≤ j≤pm— 1. Если при этом элемент а является примитивным (первообразным) в поле GF(pm), то такой код БЧХ называют примитивным с длиной кодовой комбинации п=рт 1 над полем GF (р). Для двоичных примитивных ко­дов БЧХ п = 2n — 1 над полем GF (2). В случае, если ряд кор­ней многочлена Р(х) для кода БЧХ начинается с j=1, т. е. а, а 2,.... а2t, то такой код называют кодом БЧХ в узком смысле.

Код БЧХ, у которого кореньа не является примитивным элементом поля GF (рm ), т. е. имеетпорядок d < рт —1, на­зывают непримитивнымс длинойкомбинации п =d.

Пусть а j - элементрасширения простого числового поля. Тогда по определению, данному в [7], некоторый нормирован­ныймногочлен т(х) наименьшей степени, для которого т(аj) = 0, называют минимальной функцией для аi.

Отметим, чтоминимальные функции m (х) являются непри-водимыми многочленами. Если предположить, что каждому из корней аi производящего многочлена Р (х) соответствует своя минимальнаяфункция тi (х), то производящий многочлен Р (х) должен быть наименьшим общимкратным всехминимальных функций, т. е.

P(x)=НОК[m1(x),m2(x),... m2t(x)].(51)

Таким образом, вектор, представленный многочленом f (x), будет кодовым тогда и только тогда, когда он делится без ос­татка как на каждую из минимальных функций т1 (х), m2(x),..., т2t (х), так и на их наименьшее общее кратное.

Тогда для любого из корней а, а2,....a2t справедливо урав­нение f (аi) = с0 + с1 аi2i)2+…cn-1 (ai)n-1 = 0, которое можно записать в виде произведения двух матриц (coc1c2…cn-1)*[lai(ai)2…(ai)n-1]T=0. Но так как корнями f (х) должны быть все элементы a, a2 …,a2t, то можно сделать вывод, что вектор (c0c1…cn-1 _ ) будет кодовым тогда и только тогда, когда он принадлежит нулевому прост­ранству матрицы

 

 


Может оказаться, что элементы аi и аj из совокупности а, а2,..., а2t соответствуют одной и той же минимальной функ­ции, т. е. тi (х) = mj (х). Вследствие того, что производящий многочлен Р(х) равен наименьшему общему кратному всех ми­нимальных функций mj (х), в качестве сомножителя в разложе­нии многочлена Р(х) следует взять только одну из нескольких равных между собой минимальных функций.

Из свойства 1.6 полей следует, что если аi корень какой-либо минимальной неприводимой по модулю 2 функции mi (х) степени к, то остальными корнями будут i)2,( (аi)2)2,...,(ai)2^(k-1).Следовательно, в разложении многочлена Р (х) каждаяиз различных минимальных функций mi (х) должна вхо­дить только один раз, а для построения матрицы (5.2) нужно использовать только по одному корню каждой из минимальных функций, входящих в разложение многочлена Р (х). Таким об­разом, если в качестве совокупности корней многочлена Р (х) выбраны элементы поля Галуа GF (2m) а, а2, а3,..., а2t, то при построении матрицы Н должны быть использованы только нечетные степени а, а3,..., а2t-1, а многочлен Р (х) будет иметь вид

P(x)=m1(x)m3(x)... m2t-1(x). (5.3)

Рассмотрим следующий пример.

Пример 5.1. Пусть имеем двоичный циклический код БЧХ. ккоторому вектор {f (х)} будет принадлежать только тогда, когда элементы а, a 2, а3, а4, а5, а6 будут корнями многочлена f (х). Кроме того, предполагается, что a — примитивный эле­мент поля Галуа GF (24). Тогда а15 = 1 и тi (х) обозначает минимальную функцию для аj.

В соответствие со свойством 1.6 элементы a, а2, а4 и а8 — корниодной и той же минимальной функции четвертой степе­ни, следовательно, m1 (х) = т2 (х)= т4 (х) = т8 (х). Анало­гично, а3, а6, а12 и а24 = а9 — корни минимальной функции чет­вертой степени и m3 (х) = т6 (х) = m9 (х) = т12(х), а элемен­ты a5 и а10 являются корнями минимальной функции второй степени и, следовательно, т5 (х)=т10(х). Отсюда, Р (х) яв­ляется многочленом

P(x)= ml(x)m3(x)m5(x) (5.4)

степень которого равна 10.

Таким образом, к искомому циклическому коду БЧХ будет принадлежать любой вектор {f (х)}, если f (х) делится на Р(х). В то же время циклический код будет нулевым пространством матрицы

Так как аj является элементом поля GF (2т) и представляет собой вектор из т двоичных элементов 0 и I, то матрица HT имеет размерность п * mt.

Из свойства 2.2 следует, что многочлен Р (х) является де­лителем многочлена F (х) = хn — 1, где п = 2m—1. В то же время, многочлен Р (х) для кодов БЧХ равен произведению ми­нимальных функций. Следовательно, любая из минимальных функций, входящих в разложение многочлена Р(х), должна быть делителем функции F (х) = хn — 1 = х2^m-1 — 1. При этом, как следует из высшей алгебры [4, 7], степень каждой мини­мальной функции не может быть больше т. А так как таких функций t, то степень многочлена Р (х) не превосходит mt. Отсюда каждая комбинация циклического примитивного кода БЧХ при длине, равной n = 2m—1, имеет число информационных разрядов, равное k≥2m — 1 —mt.

Рассмотрим конкретный пример построения циклического кода БЧХ.

Пример 5.2. Построить двоичный примитивный циклический код БЧХ для т = 4 и t= 3.

В этом случае длина кодовой комбинации равна п = 2m— 1 = 15, а вектор {f (х)} будет принадлежать этому цикличе­скому коду, если элементы поля GF (24) а, a2,..., а6 будут корнями многочлена f (х). Кроме того, отметим, что а — при­митивный элемент поля, а минимальной функцией для него пусть будет примитивный неприводимый многочлен т1 (х) = 1 +x+x4.

Как видим, этот пример является непосредственным про­должением примера 5.1, из которого следует, что производящий многочлен Р (х) имеет вид Р (х) = m1 (х) т3 (х) т5 (х), где т1 (х) иm3 (х) — минимальные многочлены четвертой степени, а т5 (х) — минимальный многочлен второй степени, вследствие чегостепень многочлена Р (х) равна 10. Кроме того, было по­казано, что матрица Н имеет вид (5.5).

Так как примитивный элемент а — корень минимального многочлена тх(х)= 1 + х + х4, то, подставив вместо каждого элемента матрицы Hего значение из табл. 1.1, получим транс­понированную матрицу НТ;

 

 

В [7] показано, что m3(x)=1+x+x2+x3+x4, m5(x)=1+x+x2, тогда степень многочлена P(x) равна 10, что не превышает mt.

В рассмотренном примере

Тогда производящая матрица G искомого систематического кода имеет вид:

 

Образованный таким образом циклический (n,k)=(15,5) код БЧХ позволяет исправить любую совокупность ошибок кратности t=3 и менее.


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


<== предыдущая страница | следующая страница ==>
ЦИКЛИЧЕСКИЕ КОДЫ, ИСПРАВЛЯЮЩИЕ ПАЧКИ ОШИБОК (КОДЫ ФАЙРА)| Принципы исправления ошибок кодами БЧХ

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