4.2. Декодирование БЧХ-кодов

4.2.1. Основные этапы

Процедура исправления и менее ошибок для -ичного циклического кода, корнями порождающего многочлена которого

являются элементы где - элемент порядка поля впервые была предложена Питерсоном для Цирлер и Горенстейн [16] обобщили эту процедуру на случай произвольного

Пусть переданный кодовый вектор, вектор ошибок и принятый вектор. Так как то

Вместо того чтобы вычислять эти величины непосредственно по можно с помощью схемы деления, описанной в разд. 7.1.3, вначале найти остаток деления на и подставить в него элементы Вектор ошибок можно задавать, указывая положение его ненулевых компонент и значения последних. Для обозначения положения ненулевых компонент введем так называемые локаторы ошибок, а именно сопоставим компоненте элемент поля который назовем ее локатором. Каждую ненулевую компоненту вектора ошибок будем задавать с помощью пары где локатор этой компоненты, ее значение. Таким образом, если вектор ошибок имеет ненулевых компонент, то он может быть задан совокупностью пар все элементы которых различны, а элементы не равны нулю. В частности, если то и для задания вектора ошибок достаточно задать лишь локаторы. Если то в соответствии с определением

Положим

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

Дальнейшая задача заключается в том, чтобы каким-либо способом найти пары по известным величинам Основная идея решения этой задачи состоит в том, что вначале нужно попытаться найти затем локаторы и далее по локаторам с помощью

формулы (4.3) найти Для нахождения локаторов введем многочлен

где Из формулы (4.4) следует, что

Если левые и правые части последнего равенства просуммировать по от 1 до то, в частности, получим

Матрица коэффициентов

как легко проверить, может быть разложена в произведение трех матриц:

Определители первой и третьей матриц в правой части (4.6) являются определителями Вандермонда. Если все элементы различны, а кроме того, то матрица не вырождена. Таким образом, задача свелась к тому, что необходимо найти Берлекэмп [3,4, 17] предложил алгоритм одновременного нахождения и решения

уравнения (4.5). Если многочлен найден, то, подставляя в него вместо 2 последовательно элементы можно найти корни уравнения (для реализации этой процедуры можно воспользоваться методом Ченя, который будет описан в разд. 7.1.3). Далее, решая систему уравнений

можно найти (для решения этой системы можно воспользоваться методом, предложенным Форни [18]). Определитель матрицы коэффициентов последней системы уравнений является определителем Вандермонда, который в данном случае отличен от нуля. При последняя операция не нужна; следует лишь заменить символы принятого кодового вектора, соответствующие найденным локаторам ошибок на противоположные.

Если то число операций при декодировании для описанного выше алгоритма растет пропорционально

Утверждение 4.6. Матрица

является вырожденной при любом

Идея доказательства. По аналогии с выводом (4.6) матрицы можно представить в виде

Используя это разложение, можно проверить, что все матрицы являются вырожденными.

Для нахождения числа ошибок можно последовательно анализировать матрицы Как следует из утверждения 4.6, искомое равно наибольшему индексу такому, что матрица не вырождена. Этот способ нахождения использовали Питерсон [15], а также Горенстейн и Цирлер [16]. Определив таким образом они решали систему уравнений (4.5) и находили значения

Пример 4.7. Рассмотрим -БЧХ-код, исправляющий тройные ошибки, из примера 4.1. Для этого кода качестве возьмем корень примитивного многочлена Предположим, что ошибки возникли в 1, 3 и 9-й компонентах. Тогда локаторами являются Используя таблицу из задачи 2.59, получаем

Находим

Так как то, согласно лемме Система уравнений (4.5), в данном случае принимающая вид

имеет следующее решение: Следовательно,

С помощью таблицы из задачи 2.59 можно проверить, что корнями этого уравнения являются Рассмотренный код совпадает с кодом Рида—Маллера первого порядка длины 15, для которого известен простой алгоритм порогового декодирования (утверждение 4.23).

Задача 4.7. Рассмотреть декодирование двоичного циклического кода Хэмминга.

Решение. Так как то если только . В этом случае сразу определяет локатор. Поскольку код Хэмминга является вырожденным кодом, исправляющим пачки ошибок (длина пачки ошибок равна 1), то, кроме того, он может быть декодирован так, как описано в разд. 4.7.