РЕФЕРАТ
По курсу "Теорія інформації та кодування"
на тему:
"Коди Боуз-чоудхурі-хоквінгема"
БЧХ коди
Коди Боуза-Чоудхурі-хоквінгема (БЧХ) - клас циклічних кодів, що виправляють кратні помилки, тобто дві і більше (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 16 лютого = 4,
при цьому: m £ h S = 4 × 2 = 8; k = nm = 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 = 111 010 001 = 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 лютого 1932 = 5,
при цьому: m £ h S = 5 × 3 = 15; k = nm = 31-15 = 16.
Таким чином, отримали (31, 16)-код.
2.Визначте параметри утворює полінома:
- Кількість мінімальних многочленів, що входять до створюючий
L = S = 3;
порядок старшого мінімального многочлена
r = 3S-1 = 5;
ступінь утворює многочлена
b = m £ 15.
Вибір утворює многочлена.
З таблиці для мінімальних многочленів для кодів БЧХ (додаток 4) з колонки 5 (т. к. l = h = 5) вибираємо три мінімальні многочлена 1, 3 і 5 (тому що r = 5):
M 1 (x) = 100 101;
M 2 (x) = 111 101;
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) можна залагодити, і можна знайти значення коефіцієнтів . Якщо ж число u <t, то визначник матриці S (t) системи (4) буде дорівнює 0. Це є ознака того, що кількість помилок менше t. Тому необхідно скласти систему (4), припускаючи число помилок рівним t - 1. Вирахувати визначник нової матриці S (t - 1) і т. д., до тих пір, поки не встановимо справжнє число помилок.
Після цього можна вирішити систему (4) і отримати коефіцієнти полінома локаторів помилок. Його коріння (елементи, зворотні локатора помилок) можна знайти простим перебором по всіх елементах поля GF (qm). До них знайти елементи, зворотні по множенню, - це локатори помилок . За локатора можна знайти позиції помилок (ik = logβ Xk), а значення Yk помилок з системи (2), прийнявши t = u. Декодування завершено.
Коди Ріда-Соломона
Широко використовуваним підмножиною кодів БЧХ є коди Ріда-Соломона, які дозволяють виправляти пакети помилок. Пакет помилок довжини b є послідовністю таких b помилкових символів, що перший і останній з них відмінні від нуля. Існують класи кодів Ріда-Соломона, що дозволяють виправляти багаторазові пакети помилок.
Коди Ріда-Соломона широко використовуються в пристроях цифрового запису звуку, в тому числі на компакт-диски. Дані, що складаються з відліків об'єднуються в кадр, який представляє кодове слово. Кадри розбиваються на блоки по 8 біт. Частина блоків є контрольними.
Зазвичай 1 кадр (кодове слово) = 32 символу даних +24 сигнальних символу +8 контрольних біт = 256 біт.
Сигнальні символи це допоміжні дані, що полегшують декодування: службові сигнали, сигнали синхронізації і т. д.
При передачі даних проводиться перемеженіє (зміна порядку проходження по довжині носія і в часі) блоків з різним зсувом у часі, в результаті чого розчленовуються здвоєні помилки, що полегшує їх локалізацію та корекцію. При цьому використовуються коди Ріда-Соломона з мінімальним кодовою відстанню d 0 = 5.
Сверточних коди
Крім розглянутих коригувальних кодів використовуються так звані сверточних коди, контрольні біти, в яких формуються безперервно з інформаційних і контрольних біт суміжних блоків.
Висновки
Таким чином, в результаті написання реферату, прийшли до висновку, що коди Боуза-Чоудхурі-Хоквінгхема - це широкий клас циклічних кодів, здатних виправляти багаторазові помилки.
БЧХ-коди відіграють помітну роль в теорії та практиці кодування. Інтерес до них визначається наступним: коди БЧХ мають дуже хороші властивості; дані коди мають відносно прості методи кодування і декодування; коди Ріда-Соломона є широко відомим підкласом Недвійкова БЧХ кодів, які володіють оптимальними властивостями, і застосовуються для виправлення багатократних пакетів помилок.
Список використаної літератури
Блейхут Р. Теорія і практика кодів, контролюючих помилки = Theory and practice of error control codes. - М.: Світ, 1986. - С. 576
Дмитрієв В.І. Прикладна теорія інформації: Підручник для вузів. М.: Вища школа, 1989. 320 c.
Колесник В.Д., Полтирев Г.Ш. Курс теорії інформації. - М.: Наука, 1982.
Кудряшов Б. Д. Теорія інформації. Підручник для вузів Вид-во ПИТЕР, 2008. - 320с.
Пітерсон У., Уелдон Е. Коди, що виправляють помилки. - М.: Світ, 1976. - С. 596.
Семенюк В. В. Економне кодування дискретної інформації. - СПб.: СПб ГІТМО (ТУ), 2001
У. Петерсон, Е. Уелдон, Коди, що виправляють помилки, Москва, "Світ", 1976.
Е. Берлекемп, Алгебраїчна теорія кодування, Москва, "Світ", 1971.