Рефетека.ру / Коммуникации и связь

Реферат: Циклические коды. Коды БЧХ

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ


кафедра РЭС


реферат на тему:


«Циклические коды. Коды БЧХ»


МИНСК, 2009

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


Циклическим кодом называется линейный блоковый (n,k)-код, который характеризуется свойством цикличности, т.е. сдвиг влево на один шаг любого разрешенного кодового слова дает также разрешенное кодовое слово, принадлежащее этому же коду и у которого, множество кодовых слов представляется совокупностью многочленов степени (n-1) и менее, делящихся на некоторый многочлен g(x) степени r = n-k, являющийся сомножителем двучлена xn+1.

Многочлен g(x) называется порождающим.

Как следует из определения, в циклическом коде кодовые слова представляются в виде многочленов Циклические коды. Коды БЧХ
где n - длина кода;

Циклические коды. Коды БЧХ- коэффициенты из поля GF(q).

Если код построен над полем GF(2), то коэффициенты принимают значения 0 или 1 и код называется двоичным.
Пример. Если кодовое слово циклического кода
Циклические коды. Коды БЧХ то соответствующий ему многочлен Циклические коды. Коды БЧХ

Например, если код построен над полем GF(q)=GF(23), которое является расширением GF(2) по модулю неприводимого многочлена f(z)=z3+z+1, а элементы этого поля имеют вид, представленный в таблице 1,


Таблица 1

0 000 0 3 011 Z+1
0 001 1 4 110 Z2+Z
1 010 Z 5 111 Z2+Z+1
2 100 Z2 6 101 Z2+1

то коэффициенты Циклические коды. Коды БЧХпринимают значения элементов этого поля и поэтому они сами отображаются в виде многочленов следующего вида Циклические коды. Коды БЧХ
где m - степень многочлена, по которому получено расширение поля GF(2);\ ai - коэффициенты, принимающие значение элементов GF(2), т.е. 0 и 1. Такой код называется q-ным.

Длина циклического кода называется примитивной и сам код называется примитивным, если его длина n=qm-1 на GF(q).

Если длина кода меньше длины примитивного кода, то код называется укороченным или непримитивным.

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

Результатом деления двучлена xn+1 на многочлен g(x) является проверочный многочлен h(x).

При декодировании циклических кодов используются многочлен ошибок e(x) и синдромный многочлен S(x).

Многочлен ошибок степени не более (n-1) определяется из выражения Циклические коды. Коды БЧХ где Циклические коды. Коды БЧХ- многочлены, отображающие соответственно принятое (с ошибкой) и переданное кодовые слова.

Ненулевые коэффициенты в е(x) занимают позиции, которые соответствуют ошибкам.

Пример.
Циклические коды. Коды БЧХ

Синдромный многочлен, используемый при декодировании циклического кода, определяется как остаток от деления принятого кодового слова на порождающий многочлен, т.е.

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

Следовательно, синдромный многочлен зависит непосредственно от многочлена ошибок е(х).Это положение используется при построении таблицы синдромов, применяемой в процессе декодирования. Эта таблица содержит список многочленов ошибок и список соответствующих синдромов, определяемых из выражения Циклические коды. Коды БЧХ(см. таблицу 2).


Таблица 2

(x) S(x)
1 Rg(x)[1]
X Rg(x)[x]
X2 Rg(x)[x2]
X+1 Rg(x)[x+1]
X2+1 Rg(x)[x2+1]

В процессе декодирования по принятому кодовому слову вычисляется синдром, затем в таблице находится соответствующий многочлен е(х), суммирование которого с принятым кодовым словом дает исправленное кодовое слово, т.е. Циклические коды. Коды БЧХ Перечисленные многочлены Циклические коды. Коды БЧХможно складывать, умножать и делить, используя известные правила алгебры, но с приведением результата по mod 2, а затем по mod xn+1, если степень результата превышает степень (n-1).

Примеры.

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

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

Допустим, что длина кода n=7, то результат приводим по mod x7+1.

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

При построении и декодировании циклических кодов в результате деления многочленов обычно необходимо иметь не частное, а остаток от деления.
Поэтому рекомендуется более простой способ деления, используя не многочлены, а только его коэффициенты (вариант 2 в примере).

Пример.

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


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

Матричное задание кодов


