12.9. ДЕКОДИРОВАНИЕ АЛЬТЕРНАНТНЫХ КОДОВ
В данном параграфе мы опишем эффективный алгоритм декодирования альтернантных кодов, основанный на описанном в предыдущем параграфе алгоритме Евклида. Как и для кодов БЧХ, алгоритм состоит из трех этапов: этап (I) — вычисление синдрома; этап (II) — нахождение многочлена локаторов ошибок и многочлена значений ошибок с помощью алгоритма Евклида; этап (III) — вычисление локаторов и ошибок и исправление ошибок.
Так как этот метод декодирования в равной мере пригоден и для кодов БЧХ, то это восполняет пробел, оставленный в описании декодирования кодов БЧХ, данном в § 9.6.
Пусть 
альтернантный код 
над GF(q) с проверочной матрицей 
задаваемой (12.2), и с минимальным расстоянием 
где 
четно. Предположим, что произошло 
ошибок с локаторами
и со значениями
как и в § 9.6.
Этап (I) алгоритма декодирования состоит в вычислении синдрома. Синдром определяется равенством
где 
для 
Этап (II) состоит в нахождении по вычисленному синдрому многочлена локаторов ошибок
и многочлена значений ошибок
[Заметим, что это определение незначительно отличается от определения, даваемого равенством 
Эти многочлены связаны условием
где 
(Доказательство условия (12.68) совпадает с доказательством, данным в теореме 25 гл. 8.)
Итак, задача этапа (II) состоит в определении по заданному 
многочленов 
таких, чтобы выполнялось соотношение (12.68) и степень многочлена 
была наименьшей. Сравнение (12.68) заведомо имеет решение, так как мы предположили, что произошло не более чем 
ошибок. Уравнение (12.68) называется ключевым уравнением процесса декодирования.
Для решения ключевого уравнения можно использовать алгоритм Евклида из предыдущего параграфа. Действительно, из уравнения (12.63) вытекает, что
Следовательно, на этапе (II) можно воспользоваться следующим алгоритмом.
Алгоритм. Положим
и будем действовать согласно алгоритму Евклида до тех пор, пока 
достигнем такого 
что
Тогда многочлен локаторов ошибок и многочлен значений ошибок задаются соответственно равенствами
где константа 8 выбирается так, чтобы удовлетворялось условие 
и имели место соотношения:
Доказательство. Равенство (12.73) вытекает из (12.69). Неравенства 
следуют из (12.70).
То, что алгоритм приводит к правильным решениям для 
вытекает из следующей теоремы.
Теорема 16. Многочлены 
и 
задаваемые (12.71) и (12.72), являются единственным решением сравнения (12.73) при 
и наименьшей возможной степени многочлена 
Доказательство. (1). Покажем прежде всего, что если имеются два решения уравнения (12.73), скажем, 
и 
причем 
то для некоторого многочлена 
Действительно, 
Но степень многочленов в каждой из сторон этого сравнения меньше чем 
Следовательно, 
(2). Если в решении 
задаваемом (12.71) и (12.72), степень многочлена 
не является наименьшей, то из 
следует, что 
где 
также решение сравнения (12.73), а 
некоторый многочлен. Тогда из (12.63) и (12.72) имеем:
Кроме того, из (12.73) для некоторого 
Из (12.76) и (12.77) следует, что 
Но 
также делит и 
Так как 
взаимно просты (см. упражнение (22)), то 
равно константе.
Этап (III) алгоритма совпадает с этапом (III) алгоритма декодирования кодов БЧХ: локаторы ошибок находятся как величины, обратные корням многочлена 
а затем по формуле
определяются значения ошибок.
ЗАМЕЧАНИЯ К ГЛ. 12
(см. скан)
