Многочлен значений ошибок. Равенство (*) определяет множество из (2t–υ) уравнений и называется ключевым

Ω(x)= S (x)Λ(x) (mod x ^{2 t}), (*)

Равенство (*) определяет множество из (2 t –υ) уравнений и называется ключевым уравнением, так как оно представляется «ключом» решения задачи декодирования.

Это становится понятным, если учесть, что степень Ω(x) не превышает υ–1 и поэтому справедливо:

, (**),

где .

Из (**) можно получить υ уравнений для υ неизвестных коэффициентов Λ_k. Эти уравнения являются линейными. Они могут быть решены обычными методами либо с помощью итерационных процедур. После нахождения многочлена Λ(x) ключевое уравнение позволяет найти неизвестные компоненты вектора e (x) и по ним выходной вектор декодера: f (x)= C (x)+ e (x).

Простейшим путем нахождения корней многочлена Λ(x) является метод проб и ошибок, известный как процедура Ченя. Эта процедура состоит в последовательном вычислении Λ(α^j) для каждого j и проверки полученных значений на ноль. Если величина Λ(α^–k) равна нулю, то α^k является взаимным к корню многочлена локаторов ошибок и k -й элемент кодовой комбинации содержит ошибку. Наиболее простым способом вычисления значения Λ(x) в точке β является схема Горнера:

.

Для вычисления Λ(β) по схеме Горнера требуется только υ умножений и υ сложений, где υ – степень Λ(x).

После определения локаторов ошибок с помощью ключевого уравнения находим значения ошибок. Для этого, используя значения сомножителей, входящих в равенство для Ω(x), перепишем ключевое уравнение следующим образом:

Сворачивая выражение в квадратных скобках, получаем окончательно

Приводя это выражение по модулю x ^{2 t}, получаем

.

Вычислим многочлен значений ошибок на позиции l: .

,

Откуда

.

Найдем производную от многочлена локаторов ошибок Λ(x):

.

Для l -й позиции получаем:

.

С учетом последнего выражения Y_l значение ошибки на позиции l принимает вид

.

Рассмотренный способ декодирования позволяет найти значение ошибок по известным многочленам локаторов и значений ошибок. Он известен в литературе [ 4 ] как алгоритм Форни. Указанные многочлены вычисляются в результате решения ключевого уравнения. Более подробно декодирование кодов Рида-Соломона рассматривается в разделе 7.2.

Дата добавления: 2015-08-02