Циклічні коди Коди БЧХ

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Білоруський державний університет інформатики і радіоелектроніки
кафедра РЕЗ
реферат на тему:
«Циклічні коди. Коди БЧХ »
МІНСЬК, 2009

Циклічні коди
Циклічним кодом називається лінійний блоковий (n, k)-код, який характеризується властивістю циклічності, тобто зсув вліво на один крок будь-який дозволений кодового слова дає також дозволене кодове слово, що належить цьому ж коду і в якого, безліч кодових слів представляється сукупністю многочленів ступеня (n-1) і менш, що діляться на деякий многочлен g (x) ступеня r = nk , що є співмножником двочлена x n +1.
Многочлен g (x) називається породжує.
Як випливає з визначення, в циклічному коді кодові слова представляються у вигляді многочленів
де n - довжина коду;
- Коефіцієнти з поля GF (q).
Якщо код побудований над полем GF (2), то коефіцієнти приймають значення 0 або 1 і код називається двійковим.
Приклад. Якщо кодове слово циклічного коду
то відповідний йому многочлен
Наприклад, якщо код побудований над полем GF (q) = GF (2 3), яке є розширенням GF (2) по модулю неприводимого многочлена f (z) = z 3 + z +1, а елементи цього поля мають вигляд, представлений у таблиці 1,

Таблиця 1

0
000
0
a 3
011
Z +1
a 0
001
1
a 4
110
Z 2 + Z
a 1
010
Z
a 5
111
Z 2 + Z +1
a 2
100
Z 2
a 6
101
Z 2 +1
то коефіцієнти приймають значення елементів цього поля і тому вони самі відображаються у вигляді многочленів наступного виду
де m - ступінь многочлена, за яким отримано розширення поля GF (2); \ a i - коефіцієнти, які беруть значення елементів GF (2), тобто 0 і 1. Такий код називається q-ним.
Довжина циклічного коду називається примітивною і сам код називається примітивним, якщо його довжина n = q m -1 на GF (q).
Якщо довжина коду менше довжини примітивного коду, то код називається укороченим або непрімітівним.
Як випливає з визначення загальна властивість кодових слів циклічного коду - це їх подільність без залишку на деякий многочлен g (x), званий породжує.
Результатом розподілу двочлена x n +1 на многочлен g (x) є перевірочний многочлен h (x).
При декодуванні циклічних кодів використовуються многочлен помилок e (x) і синдромних многочлен S (x).
Многочлен помилок ступеня не більше (n-1) визначається з виразу де - Многочлени, що відображають відповідно прийняте (з помилкою) і передане кодові слова.
Ненульові коефіцієнти в е (x) займають позиції, які відповідають помилок.
Приклад.

Синдромний многочлен, використовуваний при декодуванні циклічного коду, визначається як залишок від ділення прийнятого кодового слова на породжує многочлен, тобто

або
Отже, синдромних многочлен залежить безпосередньо від многочлена помилок е (х). Це положення використовується при побудові таблиці синдромів, застосовуваної в процесі декодування. Ця таблиця містить список многочленів помилок і список відповідних синдромів, обумовлених з виразу (Див. таблицю 2).

Таблиця 2

(X)
S (x)
1
R g (x) [1]
X
R g (x) [x]
X 2
R g (x) [x2]
·
·
·
·
·
·
X +1
R g (x) [x +1]
X 2 +1
R g (x) [x2 +1]
·
·
·
·
·
·
У процесі декодування за прийнятим кодовому слову обчислюється синдром, потім в таблиці знаходиться відповідний многочлен е (х), підсумовування якого з прийнятим кодовим словом дає виправлене кодове слово, тобто Перераховані многочлени можна складати, множити і ділити, використовуючи відомі правила алгебри, але з приведенням результату по mod 2, а потім по mod x n +1, якщо ступінь результату перевищує ступінь (n-1).
Приклади.


Припустимо, що довжина коду n = 7, то результат наводимо по mod x 7 +1.

