Главная > Помехоустойчивое кодирование > Коды, исправляющие ошибки
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

6.3. Идеалы многочленов и классы вычетов

Теперь рассмотрим многочлены от одного неизвестного (или переменного) X с коэффициентами из некоторого поля

Степенью многочлена называется наибольшая степень X в слагаемом с ненулевым коэффициентом. Степень нулевого многочлена равна 0. Многочлен называется нормированным, если коэффициент при наивысшей степени X равен 1. Многочлены можно складывать и умножать обычным путем; они образуют кольцо.

Если многочлены и то говорят, что многочлен делится на многочлен или что многочлен является делителем многочлена или что многочлен является множителем для Многочлен степени который не делится ни на какой многочлен степени меньшей, чем но большей, чем 0, называется неприводимым. Наибольшим общим делителем двух многочленов называется нормированный многочлен наибольшей степени, который является делителем обоих многочленов. Говорят, что два многочлена взаимно просты, если их наибольший общий делитель равен 1.

Степень произведения двух многочленов равна сумме их степеней. Ненулевой многочлен степени 0 является элементом поля, и поэтому существует обратный ему элемент, но многочленов более высоких степеней, которые обладали бы обратными элементами, не существует. Если делится на делится на то они отличаются самое большее множителем, который является элементом поля. Это утверждзние можно проверить следующим образом. Пусть для некоторых и справедливы равенства и Тогда так как степень равна сумме степеней то степень больше или равна степени Аналогично степень равна или больше, чем степень таким образом, их степени должны быть равны. Следовательно, многочлены а имеют степень 0 и должны быть элементами поля.

Для любой пары многочленов существует единственная пара многочленов, -частное и остаток, таких, что

и степень меньше, чем степень Этот факт известен как алгоритм деления Евклида, и многочлены могут быть найдены путем обычного деления многочленов "столбиком".

В предположении, что делитель в алгоритме деления имеет первую степень, т. е. что а, можно получить несколько важных результатов. Пусть

Поскольку многочлен должен иметь степень меньшую, чем степень делителя, он должен иметь степень, равную 0, т. е. он должен быть элементом поля. Подставляя в это равенство а вместо X, найдем, что Это теорема об остатке. Далее, если т. е. если а — корень многочлена то и многочлен является множителем Этот результат известен как теорема Везу. Таким образом, каждому корню многочлена однозначно соответствует сомножитель первой степени. Поскольку степень произведения многочленов равна сумме степеней сомножителей, степень по крайней мере не меньше, чем число корней многочлена

Сходство в строении и свойствах кольца целых чисел и кольца многочленов над некоторым полем очевидно. Оба они являются частными случаями алгебраического образования, называемого евклидовым кольцом. Ниже, до разд. 6.6, приводятся в основном результаты, аналогичные теоремам разд. 6.2. Доказательства проводиться не будут, но читатель сможет сам получить их на основе доказательств разд. 6.2, заменяя слова "целое число" словом "многочлен",

выражение меньше, чем выражением "степень меньше, чем степень и введя несколько очень незначительных дополнительных изменений.

Наибольший обший делитель двух многочленов всегда может быть представлен в виде

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

Теорема 6.5. Совокупность многочленов образует идеал тогда и только тогда. когда она содержит все многочлены, кратные некоторому многочлену.

Это значит, что кольцо многочленов есть кольцо главных идеалов. Идеал, образованный всеми многочленами, кратными обозначается Кольцо классов вычетов, образованных по этому идеалу, называется кольцом многочленов по модулю

Теорема 6.6. Каждый класс вычетов по модулю многочлена степени содержит либо 0, либо многочлен степени меньшей, чем Нуль является элементом идеала, а все многочлены степеней меньших, чем принадлежат различным классам вычетов.

<< Предыдущий параграф Следующий параграф >>
Оглавление