РЕФЕРАТ
По курсу "Теорія інформації та кодування"
на тему:
"Коди Боуз-чоудхурі-хоквінгема"

БЧХ коди
Коди Боуза-Чоудхурі-хоквінгема (БЧХ) - клас циклічних кодів, що виправляють кратні помилки, тобто дві і більше (d ₀ ³ 5).
Теоретично коди БЧХ можуть виправляти довільну кількість помилок, але при цьому істотно збільшується тривалість кодової комбінації, що призводить до зменшення швидкості передачі даних і ускладнення приймально-передавальної апаратури (схем кодерів та декодерів).
Методика побудови кодів БЧХ відрізняється від звичайних циклічних, в основному, вибором визначального полінома P (х). Коди БЧХ будуються по заданій довжині кодового слова n і числа виправляє помилок S, при цьому кількість інформаційних розрядів k не відомо поки не обраний визначає поліном.
Розглянемо процедуру кодування з використанням коду БЧХ на конкретних прикладах.
Приклад Побудувати 15-розрядний код БЧХ, що виправляє дві помилки в кодової комбінації (тобто n = 15, S = 2).
Рішення:
1. Визначимо кількість контрольних m та інформаційних розрядів k
m £ h S.
Визначимо параметр h з формули
n = 2 ^h -1, h = log ₂ (n +1) = log ₁₆ лютого = 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 ₁ (x) = 10011;
M ₂ (x) = 11111.
При цьому
P (x) = M ₁ (x) × M ₂ (x) = 10011'11111 = 111010001 = x ⁸ + x ⁷ + x ⁶ + x ⁴ +1.
4. Будуємо твірну матрицю. Записуємо перший рядок утворює матриці, яка складається з утворює полінома з попередніми нулями, при цьому загальна довжина кодової комбінації дорівнює n = 15. Решта рядки матриці отримуємо в результаті k-кратного циклічного зсуву праворуч ліворуч першого рядка матриці.

