Коды Боуза — Чоудхури — Хоквингема (БЧХ)

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

В БЧХ-коде образующий полинома представляет собой произведение нескольких неприводимых полиномов – мы далее посмотрим каких.

БЧХ коды, вообще-то говоря , как и линейные циклические коды в целом не обязательно являются двоичными., то есть с символами, из которых состоит код =1 или 0.

Символами КС слова могут быть например числа вида q^m представленные в виде полиномов с недвоичными коэффициентами. Мы же рассматриваем двоичные коды, что позволяет избежать значительных усилий на знакомство с теорией полей Галуа.

В БЧХ-кодах построение образующего полинома, в основном, зависит от двух параметров: от длины кодового слова n=k+r и от числа исправляемых ошибок S.

Особенностью кода является, то что для исправления числа ошибок S>=2 еще недостаточно условия, что между комбинациями кода минимальное кодовое расстояние d_min=2*S+1. Необходимо также, чтобы длина кода n удовлетворяла условию

n = 2^h - 1, (1)

где h -любое целое число.

При этом длина кода n всегда будет нечетным числом и принимать значения: 1,3,7,15,31,63,127..и.т.д, т.е не все значения динымогут быть заданы пользователем.

Выбранная по формуле (1) величина n определяет число контрольных символов r.

r<=h*S<=log₂(n+1)*S. (2)

При решении задачи выбора допустимого числа информационных символов при заданных корректирующих свойствах удобно пользоваться таблицей, в которой приведены соотношения корректирующих и информационных разрядов для БЧХ кодов.

Построение образующего полинома G(X) производится при помощи таблицы неприводимых полиномов M(X). Образующий полином представляет собой произведение неприводимых полиномов и является их наименьшим общим кратным (НОК). Максимальный номер неприводимого полинома в их произведении

p = 2*S - 1 . (3)

Порядок полинома используется при определении числа сомножителей. Для построения G(X) используются только нечетные полиномы.

Например, при S=4 ими будут: M1(X); M3(X); M5(X); M7(X). Старший из них имеет номер p=2*S-1=7. Число их равно 4, т.е. равно числу исправляемых ошибок.

Число неприводимых полиномов, участвующих в построении образующего полинома

V = S, (4)

а старшая степень

v= h (5)

указывает строку в таблице неприводимых полиномов, из которой обычно выбирается полином для построения G(X). Для построения образующего полинома используются только нечетные полиномы степени v. Иногда допускается использование полиномов и меньшей степени. Степень образующего полинома, полученного в результате перемножения выбранных неприводимых полиномов,

b = r = v*S = h*S (6)

В общем виде G(X)=НОК[M1(X)M3(X)...Mp(X)].

Пример: Рассмотрим построение циклического кода длиной в 15 разрядов, исправляющего одну или две ошибки. Согласно (1) ,

n = 2^h - 1, откуда h=log₂(n+1) = log₂16 = 4

Число контрольных символов k, согласно (2),

r=log₂(n+1)*S=4*2=8.

Номер старшего из неприводимых полиномов, cогласно (3)

p = 2*S-1 = 2*2 -1 = 3.

Количество неприводимых полиномов, участвующих в построении образующего полинома, согласно (4),

V= S = 2,

cтаршая степень, согласно (5),

v = h = 4.

Степень образующего полинома , согласно (6),

b = r = 8.

Из таблицы неприводимых полиномов выбираем полиномы степени v=4, из них выбираем два (V=2) неприводимых полинома , номер старшего из которых равен 3(p=3), т.е. выбираем неприводимые полиномы p1 и p3 .

G(X)=M1(X)*M3(X) = 10011 * 11111 = 111010001 = X⁸+X⁷+X⁶+X⁴+1.

Число информационных разрядов

k = n - m = 15 - 8 = 7.

Первая строка образующей матрицы получается путем добавления слева от G(X) такого числа нулей, чтобы общая длина кодовой комбинации была равна n. Образующая матрица получается в результате m кратного циклического сдвига кодовой комбинации, соответствующей первой строке образующей матрицы.

0 0 0 0 0 0 1 1 1 0 1 0 0 0 1

0 0 0 0 0 1 1 1 0 1 0 0 0 1 0

0 0 0 0 1 1 1 0 1 0 0 0 1 0 0

||ОМ|| = 0 0 0 1 1 1 0 1 0 0 0 1 0 0 0

0 0 1 1 1 0 1 0 0 0 1 0 0 0 0

0 1 1 1 0 1 0 0 0 1 0 0 0 0 0

1 1 1 0 1 0 0 0 1 0 0 0 0 0 0

Остальные комбинации кода получаются путем умножения 2⁷=128 строк различных информационных слов на образующую матрицу. Таким образом, мы получили набор кодовых комбинаций для приведенного выше примера состоящего из 128 кодовых слов.