БЧХ
Коди Боуза — Чоудхурі — Хоквінгема (БЧХ-коди, англ. BCH code) — в теорії кодування це широкий клас циклічних кодів, що застосовуються для захисту інформації від помилок (див. Попередня корекція помилок). Окремим випадком БЧХ-кодів є Код Ріда — Соломона.
| БЧХ | |
| Названо на честь | Raj Chandra Bosed, Dijen K. Ray-Chaudhurid і Alexis Hocquenghemd |
|---|---|
| Досліджується в | теорія кодування |
| Першовідкривач або винахідник | Alexis Hocquenghemd, Raj Chandra Bosed і Dijen K. Ray-Chaudhurid |
Код винайшов в 1959 році Алексіс Гоквінгем (англ. Alexis Hocquenghem), і незалежно в 1960 році Р. Боуз (англ. Raj Chandra Bose) і Д.Рой-Чоудхурі (англ. Dijen K. Ray-Chaudhur). Код отримав свою назву БЧХ-коди (англ. BCH code) від прізвищ їх авторів.
Коди БЧХ є узагальненням кодів Гемінґа і дозволяють виправляти кратні помилки.
Методи декодування
ред.Коди БЧХ є циклічними кодами, тому до них застосовні всі методи, використовувані для декодування циклічних кодів. Однак існують набагато кращі алгоритми, розроблені саме для БЧХ-кодів.
Головною ідеєю в декодуванні БЧХ кодів є використання елементів скінченного поля для нумерації позицій кодового слова (або, еквівалентно, в порядку коефіцієнтів асоційованого многочлена).
Декодування
ред.Декодер, що працює по авторегресивному спектральному методу декодування, послідовно виконує наступні дії:
- Обчислює синдром помилки
- Будує поліном помилки
- Знаходить корені даного полінома
- Визначає характер помилки
- Виправляє помилки
Обчислення синдрому помилки
ред.Обчислення синдрому помилки виконується синдромним декодером, який ділить кодове слово на породжувальний многочлен. Якщо виникає залишок, то у слові є помилка. Залишок від ділення є синдромом помилки.
Побудова полінома помилки
ред.Обчислений синдром помилки не вказує на становище помилок. Ступінь полінома синдрому дорівнює 2t, що багато менше ступеня кодового слова n. Для отримання відповідності між помилкою і її положенням у повідомленні будується поліном помилок. Поліном помилок реалізується за допомогою алгоритму Берлекемпа — Мессі, або за допомогою алгоритму Евкліда. Алгоритм Евкліда має просту реалізацію, але вимагає великих витрат ресурсів. Тому частіше застосовується більш складний, але менш затратний алгоритм Берлекемпа - Мессі. Коефіцієнти знайденого полінома безпосередньо відповідають коефіцієнтам помилкових символів у кодовому слові.
Знаходження коренів
ред.На цьому етапі шукаються корені полінома помилки, що визначають положення спотворених символів в кодовому слові. Реалізується за допомогою процедури Ченя, повним перебором. У поліном помилок послідовно підставляються всі можливі значення, коли поліном звертається в нуль — корені знайдені.
Визначення характеру помилки і її виправлення
ред.По синдрому помилки і знайденим кореням полінома за допомогою алгоритму Форні визначається характер помилки і будується маска спотворених символів.
Після того як маска знайдена, вона накладається на кодове слово за допомогою операції XOR і спотворені символи відновлюються. Після цього відкидаються перевірочні символи і виходить відновлене інформаційне слово.
Див. також
ред.Посилання
ред.- Електронні системи: навчальний посібник / Й. Й. Білинський, К. В. Огороднік, М. Й. Юкиш. — Вінниця: ВНТУ, 2011. — 208 с.
- Гоккенгем, А. (September 1959), Codes correcteurs d'erreurs, Chiffres (фр.), Paris, 2: 147—156
- Бос, Р. Ч.; Рой-Чоудхурі, Д. К. (March 1960), On A Class of Error Correcting Binary Group Codes (PDF), Information and Control, 3 (1): 68—79, doi:10.1016/s0019-9958(60)90287-4, ISSN 0890-5401, архів (PDF) оригіналу за 9 жовтня 2022
