3.5. Декодирование двоичных бчх кодов

Главной идеей в декодировании БЧХ кодов является использование элементов конечного поля для нумерации позиций кодового слова (или, эквивалентно, в порядке коэффициентов ассоциированного многочлена). Такая нумерация показана на Рисунке 20 для вектора r = (r₀, r₁ ,..., r_n-1), соответствующего многочлену r(x).

Позиции ошибок могут быть найдены из решения системы уравнений в поле GF(2^m). Эти уравнения можно получить, вводя многочлен ошибок е(х) и учитывая нули кода а ^j для b ≤ j < b + 2t_d - 1, как показано ниже.

Пусть r(x) = v(x) + е(х) представляет полином, ассоциированный с принятым словом, где многочлен ошибок определен как

(3.14)

где v ≤ t_d число ошибок в принятом слове. Множества

и

называют значениями ошибок и локаторами ошибок, соответственно, где e_j {0, 1} для двоичных БЧХ⁵ кодов и GF(2^m).

Рис. 20. Нумерация позиций кодового слова элементами поля GF(2^m)

Синдромы определены как значения принятого полинома r(х) в нулях кода:

Это определение эквивалентно s = Нr , где проверочная матрица Н определена в (3.13).

Введем многочлен локаторов ошибок

(3.15)

корни которого равны обратным величинам локаторов ошибок. Тогда справедливо следующее соотношение между коэффициентами многочлена локаторов ошибок и синдромами:

(3.16)

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

1. Алгоритм Берлекемпа-Мэсси (ВМА) Этот алгоритм был предложен Берлекемпом и Мэсси. По числу операций в конечном поле этот алгоритм обладает высокой эффективностью. ВМА обычно используется для программной реализации или моделирования кодов БЧХ и PC.

2. Евклидов алгоритм (еа)

Из-за высокой регулярности структуры этого алгоритма его широко используют для аппаратной реализации декодеров БЧХ и PC кодов.

3. Прямое решение

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

3.5.1. Общий метод декодирования для бчх кодов

На Рисунке 21 показана блок-схема декодера БЧХ кодов (как двоичных, так и недвоичных). Декодер состоит из логических схем и обрабатывающих блоков, реализующих следующие задачи:

• Вычислить синдромы, вычисляя значения принятого полинома в нулях кода

(3.17)

• Найти коэффициенты многочлена локаторов ошибок σ(х).

Рис. 21 Архитектура БЧХ декодера

Рис. 22. Пример схемы вычисления синдрома.

• Найти обратные величины корней σ(х), т.е. позиции ошибок j₁, j₂, …, j;

• Найти значения ошибок (этап ненужный для двоичных кодов);

• Исправить принятое слово на вычисленных позициях для вычисленных значений ошибок.

Одним из преимуществ использования арифметики над конечным полем GF(2^m) является возможность применения относительно простых логических схем и вычислительных блоков. Например, на Рисунке 22 показана схема вычисления синдромов S_j. Умножение в поле GF(2^m) также реализуется относительно простой логической схемой.