Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике Глава 2. Арифметические операции по модулю неприводимого двоичного многочлена2.1. Более подробно об алгоритме ЕвклидаВ предыдущем разделе было показано, что для декодирования двоичных БЧХ-кодов необходимо уметь выполнять арифметические операции в поле классов вычетов по модулю неприводимого двоичного многочлена С теоретической точки зрения алгоритм Евклида позволяет доказать однозначность (с точностью до скалярных множителей) разложения многочлена над любым полем в произведение неприводимых множителей. Отсюда вытекает, что многочлен степени d ни в одном поле не может иметь более чем d корней. Последний результат важен в применении к многочлену локаторов ошибок С прикладной точки зрения алгоритм Евклида важен потому, что его модификация — метод непрерывных дробей — приводит к одной Алгоритм Евклида основан на том факте, что любой делитель элементов случае — общий делитель наибольшей степени. Единственность н. о. д. для многочленов (с точностью до постоянного множителя) будет установлена позже как следствие алгоритма деления. В обоих случаях н. о. д. обладает следующими важнейшими свойствами:
Если
Здесь
Исходя из начальной пары чисел
Так как Очевидно,
Найдем теперь последовательности
где
Следовательно, можно взять
Проделав эти выкладки, получим для и
При такой форме алгоритма сначала вычисляются Иную процедуру, избавляющую от запоминания промежуточных результатов, дает алгоритм 2.11. 2.11. Другой вариант алгоритма Евклида. Пусть заданы числа
и будем далее вычислять
При Легко проверить, что
и что
Начиная с
При
Более того, можно сделать некоторые выводы о величинах
Отметим, что в рассматриваемой процедуре на каждом шаге необходимо запоминать не более семи чисел: два Эта вариация алгоритма Евклида называется вариантом непрерывных дробей. Название это объясняется тем, что
Можно также показать, что частные
Читатель, заинтересованный в более глубоком изучении непрерывных дробей, может найти превосходное введение в эту теорию в гл. 5 книги Маккоя [1965]. Алгоритм Евклида для многочленов над полем аналогичен алгоритму Евклида для чисел. Пусть даны многочлены
где
Операция алгоритма деления (с остатком) для многочленов несколько сложнее, чем для чисел. В любом случае имеются делимое
Ясно, что
Так как многочлен Таким образом, алгоритм Евклида для многочленов состоит из нескольких шагов итераций, в каждом из которых вычисляются новое частное В алгоритме Евклида для многочленов возникает последовательность остатков, степени которых строго убывают. Значит,
Как и в случае чисел, последовательно вычисляются многочлены
Этот метод обладает тем же серьезным недостатком — он требует чрезвычайно большого объема памяти для запоминания промежуточных значений
и
Как и в случае чисел, многочлены
Так как
Из алгоритма Евклида вытекает несколько следствий. Во-первых, ясно, что любой общий делитель многочленов Так как делит и правую. По индукции можно заключить, что если неприводимый многочлен 2.14. Теорема. Любой нормированный многочлен над полем Этот результат справедлив для любого поля Так как степень произведения многочленов равна сумме их степеней то, очевидно, любой многочлен первой степени неприводим. Очевидно также, что многочлен степени d не может иметь более чем d линейных делителей. Более того, мы утверждаем, что линейный многочлен 2.15. Теорема. Многочлен степени d над полем Заметим, что теорема 2.15 неверна для многочленов с коэффициентами из кольца 2). Например, квадратный многочлен
Такая ситуация, как правило, имеет место для составных модулей. Если Таким образом, сравнение В общем случае решения сравнений по составному модулю описываются следующими утверждениями: 2.16. Китайская теорема об остатках для чисел. Для заданных простых чисел 2.17. Китайская теорема об остатках для многочленов. Для заданных неприводимых многочленов Доказательство (для многочленов). Так как многочлен Доказательство китайской теоремы об остатках для чисел полностью повторяет приведенное выше рассуждение для многочленов. Следствия из алгоритма Евклида для многочленов в основном аналогичны следствиям из алгоритма Евклида для чисел. Однако в деталях эти следствия существенно различны. Несмотря на это имеется один важный частный случай, в котором возможно построение прямого соответствия. 2.18. Теорема. Если число Доказательство. Запишем формулу геометрической прогрессии
Полагая
Таким образом, шагу алгоритма деления для чисел
Следовательно, Теоремы 2.14-2.18 очень важны, однако польза от варианта непрерывных дробей алгоритма Евклида не ограничивается этими теоретическими результатами. Он составляет также основу технической реализации одной из арифметических операций (деления), необходимых для декодирования БЧХ-кодов. Перейдем к рассмотрению этой реализации.
|
1 |
Оглавление
|