Циклический код может быть задан порождающей и проверочной матрицами. Для их построения достаточно знать порождающий g(x) и проверочный h(x) многочлены. Для несистематического циклического кода матрицы строятся циклическим сдвигом порождающего и проверочного многочленов, т.е. путем их умножения на x Циклические коды. Коды БЧХи Циклические коды. Коды БЧХ

При построении матрицы H(n,k) старший коэффициент многочлена h(x) располагается справа.

Пример. Для циклического (7,4)-кода с порождающим многочленом g(x)=x3+x+1 матрицы G(n,k) и H(n,k) имеют вид: Циклические коды. Коды БЧХЦиклические коды. Коды БЧХгде Циклические коды. Коды БЧХ

Для систематического циклического кода матрица G(n,k) определяется из выражения Циклические коды. Коды БЧХгде Ik - единичная матрица; Rk,r - прямоугольная матрица. Строки матрицы Rk,r определяются из выражений Циклические коды. Коды БЧХили Циклические коды. Коды БЧХгде ai(x) - значение i-той строки матрицы Ik; i - номер строки матрицы Rk,r.

Пример. Матрица G(n,k) для (7,4)-кода на основе порождающего многочлена g(x)=x3+x+1, строится в следующей последовательности Циклические коды. Коды БЧХ
Циклические коды. Коды БЧХили Циклические коды. Коды БЧХ

Определяется R4,3, используя Циклические коды. Коды БЧХтак Циклические коды. Коды БЧХкак Циклические коды. Коды БЧХЦиклические коды. Коды БЧХ

Аналогичным способом определяется Циклические коды. Коды БЧХ

В результате получаем Циклические коды. Коды БЧХили Циклические коды. Коды БЧХ

Используя выражение Циклические коды. Коды БЧХполучим тот же результат.
Строки матрицы G(n,k) можно определить непосредственно из выражения
Циклические коды. Коды БЧХгде Циклические коды. Коды БЧХ

Проверочная матрица в систематическом виде строится на основе матрицы G(n,k), а именно: Циклические коды. Коды БЧХгде Ir - единичная матрица; Циклические коды. Коды БЧХ- матрица из G(n,k) в транспонированном виде.

Пример. Для (7,4)-кода матрица H(n,k) будет иметь вид: Циклические коды. Коды БЧХ

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

Существуют специальные таблицы по выбору g(x) в зависимости от предъявляемых требований к корректирующим возможностям кода. Однако у каждого циклического кода имеются свои особенности формирования g(x). Поэтому при изучении конкретных циклических кодов будут рассматриваться соответствующие способы построения g(x).

Коды БЧХ


Одним из классов циклических кодов, способных исправлять многократные ошибки, являются коды БЧХ.

Примитивным кодом БЧХ, исправляющим tu ошибок, называется код длиной n=qm-1 над GF(q), для которого элементы Циклические коды. Коды БЧХявляются корнями порождающего многочлена.

Здесь  - примитивный элемент GF(qm).

Порождающий многочлен определяется из выражения
Циклические коды. Коды БЧХгде f1(x),f2(x)...- минимальные многочлены корней g(x).

Число проверочных элементов кода БЧХ удовлетворяет соотношению Циклические коды. Коды БЧХ

Пример. Определить значение порождающего многочлена для построения примитивного кода БЧХ над GF(2) длины 31, исправляющего двух кратные ошибки (tu=2).

Исходя из определения кода БЧХ корнями многочлена g(x) являются: Циклические коды. Коды БЧХ, где  - примитивный элемент GF(qm)=GF(25).

Порождающий многочлен определяется из выражения Циклические коды. Коды БЧХгде f1(x), f2(x), f3(x), f4(x) - минимальные многочлены корней соответственно Циклические коды. Коды БЧХ.

Примечание.

Минимальный многочлен элемента  поля GF(qm) определяется из выражения Циклические коды. Коды БЧХ, где Циклические коды. Коды БЧХ- наименьшее целое число, при котором Циклические коды. Коды БЧХ.

Значения минимальных многочленов будут следующими:
Циклические коды. Коды БЧХ

Так как f1(x)= f2(x)= f4(x), то
Циклические коды. Коды БЧХ

