РЕФЕРАТ
По курсу "Теорія інформації та кодування"
на тему:
"КОДИ Боуз-Чоудхурі-хоквінгема"
БЧХ коди
Коди Боуза-Чоудхурі-хоквінгема (БЧХ) - клас циклічних кодів, які виправляють кратні помилки, тобто дві і більше ( d 0 Ві 5).
Теоретично коди БЧХ можуть виправляти довільну кількість помилок, але при цьому істотно збільшується тривалість кодової комбінації, що призводить до зменшенню швидкості передачі даних і ускладнення приймально-передавальної апаратури (Схем кодерів і декодерів).
Методика побудови кодів БЧХ відрізняється від звичайних циклічних, в основному, вибором визначального полінома P (х). Коди БЧХ будуються по заданій довжині кодового слова n і числа виправляються помилки S , при цьому кількість інформаційних розрядів k не відомо поки не обраний визначає поліном.
Розглянемо процедуру кодування з використанням коду БЧХ на конкретних прикладах.
Приклад Побудувати 15-розрядний код БЧХ, що виправляє дві помилки в кодової комбінації (тобто n = 15, S = 2 ).
Рішення:
1. Визначимо кількість контрольних m та інформаційних розрядів k
m ВЈ h S.
Визначимо параметр h з формули
n = 2 h -1, h = log 2 (n +1) = log 2 16 = 4,
при цьому: m ВЈ h S = 4 Г— 2 = 8 ; k = n-m = 15-8 = 7 .
Таким чином, отримали (15, 7)-код.
2. Визначимо параметри утворює полінома:
- кількість мінімальних многочленів, що входять в створюючий
L = S = 2;
- порядок старшого (всі мінімальні - непарні) мінімального многочлена r = 2S-1 = 3;
- ступінь утворює многочлена b = m ВЈ 8.
3. Вибір утворює многочлена.
З таблиці для мінімальних многочленів для кодів БЧХ (див. додаток 4) з колонки 4 (т. к. l = h = 4 ) вибираємо два мінімальних многочлена 1 і 3 (т. к. r = 3 ):
M 1 (x) = 10011;
M 2 (x) = 11111.
При цьому
P (x) = M 1 (x) Г— M 2 (x ) = 10011'11111 = 111010001 = x 8 + x 7 + x 6 + x 4 +1 .
4. Будуємо утворюючу матрицю. Записуємо перший рядок утворює матриці, яка складається з утворює полінома з попередніми нулями, при цьому загальна довжина кодової комбінації дорівнює n = 15 . Решта рядків матриці одержуємо в Внаслідок k-кратного циклічного зсуву праворуч ліворуч першого рядка матриці.
Рядки утворює матриці являють собою 7 кодових комбінацій коду БЧХ, а інші можуть бути отримані шляхом підсумовування по модулю 2 всіляких поєднань рядків матриці.
Процедура декодування, виявлення та виправлення помилок у прийнятій кодовій комбінації така ж, як і для циклічних кодів з d 0 <5
Приклад Побудувати 31-розрядний код БЧХ, що виправляє три помилки в кодової комбінації (тобто n = 31, S = 3 ).
Рішення:
1. Визначимо кількість контрольних розрядів m та інформаційних розрядів k.
m ВЈ h S.
Визначимо параметр h з формули
n = 2 h -1, h = log 2 (n +1) = log 2 32 = 5,
при цьому: m ВЈ h S = 5 Г— 3 = 15 ; k = n-m = 31-15 = 16 .
Таким чином, отримали (31, 16)-код.
2.Определить параметри утворює полінома:
- кількість мінімальних многочленів, що входять в створюючий
L = S = 3;
- порядок старшого мінімального многочлена
r = 3S-1 = 5;
- ступінь утворює многочлена
b = M ВЈ 15.
1. Вибір утворює многочлена.
З таблиці для мінімальних многочленів для кодів БЧХ (додаток 4) з колонки 5 (Т. к. l = h = 5 ) вибираємо три мінімальні многочлена 1, 3 і 5 (т. к. r = 5 ):
M 1 (x) = 100101;
M 2 (x) = 111101;
M 3 (x) = 110111.
При цьому
P (x) = M 1 (x) Г— M 2 (x ) Г— M 3 (x) = 1000111110101111 =
= x 15 + x 11 + x 10 + x 9 + x 8 + x 7 + x 5 + x 3 + x 2 + x + 1 .
4. Будуємо утворюючу матрицю. Записуємо перший рядок утворює матриці, яка складається з утворює полінома з попередніми нулями, при цьому загальна довжина кодової комбінації дорівнює n = 31 . Решта рядків матриці одержуємо в Внаслідок k-кратного циклічного зсуву праворуч ліворуч першого рядка матриці.
000000000000000100011111011111
G (31,16) = 000000000000001000111110111110
. . .
100011111011111000000000000000
Рядки утворює матриці являють собою 16 кодових комбінації коду БЧХ, а інші можуть бути отримані шляхом підсумовування по модулю 2 всіляких поєднань рядків матриці.
Декодування кодів БЧХ
Коди БЧХ являють собою циклічні коди і, отже, до них застосовні будь-які методи декодування циклічних кодів. Відкриття кодів БЧХ призвело до необхідності пошуку нових алгоритмів і методів реалізації кодерів і декодерів. Отримані істотно кращі алгоритми, спеціально розроблені для кодів БЧХ. Це алгоритми Пітерсона, Берлекемпа та ін
Розглянемо алгоритм ПГЦ (Пітерсона-Горенстейна-Цірлера). Нехай БЧХ код над полем GF (q) довжини n і з конструктивним відстанню d задається породжує поліномом g (x), який має серед своїх коренів елементи, - Ціле число (наприклад 0 або 1). Тоді кожне кодове слово має тим властивістю, що. Прийняте слово r (x) можна записати як r (x) = c (x) + e (x), де e (x) - поліном помилок. Нехай відбулося помилок на позиціях (t максимальне число виправляються помилки), значить, а - величини помилок.
Можна скласти j-ий синдром Sj прийнятого слова r (x):
.
Задача полягає в знаходжень числа помилок u, їх позицій і їх значень при відомих синдромах Sj.
Припустимо, для початку, що u в точності дорівнює t. Запишемо (1) у вигляді системи нелінійних рівнянь в явному вигляді:
Позначимо через локатор k-ой помилки, а через величину помилки,. При цьому всі Xk різні, так як порядок елемента ОІ дорівнює n, і тому при відомому Xk можна визначити ik як ik = logОІXk.
Складемо поліном локаторів помилок:
Корінням цього полінома є елементи, зворотні локатора помилок. Множитимемо обидві частини цього полінома на. Отримане рівність буде справедливо для
:
Покладемо і підставимо в (3). Вийде рівність, справедливе для кожного і при всіх:
Таким чином для кожного l можна записати свою рівність. Якщо їх просумувати по l, то вийти рівність, справедливе для кожного
:
.
Враховуючи (2) і те, що
(тобто змінюється в тих же межах, що і раніше) отримуємо систему лінійних рівнянь:
.
Або в матричній формі
,
Де
Якщо число помилок і справді одно t, то система (4) розв'язна, і можна ...