9.7. КВАДРАТНЫЕ УРАВНЕНИЯ НАД GF(2^m)

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

В § 4.6-4.9 было показано, что в поле имеется базис вида называемый нормальным. Любой элемент поля записывается в виде

где равны 0 или 1 и след элемента

Теорема 15. Квадратное уравнение имеет два корня в если и не имеет корней в если Таким образом,

если и многочлен неприводим в поле если

Доказательство. Выпишем разложение по нормальному базису:

Если решение уравнения то, приравнивая коэффициенты при получаем:

Сложение этих равенств согласно (9.25) дает:

Следовательно, равенство является необходимым условием для того, чтобы уравнение имело решение. Это условие также достаточно, так как если то имеются два решения этого уравнения, задаваемые соответственно равенствами где или 1.

Примеры. В поле многочлен неприводим, так как . В поле многочлен неприводим, так как

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

Доказательство. Предположим, что многочлен с неприводим, причем Более того, так как в противном случае мы имеем полный квадрат. Заменяя на приводим многочлен к виду

Согласно теореме Следовательно, Применяя опять теорему 15, заключаем, что в поле найдется такой элемент что Заменяя на приводим квадратное уравнение к виду

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