Коди Боуза — Чоудхурі — Хоквінгема (БЧХ-коди, ) — в теорії кодування це широкий клас циклічних кодів, що застосовуються для захисту інформації від помилок (див. Попередня корекція помилок). Окремим випадком БЧХ-кодів є Код Ріда — Соломона.
Код винайшов в 1959 році Алексіс Гоквінгем (), і незалежно в 1960 році Р. Боуз () і Д.Рой-Чоудхурі (). Код отримав свою назву БЧХ-коди () від прізвищ їх авторів.
Коди БЧХ є узагальненням кодів Гемінґа і дозволяють виправляти кратні помилки.
Методи декодування
Коди БЧХ є циклічними кодами, тому до них застосовні всі методи, використовувані для декодування циклічних кодів. Однак існують набагато кращі алгоритми, розроблені саме для БЧХ-кодів.
Головною ідеєю в декодуванні БЧХ кодів є використання елементів скінченного поля для нумерації позицій кодового слова (або, еквівалентно, в порядку коефіцієнтів асоційованого многочлена).
Декодування Декодер, що працює по авторегресивному спектральному методу декодування, послідовно виконує наступні дії:
Обчислює синдром помилки Будує поліном помилки Знаходить корені даного полінома Визначає характер помилки Виправляє помилки
Обчислення синдрому помилки Обчислення синдрому помилки виконується синдромним декодером, який ділить кодове слово на породжувальний многочлен. Якщо виникає залишок, то у слові є помилка. Залишок від ділення є синдромом помилки.
Побудова полінома помилки Обчислений синдром помилки не вказує на становище помилок. Ступінь полінома синдрому дорівнює 2t, що багато менше ступеня кодового слова n. Для отримання відповідності між помилкою і її положенням у повідомленні будується поліном помилок. Поліном помилок реалізується за допомогою алгоритму Берлекемпа — Мессі, або за допомогою алгоритму Евкліда. Алгоритм Евкліда має просту реалізацію, але вимагає великих витрат ресурсів. Тому частіше застосовується більш складний, але менш затратний алгоритм Берлекемпа - Мессі. Коефіцієнти знайденого полінома безпосередньо відповідають коефіцієнтам помилкових символів у кодовому слові.
Знаходження коренів На цьому етапі шукаються корені полінома помилки, що визначають положення спотворених символів в кодовому слові. Реалізується за допомогою процедури Ченя, повним перебором. У поліном помилок послідовно підставляються всі можливі значення, коли поліном звертається в нуль — корені знайдені.
Визначення характеру помилки і її виправлення По синдрому помилки і знайденим кореням полінома за допомогою алгоритму Форні визначається характер помилки і будується маска спотворених символів.Після того як маска знайдена, вона накладається на кодове слово за допомогою операції XOR і спотворені символи відновлюються. Після цього відкидаються перевірочні символи і виходить відновлене інформаційне слово.
Див. також Виявлення та виправлення помилок
Посилання Електронні системи: навчальний посібник / Й. Й. Білинський, К. В. Огороднік, М. Й. Юкиш. — Вінниця: ВНТУ, 2011. — 208 с.