7.2. Ключевое уравнение для декодирования двоичных БЧХ-кодов

Если кодер передает слово двоичного БЧХ-кода

а шум в канале задается вектором

то полученпое слово записывается многочленом

Для кодовое слово кратно минимальному многочлену элемента следовательно,

где элементы поля Галуа локаторы ошибок Как было показано в разд. 5.2 где остаток от деления на минимальный многочлен элемента После вычисления основная задача декодера — определить из уравнений

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

Для решения системы декодер сначала пытается определить коэффициенты многочлена локаторов ошибок (7.21) (см. также уравнение

7.21. Определение

Если многочлен уже найден декодером, то, используя процедуру Ченя, можно найти взаимные корни для Ошибки после этого могут быть исправлены с помощью схемы, изображенной на рис. 5.14. Наиболее тяжелая часть этой процедуры — определение коэффициентов по величинам

Для того чтобы найти зависимость между величинами введем производящую функцию

После умножения на имеем

Прибавив к обеим частям равенства получим

Определим многочлен со с помощью равенства

Тогда

В общем случае декодеру известны коэффициенты только при первых степенях в и не известны коэффициенты Иными словами, декодер не знает но знает Поэтому естественно ввести уравнение, которое мы назовем ключевым:

Из этого уравнения по заданному нужно найти оба многочлена и степени которых не превосходят где число ошибок в канале.

Одна «физическая интерпретация» ключевого уравнения была предложена Месси [1968]. Перепишем уравнение в виде

или в виде

Последнее равенство задает выход регистров сдвига, приведенных на рис. 7,1 и 7.2, обратные связи которых соответствуют многочлену а начальное состояние ячеек — многочлену

Рис. 7.1. Интерпретация ключевого уравнения с помощью регистра сдвига с обратной связью.

Это позволяет интерпретировать ключевое уравнение как математическую постановку задачи синтеза регистра с обратной связью: по заданной выходной последовательности необходимо определить обратные связи и начальное состояние кратчайшего (наименьшего) регистра сдвига с выходной последовательностью

В задаче декодирования двоичных БЧХ-кодов реальный интерес представляет только многочлен а не многочлен Однако это же ключевое уравнение возникает и в некоторых других приложениях.

Рис. 7.2. Другая интерпретация ключевого уравнения с помощью регистра сдвига с обратной связью.

Мы вернемся к нему в гл. 9 и 10, где оно интерпретируется как задача сиптеза регистров с обратной связью, и оба неизвестных многочлена и представляют непосредственный интерес.

Рассмотрим теперь алгоритм решения ключевого уравнения над произвольным полем.