Коди БЧХ. Алгоритмикодуваннятадекодування
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, що виправляє одиночні помилки:
/>
Цимкодом послідовність 11 чотверичних символів (що еквівалентно 22 бітам)
Таблиця 2 Подання поля GF (42)GF(4) + 0 1 2 3 * 0 1 2 3
1
2
3
0 1 2 3
1 0 3 2
2 3 0 1
3 2 1 0
1
2
3
0 0 0 0
0 1 2 3
0 2 3 1
0 3 1 2
кодується в послідовність 15 чотверичних символів. Такийкод не є кодом Хемінга.
У такий же спосіб ми можемо знайти породжуючийбагаточлени для інших кодів над GF(4) довжини 15.
Нехай t = 2:
/>
Вийшов породжуючий багаточлен для (15, 9)-коду БЧХ надGF(4), що виправляє дві помилки.
Нехай t = 3:
/>
Це дає (15, 6) -код БЧХ над GF(4), що виправляє трипомилки.
Нехай t = 4:
/>
Це дає (15, 4) -код БЧХ над GF(4), що виправляє чотирипомилки.
Нехай t == 5:
/>
Це дає (15, 3) -код БЧХ над GF (4), що виправляє п'ятьпомилок.
Нехай t = 6:
/>
Виходить (15, 1) -код БЧХ над GF(4), що виправляє шістьпомилок. Це простий код з повторенням, що у дійсності виправляє сім помилок.
Тому, що коди БЧХ є циклічними кодами, то при кодуваннівикористовуються загальні правила кодування інформації циклічними кодами.
3 Коди БЧХ. Алгоритми декодування
Коди БЧХ є циклічними, і, отже, до них застосовнібудь-які методи декодування циклічних кодів. Є, однак, істотно кращі алгоритми,розроблені спеціально для декодування кодів БЧХ. Алгоритм, що розглядається, впершебув запропонований Питерсоном для двійкових кодів. Для спрощення рівнянь усюдипокладається />=1 хоча всі викладення без зміниідеї можуть бути пророблені для довільного />.
Припустимо, що в основі конструкції коду БЧХ лежитьелемент /> поля,можливо не примітивний. Багаточлен помилок дорівнює
/>,
де не більше 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 і />.