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

6.4. Алгебра классов вычетов многочленов

Теорема 6.7. Классы вычетов многочленов по модулю многочлена степени образуют коммутативную линейную алгебру размерности над полем коэффициентов.

Доказательство. Умножение на скаляр определяется равенством легко проверить, что выполняются все аксиомы векторного пространства и алгебры. Например, справедливость дистрибутивного закона проверяется следующим образом;

что векторное пространство имеет размерность можно увидеть из того, что классов вычетов порождают все пространство, поскольку каждый класс вычетов содержит многочлен степени меньшей, чем и

Кроме того, эти классов вычетов линейно независимы, потому что 3 правой части соотношения (6.7) стоит произвольная линейная

комбннация классов вычетов а левая часть равна нулю, только если многочлен делится на что невозможно, или если все коэффициенты равны 0. Ч. т. д.

Обычно принято использовать многочлен минимальной степени в классе вычетов в качестве представителя этого класса вычетов, однако в этой книге использование одних и тех же обозначений для класса вычетов и многочлена минимальной степени в классе вычетов может привести к некоторой путанице. Поэтому там, где классы вычетов не обозначаются при помощи фигурных скобок, в данной книге принята следующая система обозначений. Некоторый символ, обычно 5 или а, будет использоваться для обозначения класса вычетов, содержащего Класс вычетов, содержащий элемент поля, будет обозначаться таким же символом, как этот элемент поля; это не должно стать причиной путаницы. Тогда смежный класс, который содержит многочлен есть

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

Теорема 6.8. В алгебре многочленов по модулю многочлена степени многочлен но не существует многочлена от степени меньшей, чем

Доказательство:

Аналогично, если любой многочлен степени меньшей, чем то и по теореме 6.6 этот класс вычетов не есть идеал. Ч. т. д.

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

Теорема 6.9. Пусть -идеал в алгебре многочленов по модулю и пусть отличный от нуля многочлен, наименьшей степени, такой, что класс вычетов принадлежит Тогда класс вычетов принадлежит I тогда и только тогда, когда многочлен делится на Более того, многочлен является делителем

Доказательство. В соответствии с алгоритмом деления

где имеет степень, не превосходящую степень Следовательно,

и если классы вычетов принадлежат то класс вычетов также принадлежит Так как степень не превосходит степень по предположению, ненулевой многочлен наименьшей степени, такой, что класс вычетов принадлежит I, то многочлен должен быть равен 0. Следовательно, многочлен кратен многочлену Обратно, если многочлен кратен многочлену то так что если класс вычетов принадлежит то класс вычетов также должен принадлежать

В соответствии с алгоритмом деления

где степень многочлена меньше степени Поэтому

и, значит, класс вычетов принадлежит Поскольку степень меньше степени то многочлен должен быть нулевым, и, следовательно, кратен

Теорема 6.10. Для любого идеала I в алгебре многочленов по модулю существует единственный нормированный многочлен минимальной степени, такой, что класс вычетов принадлежит идеалу . И наоборот, каждый нормированный многочлен являющийся делителем порождает некоторый идеал в которое является нормированным многочленом наименьшей степени, таким, что класс вычетов принадлежит идеалу

Доказательство. Должен существовать многочлен наименьшей степени такой, что класс вычетов принадлежит Тогда многочлен есть нормированный многочлен наименьшей степени, класс вычетов которого также принадлежит следовательно, в существует по крайней мере один нормированный многочлен минимальной степени. Предположим, что существуют два таких многочлена: Тогда по теореме 6.9 многочлен делится на и многочлен делится на и, таким образом, они отличаются самое большее на множитель, являющийся элементом поля. Поскольку, по

предположению, оба многочлена являются нормированными, этим элементом поля должна быть Следовательно, существует единственный нормированный многочлен минимальной степени класс вычетов которого принадлежит

Предположим теперь, что — нормированный многочлен, являющийся делителем и рассмотрим идеал порожденный классом вычетов т. е. идеал, содержащий все классы вычетов, кратные Пусть класс вычетов принадлежит Тогда

для некоторого и поэтому

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

Теорема 6.11. Пусть где — многочлен степени многочлен степени Тогда идеал, порожденный классом вычетов в алгебре многочленов по модулю имеет, размерность

Доказательство. В идеале, который является некоторым подпространством, векторы линейно независимы, ибо любая линейная комбинация этих векторов имеет вид и по теореме 6.6 отлична от нуля, так как каждый класс вычетов содержит "некоторый многочлен степени, меньшей Более того, если принадлежит идеалу, многочлен делится на по теореме 6.9, а если многочлен наименьшей степени в своем классе вычетов, то его степень меньше, чем Таким образом,

и

так что векторов порождают идеал. Следовательно, размерность идеала равна k. Ч. т. д.

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

Утверждения теорем 6.9 и 6.11 можно суммировать следующим образом. Каждому идеалу в алгебре многочленов по модулю

соответствует порождающий многочлен являющийся делителем и каждый нормированный многочлен, являющийся делителем многочлена порождает свой идеал. Каждый класс вычетов в идеале, порожденном многочленом содержит единственный многочлен, который делится на и степень которого меньше, чем степень многочлена и каждый такой многочлен принадлежит некоторому классу вычетов, входящему в идеал.

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

Будем говорить, что многочлен принадлежит нулевому пространству идеала если для любого многочлена из Это определение отличается от определения нулевого пространства, данного в гл. 2, потому что требования, состоящие в том, что скалярное произведение векторов равно 0 и что произведение многочленов равно 0, не совпадают. Между этими понятиями, однако, имеется очень тесная связь, если Пусть

Тогда коэффициент при в произведении с равен

Слагаемые, содержащие появляются из-за слагаемых в произведении которые содержат ведь поскольку , то Равенство для можно переписать в виде скалярного произведения:

Первый вектор — это вектор, соответствующий . Второй вектор содержит коэффициенты расположенные в обратном порядке а сдвинутые циклически на элемент вправо. Таким образом, если произведение равно нулю, то вектор, соответствующий ортогонален вектору, соответствующему

коэффициенту компоненты которого расположены в обратном порядке, и каждому циклическому сдвигу этого вектора. Обратное утверждение тоже верно: если вектор ортогонален вектору и каждому циклическому сдвигу этого вектора, то

Теорема 6.12, Пусть нормированные многочлены, и пусть Тогда класс вычетов принадлежит нулевому пространству идеала, порожденного многочленом тогда и только тогда, когда он принадлежит идеалу, порожденному многочленом

Доказательство. Если принадлежит идеалу, порожденному многочленом любой класс вычетов из идеала, порожденного то многочлен кратен и многочлен кратен а произведение кратно Следовательно, таким образом, класс вычетов принадлежит нулевому пространству идеала, порожденного многочленом Обратно, если то произведение должно быть кратно Это значит, что многочлен должен делиться на следовательно, класс вычетов принадлежит идеалу, порожденному

Примеры применения этих понятий даны в разделах 8.1 и 8.2.

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