Реферат: Коди БЧХ. Алгоритми кодування та декодування

1 КОДИ БОУЗА-ЧОУДХУРИ-ХОКВИНГЕМА

Коди Боуза-Чоудхури-Хоквингема (БЧХ) являють собою великий клас кодів, здатних виправляти кілька помилок і займають помітне місце в теорії і практиці кодування. Інтерес до кодів БЧХ визначається щонайменше наступними чотирма обставинами:

1) серед кодів БЧХ при невеликих довжинах існують гарні (але, як правило, не кращі з відомих) коди;

2) відомі відносно прості й конструктивні методи їх кодування і декодування (хоча якщо єдиним критерієм є простота, то перевага варто віддати іншим кодам);

3) коди Ріда-Соломона, що є широко відомим підкласом недвійкових кодів, мають певні оптимальні властивості і прозору вагову структуру;

4) повне розуміння кодів БЧХ, як видно, є найкращою відправною крапкою для вивчення багатьох інших класів кодів.

2 ВИЗНАЧЕННЯ КОДІВ БЧХ

Одним із класів циклічних кодів, здатних виправляти багатократні помилки, є коди БЧХ.

Примітивним кодом БЧХ, що виправляє 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), то

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

По заданій довжині коду 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, мінімальні багаточлени елементів відповідають мінімальному багаточлену і т.і.

Приклад. Визначити значення породжуючого багаточлена для побудови примітивного коду над GF(2) довжини 31, що забезпечує tu=3. Визначаємо значення m і j.

Із таблиці мінімальних багаточленів відповідно до m=5 і j=5 одержуємо

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

Приклад. Побудуємо породжуючий багаточлени для кодів БЧХ у полі GF(16), побудованому як розширення поля GF(2). Коди повинні виправляти помилки кратності 2-7.

У табл. 1 задане подання поля GF(16), як розширення поля GF(2), побудоване по примітивному багаточлену . В неї включені також мінімальні багаточлени GF(2) для всіх елементів з поля GF(16), де — примітивний елемент GF(16). Помітно, що мінімальні багаточлени для будь-якого парного ступеня завжди вже існують в одному з попередніх рядків таблиці. Породжуючий багаточлен для коду БЧХ довжини 15, що виправляє дві помилки:

Оскільки ступінь g(х) дорівнює 8, п — k = 8. Звідси k = 7 і ми одержали породжуючий багаточлен (15, 7)-коду БЧХ, що виправляє 2 помилки. Відзначимо, що коди БЧХ будуються по заданим п и t. Значення k не відомо, поки не знайдений g (х).

Таблиця 1 – Подання поля GF(24)

Тим же способом ми можемо побудувати багаточлен, що породжує, для іншого примітивного коду БЧХ довжини 15

Нехай t = 3:

Вийшов породжуючий багаточлен для (15, 5)-коду БЧХ, що виправляє три помилки. Нехай t = 4:

.

Вийшов породжуючий багаточлен для (15,1)-коду БЧХ. Це простий код з повторенням, що виправляє сім помилок.

Нехай t = 5, 6, 7. Кожний із цих випадків приводить до такого ж породжуючого багаточлена, як і при t = 4. При t > 7 код БЧХ не визначений, оскільки ненульових елементів поля GF(16) усього 15.

В табл. 6.2 наведене подання поля GF(16), як розширення поля GF(4), побудоване по примітивному багаточлену . Ця таблиця містить також мінімальні багаточлени над GF(4) для всіх елементів з поля GF(16), де = z — примітивний елемент.

Приклад. Знайдемо породжуючи багаточлени для кодів БЧХ, що виправляють від 1-й до 6 помилок у кодовій комбінації. Код повинен бути побудований у поле GF(16) отриманому як розширення поля GF(4). Породжуючий багаточлен для коду БЧХ над GF(4) довжини 15, що виправляє одиночні помилки:

--> ЧИТАТЬ ПОЛНОСТЬЮ <--