Понятие о кодах Боуза-Чоудхури-Хоккенгема

Остался открытым вопрос о методике построения кодов, минимальное расстояние между кодовыми словами которых равно заданному числу. В 1960 году независимо Боуз (Bose), Чоудхури (Chaudhuri) и Хоккенгем (Hocquengem) открыли способ построения полиномиальных кодов, удовлетворяющих таким требованиям. Эти коды получили названия кодов Боуза-Чоудхури-Хоккенгема или БЧХ-кодов (BCH codes).

БЧХ-коды могут быть не только двоичными, например, на практике достаточно широко используются недвоичные коды Рида-Соломона (Reed, Solomon), но далее будут рассматриваться только двоичные.

Многочлен g(x) степени k называется примитивным, если x^j + 1 делится на g(x) без остатка для j = 2^k − 1 и не делится ни для какого меньшего значения j.

Например, многочлен 1 + x² + x³ примитивен: он делит x⁷ + 1, но не делит
x^j + 1 при j < 7. Примитивен также многочлен 1 + x³ + x⁴ — он делит x¹⁵ + 1, но не делит x^j + 1 при j < 15.

Кодирующий многочлен g(x) для БЧХ-кода, длина кодовых слов которого n, строится так. Находится примитивный многочлен минимальной степени q такой, чтоПусть а — корень этого многочлена, тогда рассмотрим кодирующий многочлен — многочлены минимальной степени, имеющие корнями соответственно

Построенный кодирующий многочлен производит код с минимальным расстоянием между кодовыми словами, не меньшим d, и длиной кодовых слов n.

Пример. Нужно построить БЧХ-код с длиной кодовых слов n = 15 и минимальным расстоянием между кодовыми словами d = 5. Степень примитивного многочлена равна q = log₂(n + 1) = 4 и сам он равен x⁴ + x³ + 1. Пусть α — его корень, тогда α² и α⁴ — также его корни. Минимальным многочленом для α³ будет
x⁴ + x³ + x² + x + 1. Следовательно,

Степень полученного многочлена равна 8, следовательно, построенный БЧХ-код будет (7,15)-кодом. Слово 1000100 или a(x) = x⁴ + 1 будет закодировано кодовым словом или 111001100000100.

Можно построить двоичный БЧХ-код с кодовыми словами длины n = 2^q − 1 и нечетным минимальным расстоянием d, у которого число контрольных символов не больше Первый БЧХ-код, примененный напрактике, был (92,127)-кодом, исправляющим ошибки кратности до 5, но наиболее широкое распространение получил (231, 255)-код, обнаруживающий ошибки кратности до 6.

БЧХ-коды умеренной длины не слишком далеки от совершенных или квазисовершенных кодов. Коды Хэмминга, например, являются БЧХ-кодами, а БЧХ-коды с минимальным весом кодового слова 5 — квазисовершенны. Но с ростом длины кодовых слов качество БЧХ-кодов падает. Код Голея, например, — это не код БЧХ.