При побудові і декодуванні циклічних кодів в результаті ділення многочленів звичайно необхідно мати не приватна, а залишок від ділення.
Тому рекомендується більш простий спосіб розподілу, використовуючи не многочлени, а тільки його коефіцієнти (варіант 2 у прикладі).
Приклад.
1.
2.

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

Циклічний код може бути заданий породжує і перевірочної матрицями. Для їх побудови досить знати породжує g (x) і перевірочний h (x) многочлени. Для несистематичного циклічного коду матриці будуються циклічним зсувом породжує і перевірочного многочленів, тобто шляхом їх множення на x і
При побудові матриці H (n, k) старший коефіцієнт многочлена h (x) розташовується праворуч.
Приклад. Для циклічного (7,4)-коду з породжує многочленом g (x) = x 3 + x +1 матриці G (n, k) і H (n, k) мають вигляд: де
Для систематичного циклічного коду матриця G (n, k) визначається з виразу де I k - одинична матриця; R k, r - прямокутна матриця. Рядки матриці R k, r визначаються з виразів або де a i (x) - значення i-того рядка матриці I k; i - номер рядка матриці R k, r.
Приклад. Матриця G (n, k) для (7,4)-коду на основі породжує многочлена g (x) = x 3 + x +1, будується в такій послідовності
або
Визначається R 4,3, використовуючи так як
Аналогічним способом визначається
У результаті отримуємо або
Використовуючи вираз отримаємо той самий результат.
Рядки матриці G (n, k) можна визначити безпосередньо з виразу
де
Перевірочна матриця в систематичному вигляді будується на основі матриці G (n, k), а саме: де I r - одинична матриця; - Матриця з G (n, k) в транспонованої вигляді.
Приклад. Для (7,4)-коду матриця H (n, k) буде мати вигляд:
Одна з основних задач, що стоять перед розробниками пристроїв захисту від помилок при передачі дискретних повідомлень по каналах зв'язку є вибір породжує многочлена g (x) для побудови циклічного коду, що забезпечує необхідну мінімальну кодова відстань для гарантійного виявлення та виправлення t-кратних помилок.
Існують спеціальні таблиці з вибору g (x) в залежності від пропонованих вимог до коригуючих можливостям коду. Однак у кожного циклічного коду є свої особливості формування g (x). Тому при вивченні конкретних циклічних кодів будуть розглядатися відповідні способи побудови g (x).

Коди БЧХ
Одним з класів циклічних кодів, здатних виправляти багаторазові помилки, є коди БЧХ.
Примітивним кодом БЧХ, виконуючим t u помилок, називається код довжиною n = q m -1 над GF (q), для якого елементи є корінням породжує многочлена.
Тут a - примітивний елемент GF (q m).
Породжує многочлен визначається з виразу
де f 1 (x), f 2 (x )...- мінімальні многочлени коренів g (x).
Число перевірочних елементів коду БЧХ задовольняє співвідношенню
Приклад. Визначити значення породжує многочлена для побудови примітивного коду БЧХ над GF (2) довжини 31, виправляє двох кратні помилки (t u = 2).
Виходячи з визначення коду БЧХ корінням многочлена g (x) є: , Де a - примітивний елемент GF (q m) = GF (2 5).
Породжує многочлен визначається з виразу де f 1 (x), f 2 (x), f 3 (x), f 4 (x) - мінімальні многочлени коренів відповідно .
Примітка.
Мінімальний многочлен елемента b поля GF (q m) визначається з виразу , Де - Найменше ціле число, при якому .
Значення мінімальних многочленів будуть наступними:

Так як f1 (x) = f2 (x) = f4 (x), то

