Файл: Контрольная работа Математические методы теории сетей связи.pdf

ни корня α многочлена π(x), поэтому говорят, что расширение поля образу-
ется присоединением корней π(x) к основному полю. 

1.2. Группа, подгруппа и смежные классы 

Подмножество H элементов группы G, удовлетворяющее всем группо-

вым аксиомам, называется подгруппой.  

Обозначим элементы группы G через g

1

, g

2

, g

3

, … , а подгруппы через 

h

1

,  h

2

,  h

3

,  …  .  Рассмотрим  следующую  таблицу.  Первая  строка  состоит  из 

элементов подгруппы H, взятых по одному разу, с единичным элементом в 
начале  строки.  Первым  элементом  второй  строки  может  быть  любой  эле-
мент G, не вошедший в первую строку, а все остальные элементы получа-
ются  применением  групповой  операции  (например,  сложения)  первого 
элемента второй строки с элементами подгруппы.  

Аналогично  образуются  последующие  строки,  каждая  с  неиспользо-

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

h

1

=0, 

h

2

, 

h

3

, 

….., 

h

l 

g

1

, 

g

1

+h

2

, 

g

1

+h

3

, 

…..,  g

1

+h

l

g

2

, 

g

2

+h

2

, 

g

2

+h

3

, 

…..,  g

2

+h

l

----- 

----- 

----- 

----- 

----- 

----- 

----- 

----- 

----- 

----- 

----- 

----- 

----- 

----- 

----- 

g

m

, 

g

m

+h

2

, 

g

m

+h

3

, 

…..,  g

m

+h

l

Каждая строка в полученной таблице называется смежным классом, а 

элемент группы в начале строки называется образующим смежного класса.  

Представленное  разложение  группы  G  по  подгруппе  H  на  смежные 

классы, независимо от групповой операции, обладает следующими свойст-
вами. 

1.  В  таблице  содержатся  все  элементы  группы,  и  каждый  элемент 

группы появляется в таблице только один раз. 

2. Состав смежного класса не зависит от выбора образующего элемен-

та смежного класса. 

3. По введенной в группе операции можно ввести операцию над смеж-

ными классами, и по введенной операции смежные классы образуют новую 
группу,  элементами  которой  являются  смежные  классы  {g

i

}  (в  фигурных 

скобках указывается образующий смежного класса), а единичным элемен-
том – сама подгруппа {h

j

}. 

Действие над смежными классами выполняется следующим образом: 
сложение  {g

i

}+{g

j

}={g

z

}  означает,  что  сумма  любого  элемента  из 

смежного класса {g

j

} с любым элементом смежного класса {g

i

} находится в 

классе {g

z

}; 

умножение {g

i

}·{g

j

}={g

x

} означает, что произведение любого элемен-

та из {g

i

} с любым элементом {g

j

} находится в {g

x

}. 

Пример 1.2.1. Пусть G – группа по сложению из всех целых положи-

тельных, отрицательных чисел и нуля и H – подгруппа, состоящая из всех 
чисел, кратных двум.  

Тогда таблица разложения G по H на смежные классы состоит из двух 

строк: 

{0} 

2 

–2 

4 

–4 

6 

–6, … 

{1}  –1 

3 

–3 

5 

–5 

7, … 

где {0} – подгруппа, содержащая все числа, кратные двум, т. е. четные чис-
ла положительные и отрицательные; 

{1} – смежный класс, содержащий все нечетные положительные и от-

рицательные числа. 

Таблица сложения для смежных классов 

+ 

{0} 

{1} 

{0} 
{1} 

{0} 
{1} 

{1} 
{0} 

В этой таблице легко узнается таблица сложения по модулю 2. Число 

элементов группы называется порядком группы. 

Пример 1.2.2. Показать, что множество всех двоичных последователь-

ностей  длины  3:  000,  001,  010,  011,  100,101,  110,  111,  состоящее  из  всех 
возможных трехразрядных двоичных чисел, является группой по операции 
поразрядного сложения по модулю 2. 

Проверим выполнение групповых аксиом для заданной совокупности 

двоичных последовательностей и заданной операции. 

А1. Замкнутость. Поразрядное сложение по модулю 2 дает для суммы 

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

А2. Ассоциативность. Для введенной операции результат сложения не 

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

А3.  Наличие  единичного  элемента.  Единичным  элементом  является 

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

А4.  Существование  обратных  элементов.  Для  любой  двоичной  по-

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

А5. Коммутативный закон. Выполнение коммутативного закона под-

тверждается пояснениями в А2. 

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

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

1.3. Кольцо, идеал и классы вычетов 

В теории колец роль, аналогичную подгруппе в группе, играет понятие 

идеала. 

Идеалом I называется подмножество элементов кольца R, обладающее 

следующими двумя свойствами: 

● является подгруппой аддитивной группы кольца R; 
● для любого элемента a из I и любого элемента r из R произведение 

ar и ra принадлежит I. 

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

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

Все  свойства  смежных  классов  верны  и  для  классов  вычетов,  т. е.  их 

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

Понятие кольца и кольца классов вычетов одинаково справедливо как 

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

Для  целых  чисел  структура  идеала  и  классов  вычетов  формируется 

следующим образом:  

● совокупность целых чисел образует идеал тогда и только тогда, ко-

гда она состоит из всех чисел, кратных некоторому целому числу; 

● идеал, состоящий из всех целых чисел кратных m и самого m, лежит в 

