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

 

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 і, як наслідок цього, до невиправданого збільшення довжини коду. ............