Глава 11. Линеаризированные многочлены и аффинные многочлены
11.1. Как найти их корни
Мы видели, что часто возникает ситуация, когда декодеру необходимо знать корни многочлена
над
лежащие в этом поле. Общим методом решения этой задачи является процедура Ченя, описанная в разд. 5.4. Для больших значений числа
она требует значительного числа операций.
Однако существует специальный класс многочленов, корни которых могут быть найдены значительно проще. Эти многочлены впервые исследовались
[1933, 1934], который назвал их
-многочленами, но мы в силу причин, которые станут ясными из теоремы 11.12, будем называть их линеаризированными многочленами.
11.11. Определение. Многочлен
над
называется линеаризированным, если
Если
стандартный базис поля
то отсюда получим важное утверждение.
11.12. Теорема. Пусть
линеаризированный многочлен и
где
тогда
Используя для элементов
стандартные выражения, получаем, что
Следовательно, коэффициенты разложения многочлена
по стандартному базису могут быть получены путем умножения вектор-строки
на
-матрицу над
Рассмотрим, например, многочлен
над
где
— корень примитивного неприводимого двоичного многочлена
Используя приведенные в приложении А таблицы логарифмов и антилогарифмов, получаем, что
так что X — двоичная
-матрица вида
Если, например, необходимо найти корни многочлена
то это эквивалентно уравнению
что равносильно системе линейных двоичных уравнений
Эта система может быть решена с помощью методов, описанных в разд. 2.5. Ее решения — это
. Следовательно,
корни многочлена (10.62) в
; другие два корня лежат в
Многочлен (10.62) получается путем вычитания из линеаризированного многочлена константы. Многочлены такого вида мы будем называть аффинными.
11.13. Определение. Многочлен
над
называется аффинным, если
и, где
линеаризированный многочлен,
Как было видно из примера, корни произвольного аффинного многочлена над
лежащие в поле
могут быть найдены