основе кольца класса вычетов, называемого кольцом целых чисел по модулю m; 

●  каждый  класс  вычетов  по  модулю  m  содержит  либо  0,  либо  целое 

положительное  число,  не  превосходящее  m.  Нуль  является  элементом 
идеала, а все целые положительные числа, не превосходящие m, принадле-
жат различным классам вычетов. 

Рассмотрим  кольцо  целых  чисел.  Оно  имеет  бесконечное  число  эле-

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

Построим кольцо классов вычетов по модулю m=5, идеал которого со-

держит числа: 

{0}: 0, 5 ,

 – 5, ,10, – 10, 15, – 15, … 

В  качестве  образующего  первого  класса  вычетов  выберем  минималь-

ное число, не вошедшее в {0}: 

{1}: 1, 6, – 4, 11, – 9, 16, – 14, … 

В качестве образующих следующих классов вычетов возьмем числа 2, 

3, 4, при этом состав классов вычетов будет иметь вид: 

{2}: 2, 7, – 3, 12, – 8, 17, – 13, …  
{3}: 3, 8, – 2, 13, – 7, 18, – 12, …  
{4}: 4, 9, – 1, 14, – 6, 19, – 11, …  

Идеал {0} и классы вычетов {1}, {2}, {3}, {4} образуют кольцо клас-

сов вычетов по модулю 5. 

Сложение  и  умножение  чисел  в  этом  новом  кольце  будут  произво-

диться по модулю 5. 

Таблицы сложения и умножения чисел по модулю 

  + 

{0}  {1}  {2}  {3}  {4} 

  {0} 

{1} 
{2} 
{3} 
{4} 

{0} 
{1} 
{2} 
{3} 
{4} 

{1} 
{2} 
{3} 
{4} 
{0} 

{2} 
{3} 
{4} 
{0} 
{1} 

{3} 
{4} 
{0} 
{1} 
{2} 

{4} 
{0} 
{1} 
{2} 
{3} 

 
Аналогично  можно  охарактеризовать структуру  идеала  и классов  вы-

четов кольца многочленов, заменяя слова «целое число» на «многочлен». 

Будем рассматривать многочлены с коэффициентами из двоичного поля:  

f(x)=f

0

+f

1

x +f

2

x

2

 +….+f

n

 x

n

, 

где f

i

= 0,1. 

Степенью многочлена называют наибольшую степень x в слагаемом с 

ненулевым коэффициентом. Степень нулевого многочлена равна 0. Много-
член называют нормированным, если коэффициент при наивысшей степени 
x равен 1 (в двоичном поле все ненулевые многочлены нормированные). 

×  {0}  {1}  {2}  {3}  {4} 

{0} 
{1} 
{2} 
{3} 
{4} 

{0} 
{0} 
{0} 
{0} 
{0} 

{0} 
{1} 
{2} 
{3} 
{4} 

{0} 
{2} 
{4} 
{1} 
{3} 

{0} 
{3} 
{1} 
{4} 
{2} 

{0} 
{4} 
{3} 
{2} 
{1} 

В двоичном случае многочлены можно складывать, умножать и делить 

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

Порядок такого кольца бесконечен  оно имеет следующую структуру: 
1) совокупность многочленов образует идеал тогда и только тогда, ко-

гда она содержит все многочлены, кратные некоторому многочлену; 

2) идеал, состоящий из всех многочленов, кратных некоторому много-

члену  f(x),  лежит  в  основе  кольца  классов  вычетов,  называемого  кольцом 
многочленов по модулю многочлена f(x); 

3) каждый класс вычетов по модулю многочлена f(x) степени n содер-

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

В  качестве  примера  рассмотрим  кольцо  многочленов  по  модулю 

f(x)=x

2

+1. 

Идеал этого кольца и классы вычетов по модулю f(x)=x

2

+1 имеют вид: 

{0} 

x

2

+1 

(x

2

+1)x  (x

2

+1)(x+1)  … 

{1} 

x

2

x

3

+x+1 

x

3

+x

2

+x 

… 

{x} 

x

2

+x+1 

x

3

x

3

+x

2

+1 

… 

{1+х} 

x

2

+x 

x

3

+1 

x

3

+x

2

… 

Составим таблицы сложения и умножения для этого кольца. 

 
Обратим внимание, что по сложению рассматриваемое кольцо удовле-

творяет всем групповым аксиомам. 

При операции умножения  для элемента {1+x} отсутствует обратный, 

что  допустимо  для  кольца.  Сравнение  элементов  кольца  многочленов  по 
модулю f(x)=x

2

+1 с элементами расширенного поля GF(2

2

) из п. 1.1 показы-

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

Классы вычетов кольца многочленов по модулю многочлена f(x) степе-

ни n образуют кольцо многочленов по модулю f(x).Порядок этого кольца при 

+ 

  {0}       {1}        {x}      {1+x} 

{0} 
{1} 

{x} 

{1+x} 

  {0}       {1}        {x}      {1+x} 
  {1}       {0}     {1+x}       {x} 
  {x}     {1+x}      {0}        {1} 
{1+x}     {x}        {1}        {0} 

× 

{0}        {1}        {x}       {1+x} 

{0} 
{1} 

{x} 

{1+x} 

{0}        {0}        {0}         {0} 
{0}        {1}        {x}        {1+x} 
{0}        {x}        {1}        {1+x} 
{0}       {1+x}    {1+x}      {0}