Рядки твірної матриці представляють собою 7 кодових комбінацій коду БЧХ, а інші можуть бути отримані шляхом підсумовування за модулем 2 всіляких поєднань рядків матриці.
Процедура декодування, виявлення та виправлення помилок у прийнятої кодової комбінації така ж, як і для циклічних кодів з d ₀ <5
Приклад Побудувати 31-розрядний код БЧХ, що виправляє три помилки в кодової комбінації (тобто n = 31, S = 3).
Рішення:
1. Визначимо кількість контрольних розрядів m та інформаційних розрядів k.
m £ h S.
Визначимо параметр h з формули
n = 2 ^h -1, h = log ₂ (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.
1. Вибір утворює многочлена.

З таблиці для мінімальних многочленів для кодів БЧХ (додаток 4) з колонки 5 (т. к. l = h = 5) вибираємо три мінімальні многочлена 1, 3 і 5 (тому що r = 5):
M ₁ (x) = 100 101;
M ₂ (x) = 111 101;
M ₃ (x) = 110111.
При цьому
P (x) = M ₁ (x) × M ₂ (x) × M ₃ (x) = 1000111110101111 =
= X ¹⁵ + x ¹¹ + x ¹⁰ + x ⁹ + x ⁸ + x ⁷ + x ⁵ + x ³ + x ² + x + 1.
4. Будуємо твірну матрицю. Записуємо перший рядок утворює матриці, яка складається з утворює полінома з попередніми нулями, при цьому загальна довжина кодової комбінації дорівнює n = 31. Решта рядки матриці отримуємо в результаті k-кратного циклічного зсуву праворуч ліворуч першого рядка матриці.
000000000000000100011111011111
G (31,16) = 000000000000001000111110111110
. . .
100011111011111000000000000000
Рядки твірної матриці являють собою 16 кодових комбінації коду БЧХ, а інші можуть бути отримані шляхом підсумовування за модулем 2 всіляких поєднань рядків матриці.

Декодування кодів БЧХ
Коди БЧХ представляють собою циклічні коди і, отже, до них застосовуються будь-які методи декодування циклічних кодів. Відкриття кодів БЧХ призвело до необхідності пошуку нових алгоритмів і методів реалізації кодерів і декодерів. Отримано істотно кращі алгоритми, спеціально розроблені для кодів БЧХ. Це алгоритми Пітерсона, Берлекемпа та ін

Розглянемо алгоритм ПГЦ (Пітерсона-Горенстейна-Цірлера). Нехай БЧХ код над полем GF (q) довжини n і з конструктивним відстанню d задається породжує полиномом g (x), який має серед своїх коренів елементи $\ Beta ^ {l_0}, \ beta ^ {l_0 +1}, \ ldots, \ beta ^ {l_0 + d-2} \ quad \ beta \ in GF (q ^ m), \ quad \ beta ^ n = 1$ , $\ Quad l_0$ - Ціле число (наприклад 0 або 1). Тоді кожне кодове слово володіє тим властивістю, що $c (\ beta ^ {l_0-1 + j}) = 0, \ quad j = 1,2, \ ldots, d-1$ . Прийняте слово r (x) можна записати як r (x) = c (x) + e (x), де e (x) - поліном помилок. Нехай відбулося $u \ leqslant t = (d-1) / 2$ помилок на позиціях $i_1, i_2, \ ldots, i_u$ (T максимальне число виправляє помилок), значить $e (x) = e_ {i_1} x ^ {i_1} + e_ {i_2} x ^ {i_2} + \ ldots + e_ {i_u} x ^ {i_u}$ , А $e_ {i_1}, e_ {i_2}, \ ldots, e_ {i_u}$ - Величини помилок.

Можна скласти j-ий синдром Sj прийнятого слова r (x):
$S_j = r (\ beta ^ {l_0-1 + j}) = e (\ beta ^ {l_0-1 + j}), \ quad j = 1, \ ldots, d-1 \ quad \ quad (1)$ .
Завдання полягає в знаходжень числа помилок u, їх позицій $i_1, i_2, \ ldots, i_u$ та їх значень $e_ {i_1}, e_ {i_2}, \ ldots, e_ {i_u}$ при відомих синдромах Sj.
Припустимо, для початку, що u точно дорівнює t. Запишемо (1) у вигляді системи нелінійних рівнянь в явному вигляді:

${\ Begin {cases} S_1 = e_ {i_1} \ beta ^ {l_0 i_1} + e_ {i_2} \ beta ^ {l_0 i_2} + \ dots + e_ {i_t} \ beta ^ {l_0 i_t} \ \ S_2 = e_ {i_1} \ beta ^ {(l_0 +1) i_1} + e_ {i_2} \ beta ^ {(l_0 +1) i_2} + \ dots + e_ {i_t} \ beta ^ {(l_0 +1) i_t} \ \ \ cdots \ cdots \ cdots \ cdots \ cdots \ cdots \ cdots \ \ S_ {d-1} = e_ {i_1} \ beta ^ {(l_0 + d-2) i_1} + e_ {i_2} \ beta ^ {(l_0 + d-2) i_2} + \ dots + e_ {i_t} \ beta ^ {(l_0 + d-2) i_t} \ \ \ end {cases}}$
Позначимо через $X_k = \ beta ^ {i_k}$ локатор k-ої помилки, а через $Y_k = e_ {i_k}$ величину помилки, $k = 1, \ ldots, t$ . При цьому всі Xk різні, так як порядок елемента β дорівнює n, і тому при відомому Xk можна визначити ik як ik = logβXk.
${\ Begin {cases} S_1 = Y_1 X_1 ^ {l_0} + Y_2 X_2 ^ {l_0} + \ dots + + Y_t X_t ^ {l_0} \ \ S_2 = Y_1 X_1 ^ {l_0 +1} + Y_2 X_2 ^ {l_0 +1} + \ dots + + Y_t X_t ^ {l_0 +1} \ quad \ quad \ quad \ quad \ quad \ quad (2) \ \ \ cdots \ cdots \ cdots \ cdots \ cdots \ cdots \ cdots \ \ S_ {d-1} = Y_1 X_1 ^ {l_0 + d-2} + Y_2 X_2 ^ {l_0 + d-2} + \ dots + + Y_t X_t ^ {l_0 + d-2} \ end {cases}}$
Складемо поліном локаторів помилок:
$\ Lambda (x) = (1-xX_1) (1-xX_2) \ dots (1-xX_t) = \ Lambda_t x ^ t + \ Lambda_ {t-1} x ^ {t-1} + \ dots + \ Lambda_1 x + 1$
Корінням цього полінома є елементи, зворотні локатора помилок. Помножимо обидві частини цього полінома на $Y_l X_ {l} ^ {\ vartheta + t}$ . Отримане рівність буде справедливо для
$\ Vartheta = l_0, l_0 +1, \ dots, l_0 + d-1, \ quad l = 1, \ ldots, t$ :
$\ Lambda (x) Y_l X_ {l} ^ {\ vartheta + t} = \ Lambda_t x ^ t Y_l X_ {l} ^ {\ vartheta + t} + \ Lambda_ {t-1} x ^ {t-1} Y_l X_ {l} ^ {\ vartheta + t} + \ dots + \ Lambda_1 x Y_l X_ {l} ^ {\ vartheta + t} + Y_l X_ {l} ^ {\ vartheta + t} \ quad (3)$
Покладемо $x = X_l ^ {-1}$ і підставимо в (3). Вийде рівність, справедливе для кожного $l \ in {1,2 ,..., t}$ і при всіх $\ Vartheta \ in {l_0, l_0 +1, \ dots, l_0 + d-1}$ :
$0 = \ Lambda_t Y_l X_ {l} ^ {\ vartheta} + \ Lambda_ {t-1} Y_l X_ {l} ^ {\ vartheta +1} + \ dots + \ Lambda_ {1} Y_l X_ {l} ^ { \ vartheta + t-1} + Y_l X_ {l} ^ {\ vartheta + t}$
Таким чином для кожного l можна записати свою рівність. Якщо їх просумувати по l, то вийти рівність, справедливе для кожного
$\ Vartheta \ in {l_0, l_0 +1, \ dots, l_0 + d-1}$ :
$0 = \ Lambda_t \ sum_ {l = 1} ^ t Y_l X_ {l} ^ {\ vartheta} + \ Lambda_ {t-1} \ sum_ {l = 1} ^ t Y_l X_ {l} ^ {\ vartheta + 1} + \ dots + \ Lambda_ {1} \ sum_ {l = 1} ^ t Y_l X_ {l} ^ {\ vartheta + t-1} + \ sum_ {l = 1} ^ t Y_l X_ {l} ^ {\ vartheta + t}$ .
Враховуючи (2) і те, що
$S_ {j + p} = \ sum_ {l = 1} ^ t Y_l X_ {l} ^ {l_0 + j + p-1} = \ sum_ {l = 1} ^ t Y_l X_ {l} ^ {\ vartheta + p}, \ quad j = 1, \ ldots, d-1, \ quad \ vartheta = l_0 + j-1,$
(Тобто $\ Vartheta$ змінюється в тих же межах, що і раніше) отримуємо систему лінійних рівнянь:
${\ Begin {cases} S_1 \ Lambda_t + S_2 \ Lambda_ {t-1} + \ dots + S_t \ Lambda_1 =-S_ {t +1} \ \ S_2 \ Lambda_t + S_3 \ Lambda_ {t-1} + \ dots + S_ {t +1} \ Lambda_1 =-S_ {t +2} \ quad \ quad \ quad \ quad \ quad \ quad (4) \ \ \ cdots \ cdots \ cdots \ cdots \ cdots \ cdots \ cdots \ \ S_t \ Lambda_t + S_ {t +1} \ Lambda_ {t-1} + \ dots + S_ {2t-1} \ Lambda_1 =-S_ {2t} \ end {cases}}$
.
Або в матричній формі
$S ^ {(t)} \ bar \ Lambda ^ {(t)} = - \ bar s ^ {(t)}$ ,
Де
$S ^ {(t)} = {\ left [\ begin {matrix} S_1 & S_2 & \ dots & S_t \ \ S_2 & S_3 & \ dots & S_ {t +1} \ \ \ cdots & \ cdots & \ cdots & \ \ S_t & S_ {t +1} & \ dots & S_ {2t-1} \ end {matrix} \ right]}, \ quad \ quad \ quad \ quad \ quad \ quad (5)$
$\ Bar \ Lambda ^ {(t)} = {\ left [\ begin {matrix} \ Lambda_t \ \ \ Lambda_ {t-1} \ \ \ cdots \ \ \ Lambda_1 \ end {matrix} \ right]}, \ quad \ quad \ bar s ^ {(t)} {\ left [\ begin {matrix} S_ {t +1} \ \ S_ {t +2} \ \ \ cdots \ \ S_ {2t} \ end {matrix} \ right]}$
Якщо число помилок і справді одно t, то система (4) можна залагодити, і можна знайти значення коефіцієнтів $\ Lambda_ {1}, \ ldots, \ Lambda_ {t}$ . Якщо ж число u <t, то визначник матриці S (t) системи (4) буде дорівнює 0. Це є ознака того, що кількість помилок менше t. Тому необхідно скласти систему (4), припускаючи число помилок рівним t - 1. Вирахувати визначник нової матриці S (t - 1) і т. д., до тих пір, поки не встановимо справжнє число помилок.
Після цього можна вирішити систему (4) і отримати коефіцієнти полінома локаторів помилок. Його коріння (елементи, зворотні локатора помилок) можна знайти простим перебором по всіх елементах поля GF (qm). До них знайти елементи, зворотні по множенню, - це локатори помилок $X_k, \ quad k = 1, \ ldots, u$ . За локатора можна знайти позиції помилок (ik = logβXk), а значення Yk помилок з системи (2), прийнявши t = u. Декодування завершено.
Коди Ріда-Соломона
Широко використовуваним підмножиною кодів БЧХ є коди Ріда-Соломона, які дозволяють виправляти пакети помилок. Пакет помилок довжини b є послідовністю таких b помилкових символів, що перший і останній з них відмінні від нуля. Існують класи кодів Ріда-Соломона, що дозволяють виправляти багаторазові пакети помилок.

Коди Ріда-Соломона широко використовуються в пристроях цифрового запису звуку, в тому числі на компакт-диски. Дані, що складаються з відліків об'єднуються в кадр, який представляє кодове слово. Кадри розбиваються на блоки по 8 біт. Частина блоків є контрольними.

Зазвичай 1 кадр (кодове слово) = 32 символу даних +24 сигнальних символу +8 контрольних біт = 256 біт.

Сигнальні символи це допоміжні дані, що полегшують декодування: службові сигнали, сигнали синхронізації і т. д.

При передачі даних проводиться перемеженіє (зміна порядку проходження по довжині носія і в часі) блоків з різним зсувом у часі, в результаті чого розчленовуються здвоєні помилки, що полегшує їх локалізацію та корекцію. При цьому використовуються коди Ріда-Соломона з мінімальним кодовою відстанню d ₀ = 5.

Сверточних коди
Крім розглянутих коригувальних кодів використовуються так звані сверточних коди, контрольні біти, в яких формуються безперервно з інформаційних і контрольних біт суміжних блоків.

Висновки
Таким чином, в результаті написання реферату, прийшли до висновку, що коди Боуза-Чоудхурі-Хоквінгхема - це широкий клас циклічних кодів, здатних виправляти багаторазові помилки.
БЧХ-коди відіграють помітну роль в теорії та практиці кодування. Інтерес до них визначається наступним: коди БЧХ мають дуже хороші властивості; дані коди мають відносно прості методи кодування і декодування; коди Ріда-Соломона є широко відомим підкласом Недвійкова БЧХ кодів, які володіють оптимальними властивостями, і застосовуються для виправлення багатократних пакетів помилок.
Список використаної літератури
1. Блейхут Р. Теорія і практика кодів, контролюючих помилки = Theory and practice of error control codes. - М.: Світ, 1986. - С. 576
2. Дмитрієв В.І. Прикладна теорія інформації: Підручник для вузів. М.: Вища школа, 1989. 320 c.
3. Колесник В.Д., Полтирев Г.Ш. Курс теорії інформації. - М.: Наука, 1982.
4. Кудряшов Б.Д. Теорія інформації. Підручник для вузів Вид-во ПИТЕР, 2008. - 320с.
5. Пітерсон У., Уелдон Е. Коди, що виправляють помилки. - М.: Світ, 1976. - С. 596.
6. Семенюк В. В. Економне кодування дискретної інформації. - СПб.: СПб ГІТМО (ТУ), 2001
7. У. Петерсон, Е. Уелдон, Коди, що виправляють помилки, Москва, "Світ", 1976.
8. Е. Берлекемп, Алгебраїчна теорія кодування, Москва, "Світ", 1971.

Коди Боуза Чоудхурі хоквінгема

Зазвичай 1 кадр (кодове слово) = 32 символу даних +24 сигнальних символу +8 контрольних біт = 256 біт.

Сигнальні символи це допоміжні дані, що полегшують декодування: службові сигнали, сигнали синхронізації і т. д.