Коді БЧХ. Алгоритми кодування та декодування
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. br/>В
Із табліці мінімальніх багаточленів відповідно до m = 5 и j = 5 одержуємо
В
Задані вихідні дані: n и tu або k и tu для побудова ціклічного кодом часто призводять до Вибори завіщеного Значення m І, як наслідок цього, до невіправданого Збільшення Довжина коду. Таке положення зніжує ефективність отриманий кодом, ТОМУ ЩО частина ІНФОРМАЦІЙНИХ розрядів взагалі НЕ вікорістовується.
Приклад. Побудуємо породжуючи багаточлені для кодів БЧХ у полі GF (16), побудованому як Розширення поля GF (2). Коді повінні віправляті помилки кратності 2-7. p> У табл. 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:
В
Вийшов пород...