На практиці при визначенні значень породжує многочлена користуються спеціальною таблицею мінімальних многочленів (див. таблицю 8 додатка), і виразом для породжує многочлена При цьому робота здійснюється в такій послідовності.
По заданій довжині коду n і кратності виправляє помилок t u визначають:
- З виразу n = 2 m -1 значення параметра m, який є максимальним ступенем співмножників g (x); - з виразу j = 2t u -1 максимальний порядок мінімального многочлена, що входить до числа співмножників g (x).
- Користуючись таблицею мінімальних многочленів, визначається вираз для g (x) в залежності від m та j. Для цього з колонки, відповідної параметру m, вибираються многочлени з порядками від 1 до j, які в результаті перемножування дають значення g (x).
У виразі для g (x) утримуватися мінімальні многочлени тільки для непарних ступенів a, так як зазвичай відповідні їм мінімальні многочлени парних ступенів a мають аналогічні вирази.
Наприклад, мінімальні многочлени елементів відповідають мінімальному многочлену елемента a 1, мінімальні многочлени елементів відповідають мінімальному многочлену a 3 та т.п.
Приклад. Визначити значення породжує многочлена для побудови примітивного коду БЧХ над GF (2) довжини 31, що забезпечує t u = 3.
Визначаємо значення m і j.
З таблиці мінімальних многочленів відповідно до m = 5 і j = 5 отримуємо

Задані вихідні дані: n і t u або k і t u для побудови циклічного коду часто призводять до вибору завищеного значення m і як наслідок до невиправданого збільшення довжини коду. Таке положення знижує ефективність отриманого коду, тому що частина інформаційних розрядів взагалі не використовується.
Приклад. Потрібно побудувати циклічний код, що виправляє двох кратні помилки, якщо довжина інформаційної частини коду k = 40.
Згідно зі слів для примітивного коду n = 2 m -1, найближча довжина коду дорівнює 63, для якої m = 6, а r = mt u = 12. Отже, код буде мати n = 63, k = 51. Невикористаних інформаційних розрядів буде 11 (51-40).
Подібне невідповідність у ряді випадків можна усунути, застосовуючи непрімітівний код БЧХ.
Непрімітівним кодом БЧХ, виконуючим t u помилок, називається код довжини n над GF (q), для якого елементи є корінням породжує многочлена.
Тут b i-непрімітівний елемент GF (q m), а довжина коду n дорівнює порядку елемента b i.
Примітка.
Порядком елемента b i є найменше n, для якого .
Приклад. Порядок елемента b 3 поля GF (2 6) дорівнює 21, так як .
Породжує многочлен непрімітівного коду БЧХ, за аналогією з примітивним кодом, визначається з виразу - Мінімальні многочлени елементів поля GF (q m), які є корінням g (x); i - ступінь непрімітівного елемента b.
Приклад. Визначити значення g (x) для побудови непрімітівного коду БЧХ над GF (2) довжини n = 20, що виправляє двох кратні помилки.
З таблиці непрімітівних елементів GF (2 m) (див. таблицю 7 додатка) вибираємо поле, елемент b якого має порядок більший, але близький до заданого n.
Додаток
Таблиця 1
Розкладання бінома х n +1 на Непріводімие співмножники
Ступінь бінома
Послідовності ступенів коренів непріводімих співмножників
Непріводімие співмножники
7
1 2 4
3 6 5
13
15
15
01 02 04 08
03 06 12 09
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
18 вересня 1936
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) за примітивним многочлену a (z) = z 4 + z +1
У двійковому вигляді
У вигляді многочлена
У вигляді ступеня
0000
0
0
0001
1
a 0
0010
z
a 1
0100
z 2
a 2
1000
z 3
a 3
0011
z +1
a 4
0110
z 2 + z
a 5
1100
z 3 + z 2
a 6
1011
z 3 + z +1
a 7
0101
z 2 +1
a 8
1010
z 3 + z
a 9
0111
z 2 + z +1
a 10
1110
z 3 + z 2 + z
a 11
1111
z 3 + z 2 + z +1
a 12
1101
z 3 + z 2 +1
a 13
1001
z 3 +1
a 14
Таблиця 3
Елементи поля GF (16) як розширення GF (4) за примітивним многочлену f (z) = z 2 + z +2
У четвертинному вигляді
У десятковому вигляді
У вигляді многочлена
У вигляді ступеня
00
0
0
0
01
1
1
a 0
10
4
z
a 1
12
6
z +2
a 2
32
14
3z +2
a 3
11
5
z +1
a 4
02
2
2
a 5
20
8
2z
a 6
23
11
2z +3
a 7
13
7
z +3
a 8
22
10
2z +2
a 9
03
3
3
a 10
30
12
3z
a 11
31
13
3z +1
a 12
21
9
2z +1
a 13
33
15
3z +3
a 14
Таблиця 4
Елементи поля GF (4) як розширення GF (2) за примітивним многочлену f (z) = z 2 + z +1
У двійковому вигляді
У вигляді многочлена
У вигляді ступеня
У десятковому вигляді
00
0
0
0
01
1
a 0
1
10
z
a 1
2
11
z +1
a 2
3
Таблиця 6
Елементи поля GF (8) як розширення GF (2) за примітивним многочлену f (z) = z 3 + z +1
У двійковому вигляді
У вигляді многочлена
У вигляді ступеня
000
0
0
001
1
a 0
010
z
a 1
100
z 2
a 2
011
z +1
a 3
110
z 2 + z
a 4
111
z 2 + z +1
a 5
101
z 2 +1
a 6

