7.4. КОДЫ БОУЗА-ЧОУДХУРИ-ХОКВИНГЕМА

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

Для исправления необходимо иметь длина кодовой комбинации должна удовлетворять условию:

где — всегда нечетное число.

Таблица 7.2

Величина определяет выбор числа проверочных символов и связана с и соотношением

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

где С — один из сомножителей, на которые разлагается число . Соотношения для можно свести в табл. 7.2. Из таблицы следует, например, что при длина кодовой комбинации может равняться и однако ясно, то не может быть меньше

Величина С влияет на выбор порядковых номеров специальных неприводимых многочленов (табл. 7.3), с помощью которых образующий полином кода БЧХ находится как их наименьшее общее кратное (НОК). Эти многочлены называются минимальными. Максимальный порядок определяет номер последнего из выбираемых табличных минимальных многочленов;

Порядок может быть только нечетным. Значения меняются от 1 до — нечетно). Так как образующий полином является произведением указанных нечетных минимальных многочленов, то используется для определения числа сомножителей Например, если то и нечетными минимальными многочленами будут . Старший из них имеет порядок Число сомножителей равно 6, т. е. числу исправляемых ошибок. Поэтому число минимальных многочленов, образующих равно , а старшая степень многочлена . Число I указывает колонку в таблице минимальных многочленов, из которых выбирается многочлен для построения образующего полинома.

Таблица 7.3

Степень образующего многочлена полученного в результате перемножения выбранных минимальных многочленов, равна

Таким образом, . Для конкретизации приведенной методики рассмотрим примеры.

Пример 7.12. Построить код БЧХ, исправляющий две ошибки. Длина кодовой комбинации

Согласно условию Число проверочных разрядов Порядок старшего из минимальных многочленов Число минимальных многочленов, участвующих в построении образующего полинома, , а старшая степень Степень образующего многочлена:

Из колонки 4 табл. 7.3, где расположены минимальные многочлены выбираем два минимальных многочлена, порядок старшего из которых равен , т. е. выбираем минимальные многочлены 1 и 3:

Тогда что соответствует образующему полиному Тогда параметры кода . Имеем код (15,7). Производящую матрицу этого кода можно получить шестью циклическими сдвигами исходной комбинации, соответствующей образующему полиному (см. пример 7.8).

Пример 7.13. Построить код БЧХ, исправляющий двойную ошибку, если требуемая длина кода .

1. Определяем значение m по формуле или согласно (7 15) для больших значений Так как всегда целое число, то , где [7.1] — меньшая целая часть. Отсюда так как ближайшее число, которое в сумме с 1 дает целую степень двух, есть 63.

Тогда имеем

2. Находим:

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

4 Умножаем индексы (порядки) выбранных многочленов на С и окончательно получаем порядковые номера минимальных многочленов, из которых строим образующий полином циклического кода:

Из колонки табл. 7.3 имеем

5. Так как степень образующего многочлена то уточненное число проверочных разрядов (а не 12, как в расчете на втором шаге).

Итак, Имеем код БЧХ (21, 12). Первая строка образующей матрицы этого кода имеет вид 000000000001110110011. Остальные строки находятся соответствующими циклическими сдвигами.