На практике при определении значений порождающего многочлена пользуются специальной таблицей минимальных многочленов (см. таблицу 8 приложения), и выражением для порождающего многочлена Циклические коды. Коды БЧХПри этом работа осуществляется в следующей последовательности.

По заданной длине кода n и кратности исправляемых ошибок tu определяют:
- из выражения n=2m-1 значение параметра m, который является максимальной степенью сомножителей g(x); - из выражения j=2tu-1 максимальный порядок минимального многочлена, входящего в число сомножителей g(x).

- пользуясь таблицей минимальных многочленов, определяется выражение для g(x) в зависимости от m и j. Для этого из колонки, соответствующей параметру m, выбираются многочлены с порядками от 1 до j, которые в результате перемножения дают значение g(x).

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

Например, минимальные многочлены элементов Циклические коды. Коды БЧХсоответствуют минимальному многочлену элемента 1, минимальные многочлены элементов Циклические коды. Коды БЧХсоответствуют минимальному многочлену 3 и т.п.

Пример. Определить значение порождающего многочлена для построения примитивного кода БЧХ над GF(2) длины 31, обеспечивающего tu=3.

Определяем значения m и j. Циклические коды. Коды БЧХ

Из таблицы минимальных многочленов в соответствии с m=5 и j=5 получаем
Циклические коды. Коды БЧХ

Заданные исходные данные: n и tu или k и tu для построения циклического кода часто приводят к выбору завышенного значения m и как следствие этого к неоправданному увеличению длины кода. Такое положение снижает эффективность полученного кода, так как часть информационных разрядов вообще не используется.

Пример. Требуется построить циклический код, исправляющий двух кратные ошибки, если длина информационной части кода k=40.

Согласно выражению для примитивного кода n=2m-1, ближайшая длина кода равна 63, для которой m=6, а r=mtu=12. Следовательно, код будет иметь n=63, k=51. Неиспользованных информационных разрядов будет 11(51-40).

Подобное несоответствие в ряде случаев можно устранить, применяя непримитивный код БЧХ.

Непримитивным кодом БЧХ, исправляющим tu ошибок, называется код длины n над GF(q), для которого элементы Циклические коды. Коды БЧХявляются корнями порождающего многочлена.

Здесь i-непримитивный элемент GF(qm), а длина кода n равна порядку элемента i.

Примечание.

Порядком элемента i является наименьшее n, для которого Циклические коды. Коды БЧХ.

Пример. Порядок элемента 3 поля GF(26) равен 21, так как Циклические коды. Коды БЧХ.

Порождающий многочлен непримитивного кода БЧХ, по аналогии с примитивным кодом, определяется из выражения Циклические коды. Коды БЧХЦиклические коды. Коды БЧХ- минимальные многочлены элементов Циклические коды. Коды БЧХполя GF(qm), которые являются корнями g(x); i - степень непримитивного элемента .

Пример. Определить значение g(x) для построения непримитивного кода БЧХ над GF(2) длины n=20, исправляющего двух кратные ошибки.

Из таблицы непримитивных элементов GF(2m) (см. таблицу 7 приложения) выбираем поле, элемент  которого имеет порядок больший, но близкий к заданному n.


Приложение

Таблица 1

Разложение бинома хn+1 на неприводимые сомножители

Степень бинома

Последовательности степеней корней неприводимых сомножителей

Неприводимые сомножители

7

1 2 4
3 6 5

13
15

15

01 02 04 08
03 06 12 09
05 10
07 14 13 11

023
037
007
031

31

01 02 04 08 16
03 06 12 24 17
05 10 20 09 18
07 14 28 25 19
11 22 13 26 21
15 30 29 27 23

045
075
067
057
073
051

63

01 02 04 08 16 32
03 06 12 24 48 33
05 10 20 40 17 34
07 14 28 56 49 35
09 18 36
11 22 44 25 50 37
13 26 52 41 19 38
15 30 60 57 51 39
21 42
23 46 29 58 53 43
27 54 45
31 62 61 59 55 47

103
127
147
111
015
155
133
165
007
163
013
141


Примечание. В разложение всех биномов входит сомножитель 03 с корнем 00. Все сомножители представлены в восьмеричной форме.


Таблица 2

Элементы поля GF(16) как расширение GF(2) по примитивному многочлену (z)=z4+z+1

В двоичном виде

