5.4. Решение ключевого уравнения

При декодировании как во временной, так и в частотной области, приходится находить многочлен локаторов ошибок как многочлен наименьшей степени, для которого выполнено ключевое уравнение (5.20). Кроме того, при декодировании во временной области требуется также определить многочлен значений ошибок Если интерпретировать как многочлен, задающий обратные связи в линейном регистре сдвига (см. рис. 5.3), то решение ключевого уравнения эквивалентно нахождению регистра сдвига с обратными связями наименьшей длины, который производит первые 21 членов многочлена синдрома. Позднее будет показано, что оба подхода оказываются полезными.

В первых опубликованных процедурах решения ключевого уравнения использовались стандартные методы обращения матриц. Однако позднее Берлекэмп предложил простую итеративную схему, которая в настоящее время используется в большинстве практических применений [2]. Недавно было показано, что решение можно также получить с помощью алгоритма Евклида [45]. Одно из привлекательных качеств этого алгоритма состоит в том, что его понять существенно легче (чем алгоритм Берлекэмпа). Кроме того, он тесно связан с алгоритмом Берлекэмпа. Поэтому изложим оба алгоритма.

5.4.1. Алгоритм Евклида

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

Предположим, что даны два целых числа Тогда

Поскольку делит 186 и 66, оно должно делить и 54. Поскольку делит 66 и 54, оно должно делить 12. Наконец, поскольку оно делит 54 и 12, оно должно делить 6 и поэтому является наибольшим общим делителем. В процессе нахождения наибольшего общего делителя согласно алгоритму вычисляются два числа или многочлена для которых

Однако более полезным является не окончательный ответ, а промежуточные результаты. При каждой итерации вычисляются числа или многочлены такие. что

Рекуррентные соотношения между становятся ясными, если еще раз вернуться к приведенному примеру. Первое уравнение имеет, очевидно, нужный вид, так что при первой итерации алгоритма получаем

Второе уравнение в примере содержит указания на то, что происходит при второй итерации: вычитая предыдущее уравнение из уравнения получаем

Аналогично после третьей и четвертой итераций находим

соответственно. Заметим, что каждое следующее уравнение получается из двух предыдущих по формуле

где отношение двух предыдущих остатков.

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

Определим как частное от деления на т. е. положим

где - неотрицательные степени 2. Тогда

Начальными значениями являются

Алгоритм построен таким образом, что

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

Таблица 5.1. (см. скан) Пример алгоритма Евклида при

Наша задача, однако, состоит не в нахождении наибольшего общего делителя, а в решении ключевого уравнения. Связь алгоритма Евклида с этой задачей станет ясной после того, как запишем уравнение (5.31) в виде

Полагая получаем

т. е. ключевое уравнение с Таким образом, алгоритм Евклида дает последовательность решений ключевого уравнения.

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

Полагая получаем

Напомним, что при появлении ошибок для интересующего нас решения имеем Существует единственный (с точностью до постоянного множителя) многочлен которого не превышает удовлетворяющий ключевому уравнению. Кроме того, если так что то Поэтому промежуточные результаты на шаге дают единственное интересующее нас решение ключевого уравнения. Таким образом, для решения ключевого уравнения следует применять алгоритм Евклида до тех пор, пока не будет выполнено условие Приведенное описание метода решения ключевого уравнения резюмируем для кодов БЧХ, исправляющих ошибок:

1) применить алгоритм Евклида к

2) использовать начальные условия (5.34);

3) остановиться, если

4) положить

Применение данного алгоритма проиллюстрируем на двух примерах. Все арифметические операции выполняются в поле с помощью табл. 5.2.

Пример. Рассмотрим двоичный код БЧХ длиной 15, исправляющий тройные ошибки. Положим так что корнями порождающего многочлена являются элементы где а — примитивный элемент Предположим, что принятое слово имеет вид

и осуществляется декодирование во временной области. Тогда, вычисляя искомые коэффициенты синдрома по формуле (5.17), получаем

Отсюда многочлен синдрома

Таблица 5.2. (см. скан) Обычное и логарифмическое представления ненулевых элементов поля при

Начнем с Нахождение решения ключевого уравнения и многочлена локаторов ошибок с помощью алгоритма Евклида показано в табл. 5.3.

Таблица 5.3. (см. скан) Решение ключевого уравнения для задаваемого уравнением (5.41)

Заметим, что решение соответствует значению для которого Корнями полученного многочлена локаторов ошибок

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

При декодировании в частотной области многочлен локаторов ошибок используется по-другому. Многочлен указывает отводы регистра сдвига с обратными связями, с помощью которых можно получить преобразование вектора ошибок, удовлетворяющего (5.13) для заданного -компонентного блока. Так, для рассматриваемого примера (5.13) можно записать в виде

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

Беря обратное преобразование, получаем гипотетический вектор ошибки в виде

Производя указанные исправления, вновь получаем нулевое кодовое слово.

Пример. Рассмотрим код Рида-Соломона длиной 15 над полем исправляющий тройные ошибки. Корнями порождающего многочлена являются Предположим, что принятое слово имеет вид

и осуществляется декодирование во временной области. Коэффициенты синдрома можно вычислить по формуле

Полученный многочлен синдрома имеет вид

Нахождение многочленов локаторов и значений ошибок с помощью алгоритма Евклида показано в табл. 5.4. Корнями полученного многочлена локаторов ошибок

являются Для нахождения значений ошибок в по формуле (5.28) можно использовать многочлен значений ошибок

и производную

Это дает и соответствующим словом на выходе декодера будет

Таблица 5.4. (см. скан) Решение ключевого уравнения для задаваемого уравнением (5.43)

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