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

Припустимо, що в основі конструкції коду БЧХ лежить елемент

поля, можливо не примітивний. Багаточлен помилок дорівнює

,

де не більше t коефіцієнтів відрізняються від нуля. Припустимо, що насправді відбулося v помилок,

, і що цим помилкам відповідають невідомі позиції Багаточлен помилок можна записати у вигляді

де

— величина l-ї помилки (у двійковому випадку ). Ми не знаємо ні , ні ; у дійсності ми навіть не знаємо числа v. Для виправлення помилок потрібно обчислити всі ці числа. Щоб одержати компонент синдрому S1, треба знайти значення отриманого багаточлена в точці а:

Прийняті тут позначення занадто громіздкі. Для їх спрощення визначимо для всіх

, v величини помилок і локатори помилок , де l - дійсне положення l-ї помилки, а - елемент поля, асоційований із цим положенням. Тому що порядок елемента а дорівнює п, то всі локатори розглянутої конфігурації помилок різні.

У цих позначеннях

запишеться у вигляді

.

Аналогічно можна обчислити значення прийнятого багаточлена при всіх ступенях

, що входять у визначення g(х). Для визначимо синдроми формулами

Тоді одержимо наступну систему з 21 рівнянь відносно v невідомих локаторів

і v невідомих величин помилок :

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

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

Розглянемо багаточлен від х:

відомий за назвою багаточлена локаторів помилок і обумовлений як багаточлен, коріннями якого є зворотні до локаторів помилок величини

для . Отже,

Якщо коефіцієнти цього багаточлена відомі, то для обчислення локаторів помилок потрібно знайти його корінь. Тому спробуємо спочатку обчислити по заданих компонентах синдрому коефіцієнти

.

Помножимо обидві частини рівності, що визначає цей багаточлен, на

і покладемо . Тоді ліва частина звернеться в нуль, і ми одержимо

або

.

Ця рівність виконується при кожному l і при кожному j. Підсумуємо ці рівності по l від 1 до v. Для кожного j це дає

Або

Кожна сума в лівій частині останньої рівності є компонентом синдрому, так що рівняння приводиться до виду

Тому що

, то для j в інтервалі всі індекси задають відомі компоненти синдрому. Таким чином, одержуємо систему рівнянь

,

тобто систему лінійних рівнянь, що зв'язує компоненти синдрому з коефіцієнтами багаточлена

(х). Якщо матриця невироджена, то цю систему можна вирішити шляхом Рисунок 1 - Декодер Питерсона-Горенстейна-Цирлера.

Оскільки число елементів поля обмежено, звичайно найпростішим шляхом знаходження корінь багаточлена

є метод проб і помилок, відомий як процедура Ченя. Ця процедура складається просто в послідовному обчисленні для кожного j і перевірки отриманих значень на нуль. Найбільш простим способом обчислення значення в точці є схема Горнера:

.

Для обчислення

за схемою Горнера потрібно тільки v множень і v додавань.

Як приклад процедури декодування, розглянемо декодування (15,5)-коду БЧХ, що виправляє три помилки і має породжуючий багаточлен g(х) = х10 + х9 + х6 + х4 + х2 + х + 1.

Алгоритм декодування представлений на рис. 1.

Для приклада будемо вважати прийнятий багаточлен рівним v(х) = x7 + x2. Ясно, що якби відбулося не більше трьох помилок, то кодове слово повинно було б бути нульовим і v(х) = е(х), але декодер не може зробити такого висновку. Виконаємо всі кроки алгоритму декодування. Спочатку обчислимо компоненти синдрому, використовуючи арифметику в полі GF(16):

Нехай v = 3, тоді

Визначник М дорівнює нулю; отже, припускаємо v = 2. Тоді

Визначник не дорівнює нулю; отже, відбулося дві помилки. Далі,

та

отже,

Використовуючи процедуру Ченя, одержуємо розкладання

Багаточлен локаторів помилок

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