Таблиця 7
Непрімітівние елементи поля GF (2 m)

m
GF (2 m)
b
n
1
4
GF (2 4)
b 3
5
b 5
3
2
6
GF (2 6)
b 3
21
b 7
9
b 9
7
3
8
GF (2 7)
b 3
85
b 5
51
b 15
17
b 17
15
4
9
GF (2 9)
b 7
73
5
10
GF (2 10)
b 3
341
b 11
93
b 31
33
b 33
31
6
12
GF (2 12)
b 3
1365
b 5
819
b 7
585
b 9
455
b 13
315
b 15
273
b 21
195
b 45
91
b 63
65
b 65
63

Таблиця 8
Мінімальні Непріводімие многочлени в полі GF (2 m)
2t u -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 (2 6) і b 3, порядок якого n = 21.
Так як j = 2t u -1 = 2 (2-1 = 3, то вираз для g (x) матиме вигляд
де f 3 (x) і f 9 (x) - мінімальні многочлени елементів b 3 та b 9 поля GF (2 6).
Значення цих многочленів наступні:


Вирази для f 3 (x) і f 9 (x) можна визначити з таблиці мінімальних многочленів, використовуючи для цього параметр m вибраного поля GF (2 m) і порядкові номери співмножників g (x).
Для розглянутого прикладу m = 6, а порядкові номери рівні 3 і 9. Тому
.

ЛІТЕРАТУРА
1. Лідовскій В.І. Теорія інформації. - М., «Вища школа», 2002р. - 120с.
2. Метрологія та радіовимірювань в телекомунікаційних системах. Підручник для ВУЗів. / В. І. Нефедов, В. І. Халкин, Є. В. Федоров та ін - М.: Вища школа, 2001 р . - 383с.
3. Цапенко М.П. Вимірювальні інформаційні системи. -. - М.: Енергоатом издат, 2005. - 440С.
4. Зюко А.Г. , Кловський Д.Д., Назаров М.В., Фінк Л.М. Теорія передачі сигналів. М: Радіо і зв'язок, 2001 р . -368 С.
5. Б. Скляр. Цифрова зв'язок. Теоретичні основи та практичне застосування. Вид. 2-е, испр.: Пер. з англ. - М.: Видавничий дім «Вільямс», 2003 р . - 1104 с.
Додати в блог або на сайт

Цей текст може містити помилки.

Комунікації, зв'язок, цифрові прилади і радіоелектроніка | Реферат
132.9кб. | скачати


Схожі роботи:
Коди без пам`яті Коди Хаффмена Коди з пам`яттю
Коди Фібоначі Коди Грея
Коригувальні коди
Лінійні блокові коди
Системи числення та коди
Коди Боуза-Чоудхурі-хоквінгема
Коди Боуза Чоудхурі хоквінгема
Штрихові коди новий предмет бібліотечної технології
Розробка кодує пристрої для формування згортальної коди
© Усі права захищені
написати до нас