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

Рассказывается методика построения кодов, минимальное расстояние между кодовыми словами которых равно заданному числу. Математическое обосновании кодов Боуза-Чоудхури-Хоккенгема, упражнения для самопроверки. Рассматриваются циклические избыточные коды(CRC) и их применение на практике

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

Многочлен степени называется примитивным, если делится на без остатка для и не делится ни для какого меньшего значения .

Например, многочлен примитивен: он делит , но не делит при . Примитивен также многочлен - он делит , но не делит при .

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

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

Пример. Нужно построить БЧХ-код с длиной кодовых слов и минимальным расстоянием между кодовыми словами . Степень примитивного многочлена равна и сам он равен . Пусть - его корень, тогда и - также его корни. Минимальным многочленом для будет . Следовательно,

Степень полученного многочлена равна 8, следовательно, построенный БЧХ-код будет -кодом. Слово 1000100 или будет закодировано кодовым словом или 111001100000100.

Можно построить1 двоичный БЧХ-код с кодовыми словами длины и нечетным минимальным расстоянием , у которого число контрольных символов не больше .

Первый БЧХ-код, примененный на практике, был -кодом, исправляющим ошибки кратности до 5, но наиболее широкое распространение получил -код, обнаруживающий ошибки кратности до 6.

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

Упражнение 45 Найти кодирующий многочлен БЧХ-кода с длиной кодовых слов 15 и минимальным расстоянием между кодовыми словами 7. Использовать примитивный многочлен с корнем . Проверить, будут ли и корнями соответственно многочленов и .