|
Читайте также: |
Кольцом R называют множество элементов, на котором определены две операции – сложение a + b и умножение ab. Для того, чтобы R было кольцом оно должно удовлетворять следующим требованиям:
R.1 Множество R является абелевой группой по операции сложения (аддитивная абелева группа).
R.2 (замкнутость). Для любых двух элементов a и b из множества R определено произведение ab, которое является элементом R.
R.3 (ассоциативный закон). Для любых трех элементов a, b, и c из R a(bc)=(ab)c.
R.4 (дистрибутивный закон). Для любых трех элементов a, b, и c из множества R справедливы равенства a(b+c)=ab+ac и (b+c)a=ba+ca.
Кольцо называют коммутативным, если операция умножения коммутативна, т.е. для любых двух элементов R выполняется равенство ab=ba.
В теории групп очень важную роль играет понятие подгруппы. В теории колец соответствующую роль играет понятие идеала. Идеалом I называют подмножество элементов кольца R, обладающее следующими двумя свойствами:
1). I является подгруппой аддитивной группы кольца R;
2). Для любого элемента a из I и любого элемента r из R произведения ar и ra принадлежат I.
Поскольку идеал является подгруппой, могут быть образованы смежные классы (см. основные свойства группы). В этом случае смежные классы называют классами вычетов. Идеал образует первую строку разложения с нулевым элементом (единичным элементом по операции сложения) слева. Далее любой элемент кольца, не принадлежащий идеалу, может быть выбран в качестве образующего первого класса вычетов, а остальные элементы класса получают прибавлением образующего к каждому элементу идеала:
| 0=a1, | a2, | a3, | a4, | a5,… |
| r1=r1+a1, | r1+a2, | r1+a3, | r1+a4, | r1+a5,… |
| r2=r2+a1, | r2+a2 | r2+a3, | r2+a4, | r2+a5,… |
| ……. | ……. | ……. | ……. | ……. |
| ……. | ……. | ……. | …….. | ……. |
| ……. | ……. | ……. | ……. | ……. |
Первыми элементами в каждой строке являются, как и при построении смежных классов, элементы, не использованные в предыдущих строках.
Все свойства смежных классов верны также для классов вычетов :{r}+{s}={r+s} и умножение классов вычетов {r}{s}={rs}
В высшей алгебре доказывается, что классы вычетов по идеалу в некотором кольце образуют кольцо. Это кольцо называют кольцом классов вычетов.
В теории кодирования важную роль играют кольца целых чисел и кольца многочленов.
Основные свойства кольца:
1. Совокупность целых чисел образует идеал тогда и только тогда, когда она состоит из всех чисел, кратных некоторому целому числу.
Пусть m – наименьшее целое положительное число в идеале и s – любое другое кольцо в идеале. На основе алгоритма деления Евклида запишем выражение для наибольшего общего делителя чисел m и s:
d=am+bs,
где a и b - целые числа.
Из приведенного равенства вытекает, что d также принадлежит идеалу. Действительно, так как m – наименьшее число в идеале, то m≤d, а так как d делит m, то d≤m. Значит m=d и s кратно m.
Идеал, который состоит из всех чисел, кратных m и самого m, обозначают (m).
2. Каждый класс вычетов по модулю m содержит либо 0, либо целое положительное число, не превосходящее m. Нуль является элементом идеала, а все целые положительные числа, не превосходящие m, принадлежат различным классам вычетов.
Доказательство этого свойства основывается на рассуждениях, приведенных в примере 5.2.2.
Построенные в этом примере смежные классы являются также и классами вычетов по идеалу (2) и образуют кольцо целых чисел по модулю 2.
Сформулированные выше свойства колец целых чисел полностью справедливы и для многочленов. Сходство в строении и свойствах кольца целых чисел и кольца многочленов обусловлены тем, что оба они являются частными случаями алгебраического образования, известного как евклидово кольцо. Рассмотрим основные свойства колец многочленов, необходимые для понимания структуры циклических кодов.
3. Совокупность многочленов образует идеал тогда и только тогда, когда она содержит все многочлены кратные некоторому многочлену.
Идеал, образованный всеми многочленами, кратными f(x) обозначают (f(x)). Кольцо классов вычетов, образованных по этому идеалу, называют кольцом многочленов по модулю f(x).
4. Каждый класс вычетов по модулю многочлена f(x) степени n содержит либо 0, либо многочлен степени меньшей, чем n. Нуль является элементом идеала, а все многочлены степеней, меньших, чем n, принадлежат различным классам вычетов.
Пример 6.1. Особую роль в теории циклических кодов играет кольцо многочленов по модулю двучлена xn+1
Рассмотрим классы вычетов многочленов по модулю двучлена третьей степени – x3+1. В соответствии со свойством 4 каждый класс вычетов содержит либо 0, либо многочлен степени меньшей, чем 3. Как и ранее рассматриваем многочлены с коэффициентами в виде двоичных элементов. Приведенная ниже таблица отражает содержание классов вычетов многочленов по модулю многочлена x3+1
| {0}=000 | 1+x3 | x(1+x3) | ... |
| {1}=100 | X3 | 1+x+x4 | ... |
| {x}=010 | 1+x+x3 | x4 | ... |
| {1+x}=110 | X+x3 | 1+x4 | ... |
| {x2}=001 | 1+x2+x3 | x+x2+x4 | ... |
| {1+x2}=101 | X2+x3 | 1+x+x2+x4 | ... |
| {x+x2}=011 | 1+x+x2+x3 | x2+x4 | ... |
| {1+x+x2}=111 | X+x2+x3 | 1+x2+x4 | ... |
В левой колонке этой таблице приведены многочлены минимальной степени в своем классе вычетов. Именно они обозначают класс вычетов и поэтому взяты в фигурные скобки. Рядом с ними показано двоичном представление многочленов данного класса вычетов.
Двоичное представление класса вычетов показывает, что классы вычетов представляют собою векторное пространство размерности 3, состоящее из 8 двоичных последовательностей длины 3.
Из приведенного примера можно сделать следующий очень важный вывод: кольцо многочленов по модулю двучлена xn+1 отображает бесконечное множество многочленов на конечное n – мерное векторное пространство. При этом векторы этого пространства можно складывать и умножать по правилам сложения и умножения классов вычетов многочленов по модулю xn+1.
Кольцо многочленов по модулю двучлена xn+1, как и любое кольцо, имеет свой идеал. Как и в случае целых чисел, идеал I кольца многочленов по модулю xn+1 содержит классы вычетов, кратные некоторому классу вычетов {g(x)}, т.е. некоторый класс вычетов {s(x)}, принадлежит идеалу I тогда и только тогда, когда s(x) делится на g(x). Покажем, что g(x) при этом должен быть делителем xn+1.
Представим процесс деления xn+1 на g(x) в следующем виде:
xn+1=g(x)q(x)+r(x),
где q(x) - частное от деления, а r(x) -остаток от деления. При этом, очевидно, что степень r(x) - меньше степени g(x). Поэтому должно быть справедливо равенство:
{0}={xn+1}={g(x)}{q(x)}+{r(x)},
из которого вытекает, что класс вычетов {r(x)} также принадлежащий идеалу I. Поскольку степень r(x) меньше степени g(x), то r(x) должно быть нулевым и, следовательно, xn+1 кратен g(x).
Пример 6.2. Определим, какие идеалы существуют в кольце многочленов Примера 6.1. Рассматриваемое кольцо образуют классы вычетов многочленов по модулю x3+1. X3+1 имеет в качестве сомножителей два многочлена с двоичными коэффициентами:
x3+1=(x+1)(x2+x+1).
Следовательно, имеется два подмножества последовательностей длины 3, образующие идеалы рассматриваемого кольца. Один идеал включает все классы вычетов кратные {1+x}: {0}, {1+x}, {1+x2}, {x+x2}, отображаемые двоичными последовательностями (000), (110), (101) и (011) соответственно. Второй идеал состоит из классов вычетов {0} и {1+x+x2}, отображаемых двоичными последовательностями (000) и (111).
Представляет интерес сравнить полученные идеалы с результатами решения задач 2 и 5 из раздела 5.2.5.
5. Пусть xn+1=g(x)·h(x), где h(x)-многочлен степени k. Тогда идеал, порожденный классом вычетов {g(x)} в кольце многочленов по модулю xn+1, имеет размерность k.
Действительно, многочлен g(x), порождающий идеал, имеет степень n-k, а значит среди классов вычетов кольца многочленов по модулю xn+1 существуют классы вычетов {g(x)}, {xg(x)},… {xk-1g(x)}, отображаемые k линейно независимыми векторами. При этом любой класс вычетов может быть представлен вектором, полученным линейной комбинацией. Например, S(x) - многочлен минимальной степени в своей классе вычетов и S(x)=g(x)·q(x)=g(x)(q0+q1x+…+qk-1xk-1) и {S(x)}=q0{g(x)}+q1{xg(x)}+…+qk-1{xk-1g(x)}, т.е k векторов {g(x)}, {xg(x)},…, {xk-1g(x)} порождают идеал. Значит размерность идеала, равна k.
В примере 6.2. один из идеалов порождается векторами {g(x)}={1+x} и {xg(x)}={x+x2}, а другой – {1+x+x2}.
Многочлен g(x) минимальной степени, такой, что его класс вычетов {g(x)} принадлежит идеалу, называет порождающим многочленом идеала.
г) Понятие о конечных полях
Полем называют множество элементов, на котором определены две операции. Одна из них называется сложением и обозначается a+b, а другая – умножением и обозначается a×b, даже если эти операции не являются обычными операциями сложения и умножения чисел. Для того чтобы множество элементов, на котором заданы операции сложения и умножения, было полем, необходимо, чтобы по каждой из этих операций выполнялись все групповые аксиомы, а также выполнялся дистрибутивный закон, т.е. для трех любых элементов поля а, b, с были справедливы равенства а×(b+с)=аb+ас и (b+с)а=bа+са.
Кроме того, по каждой операции группа должна быть коммутативной, т.е. должно выполняться, а+b=b+a и аb=bа. Следует заметить, что групповые свойства по операции умножения справедливы для всех ненулевых элементов поля.
Дата добавления: 2015-08-02; просмотров: 63 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Итеративные коды. | | | Поля с конечным числом элементов q называют полями Галуа по имени их первого исследователя Эвариста Галуа и обозначают GF(q). |