Немає перевірених версій цієї сторінки; ймовірно, її ще не перевіряли на відповідність правилам проекту.

Коди Боуза — Чоудхурі — Хоквінгема (БЧХ-коди, англ. 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