Циклические коды БЧХ

Коды Боуза — Чоудхури — Хоквингхема (БЧХ-коды) — в теории кодирования это широкий класс циклических кодов, применяемых для защиты информации от ошибок (см. Обнаружение и исправление ошибок). Отличается возможностью построения кода с заранее определёнными корректирующими свойствами, а именно, минимальным кодовым расстоянием. Коды Рида — Соломона являются частным случаем БЧХ-кодов.

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

Для нахождения порождающего полинома необходимо выполнить несколько этапов:

• выбрать q, то есть поле GF (q), над которым будет построен код;
• выбрать длину n кода из условия n = (q^m − 1) / s, где m, s — целые положительные числа;
• задать величину d конструктивного расстояния;

1) построить циклотомические классы элемента β = α ^s поля GF (q^m) над полем GF (q), где α — примитивный элемент GF (q^m);

2) поскольку каждому такому циклотомическому классу соответвует неприводимый полином над GF (q), корнями которого являются элементы этого и только этого класса, со степенью равной количеству элементов в классе, то выбрать таким образом, чтобы суммарная длина циклотомических классов была минимальна

3) вычислить порождающий полином , где f_i (x) — полином, соответствующий i -ому циклотомическому классу

Примитивный 2-ичный (15,7,5) код

Пусть q = 2, требуемая длина кода n = 2⁴ − 1 = 15 и минимальное расстояние . Возьмем α — примитивный элемент поля GF (16), и α,α²,α³,α⁴ — четыре подряд идущих степеней элемента α. Они принадлежат двум циклотомическим классам над полем GF (2), которым соответствуют неприводимые полиномы f ₁(x) = x ⁴ + x + 1 и f ₂(x) = x ⁴ + x ³ + x ² + x + 1. Тогда полином

g (x) = f ₁(x) f ₂(x) = x ⁸ + x ⁷ + x ⁶ + x ⁴ + 1

имеет в качестве корней элементы α,α²,α³,α⁴ и является порождающим полиномом БЧХ-кода с параметрами (15,7,5).