В виде многочлена

В виде степени

0000 0 0
0001 1 0
0010 z 1
0100 z2 2
1000 z3 3
0011 z+1 4
0110 z2+z 5
1100 z3+z2 6
1011 z3+z+1 7
0101 z2+1 8
1010 z3+z 9
0111 z2+z+1 10
1110 z3+z2+z 11
1111 z3+z2+z+1 12
1101 z3+z2+1 13
1001 z3+1 14

Таблица 3

Элементы поля GF(16) как расширение GF(4) по примитивному многочлену f(z)=z2+z+2

В четвертичном виде

В десятичном виде

В виде многочлена

В виде степени

00 0 0 0
01 1 1 0
10 4 z 1
12 6 z+2 2
32 14 3z+2 3
11 5 z+1 4
02 2 2 5
20 8 2z 6
23 11 2z+3 7
13 7 z+3 8
22 10 2z+2 9
03 3 3 10
30 12 3z 11
31 13 3z+1 12
21 9 2z+1 13
33 15 3z+3 14

Таблица 4

Элементы поля GF(4) как расширение GF(2) по примитивному многочлену f(z)=z2+z+1

В двоичном виде

В виде многочлена

В виде степени

В десятичном виде

00 0 0 0
01 1 0 1
10 z 1 2
11 z+1 2 3

Таблица 6

Элементы поля GF(8) как расширение GF(2) по примитивному многочлену f(z)=z3+z+1

В двоичном виде

В виде многочлена

В виде степени

000 0 0
001 1 0
010 z 1
100 z2 2
011 z+1 3
110 z2+z 4
111 z2+z+1 5
101 z2+1 6

Таблица 7

Непримитивные элементы поля GF(2m)

m

GF(2m)

n

1 4 GF(24) 3 5



5 3
2 6 GF(26) 3 21



7 9



9 7
3 8 GF(27) 3 85



5 51



15 17



17 15
4 9 GF(29) 7 73
5 10 GF(210) 3 341



11 93



31 33



33 31
6 12 GF(212) 3 1365



5 819



7 585



9 455



13 315



15 273



21 195



45 91



63 65



65 63

Таблица 8

Минимальные неприводимые многочлены в поле GF(2m)

2tu-1



m




2 3 4 5 6 7 8 9 10

1
3
5
7
9
11
13
15
17
19
21
23
25
27
29
31
33
35

7

13
15

31
37
07
31

45
75
67
57
73

103
127
147
111
015
155

211
217
235
367
277
325
203

435
567
763
551
675
747
453
727
023
545
613
543
433
477
615
435
537
771

1021
1131
1461
1231
1423
1055
1167
1541
1333
1605
1027
1751
1743
1617
1401

2011
2017
2415
3771
2257
2065
2157
2653
3515
2773
3753
2033
2443
3573
2461
3041
75
3023


Такими являются GF(26) и 3, порядок которого n=21.

Так как j=2tu-1=2(2-1=3, то выражение для g(x) будет иметь вид Циклические коды. Коды БЧХ
где f3(x) и f9(x) - минимальные многочлены элементов 3 и 9 поля GF(26).

Значения этих многочленов следующие:
Циклические коды. Коды БЧХ
Циклические коды. Коды БЧХ

Выражения для f3(x) и f9(x) можно определить из таблицы минимальных многочленов, используя для этого параметр m выбранного поля GF(2m) и порядковые номера сомножителей g(x).

Для рассмотренного примера m=6, а порядковые номера равны 3 и 9. Поэтому Циклические коды. Коды БЧХ
Циклические коды. Коды БЧХ.

ЛИТЕРАТУРА


Лидовский В.И. Теория информации. - М., «Высшая школа», 2002г. – 120с.

Метрология и радиоизмерения в телекоммуникационных системах. Учебник для ВУЗов. / В.И.Нефедов, В.И.Халкин, Е.В.Федоров и др. – М.: Высшая школа, 2001 г. – 383с.

Цапенко М.П. Измерительные информационные системы. - . – М.: Энергоатом издат, 2005. - 440с.

Зюко А.Г. , Кловский Д.Д., Назаров М.В., Финк Л.М. Теория передачи сигналов. М: Радио и связь, 2001 г. –368 с.

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

Рефетека ру refoteka@gmail.com