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

Государственное образовательное учреждение 

высшего профессионального образования 

«САНКТ-ПЕТЕРБУРГСКИЙ 

ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ 

им. проф. М. А. БОНЧ-БРУЕВИЧА» 

В. М. Охорзин 

МАТЕМАТИЧЕСКИЕ МЕТОДЫ ТЕО-

РИИ СЕТЕЙ СВЯЗИ И ПЕРЕДАЧИ 

ДАННЫХ  

(ЦИКЛИЧЕСКИЕ КОДЫ)  

КОНТРОЛЬНАЯ РАБОТА 

СПбГУТ ))) 

САНКТ-ПЕТЕРБУРГ 

2017 

УДК 621.391.254(076.5) 
ББК З88-01я73 

О92 

Рецензент 

доктор технических наук, профессор Н. В. Савищенко (ВАС) 

Рекомендовано к печати 

редакционно-издательским советом университета 

 
О92 

Охорзин В. М.  
Математические  методы  теории  сетей  связи  и  передачи  данных 
(Циклические  коды):  контрольная  работа  /  В. М. Охорзин.  –  СПб.  : 
Изд-во «Теледом» ГОУВПО СПбГУТ, 2017. – 58 с. 
 

Содержатся  теоретический  материал  по  алгебраическим  основам 

циклических кодов и вопросы, выносимые на упражнения по дисциплине 
«Математические  методы  теории  сетей  связи  и  передачи  данных».  При-
водятся задачи и примеры решения типовых задач, контрольные вопросы, 
а также необходимая литература. Предназначается для бакалавров по на-
правлению 11.03.02 и студентов, обучающихся по всем техническим спе-
циальностям.  

УДК 621.391.254(076.5) 

ББК З88-01я73 

© 

Охорзин В. М

.

, 2017 

© Государственное образовательное учреждение  
высшего профессионального образования 
«Санкт-Петербургский государственный  
университет телекоммуникаций  
им. проф. М. А. Бонч-Бруевича», 2017 

1. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ,  

ИСПОЛЬЗУЕМЫЕ ДЛЯ ПОСТРОЕНИЯ  

И АНАЛИЗА СВОЙСТВ ГРУППОВЫХ КОДОВ 

1.1. Основные определения 

В дискретных каналах  связи  информация передается  с помощью  не-

которого числа символов q, составляющих ограниченный набор, называе-
мым полем. Поля с конечным числом символов q называют полями Галуа 
и обозначают  GF(q). Число q выбирают как степень некоторого простого 
числа p: q=p

m

.  

При  этом  поле  для  m=1 – GF(p)  –  называют  простым,  а  для  m>1  – 

GF(p

m

) – расширенным или расширением степени m основного поля GF(p). 

В случае q=2 имеет место двоичный канал с символами «0» и «1». 

Для передачи сообщений источника элементы поля объединяют в ко-

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

Некоторое множество векторов называется линейным кодом, если оно 

является подпространством всех n-последовательностей. 

Для  двоичных  линейных  кодов,  у  которых  n-последовательности  со-

держат  в  качестве  символов  «0»  и  «1»,  общепринято  название  групповой 
код. Такое название обусловлено тем, что совокупность векторов линейно-
го векторного пространства образует алгебраическую систему, называемую 
группой.  

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

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

Алгебраические  системы  –  это  абстрактные  системы,  которые  под-

чиняются определенным правилам и законам, формулируемым в виде ак-
сиом [1–3].  

Применительно  к  двоичному  каналу  группа  –  это  система,  в  которой 

задана одна из двух возможных операций – сложение (аддитивная группа) 
или  умножение  (мультипликативная  группа)  по  модулю  2  и  выполняются 
аксиомы А1–А4. 

В  кольце  и  поле  определены  две  операции  –  сложение  и  умножение. 

При  этом  элементы  кольца  по  операции  сложения  должны  удовлетворять 
всем групповым аксиомам А1–А5, т. е. образуют абелеву группу, а по опе-
рации умножения – А1 и А2; в поле все элементы образуют абелеву группу 
по сложению, а все ненулевые элементы – абелеву группу по умножению. 
В  кольце  и  поле  элементы  можно  складывать  и  умножать,  значит,  в  этих 
системах должна удовлетворяться аксиома А6.  

Аксиомы, определяющие алгебраические системы [1] 

А1. Замкнутость. Операция может быть применена к любым 

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

А2. Ассоциативный закон. Для любых трех элементов a, b и c 

группы  (a+b)+c=a+(b+c),  если  заданная  операция  –  сложение,  или 
a

·(bc)=(ab)·c, если заданная операция – умножение. 

А3. Наличие единичного элемента. Если задана операция сло-

жения,  то  единичный  элемент  есть  0  и  определяется  из  уравне-
ния  0+a=a+0=a,  где  a  –  любой  элемент  группы.  При  операции  ум-
ножения, единичный элемент есть 1 и определяется из уравнения 
1

·a=a·1=a. 

А4.  Существование  обратных  элементов.  Для  каждого  эле-

мента  группы  a  существует  обратный  элемент.  Обратный  эле-
мент  для  операции  сложения  (–a)  определяется  из  уравнения  
a+(

–a)= (–a)+a=0. При операции умножения обратный элемент (a

–1

) 

определяется уравнением aa

–1

=a

–1

a=1.  

А5. Коммутативный закон. Если для элементов группы по за-

данной операции удовлетворяется a+b = b+a или ab=ba для опера-
ций сложения и умножения соответственно, то группа называет-
ся абелевой или коммутативной. 

А6.  Дистрибутивный  закон.  Правило  раскрытия  скобок: 

a(b+c) = ab+

аc. 

Кольцо  называется коммутативным,  если  коммутативна  операция  ум-

ножения,  то  есть  для  любых  двух  элементов  кольца  a  и  b  выполняется 
ab=ba. 

Полем называется коммутативное кольцо, в котором по операции ум-

ножения имеются единичный элемент и обратные элементы для всех нену-
левых элементов. 

Содержание  определений  группы,  кольца  и  поля  отображается 

табл. 1.1.  

Таблица 1.1 

Аксиома 

Система 

группа 

кольцо 

поле 

Операции 

« + » или « × » 

« + » и « × » 

« + » и « × » 

А1. Замкнутость 

+ 

+             + 

+             + 

А2. Ассоциативность 

+ 

+             + 

+            + 

А3. Единичный эле-

мент 

+ 

                     + 

+            + 

А4. Обратный эле-

мент 

+ 

                     + 

+             + 

А5. Коммутативность  Абелева группа              + 

+             + 

А6. Дистрибутивность 

– 

+ 

+ 

Наименьшее  число  элементов,  образующих  поле,  равно  2,  так  как  в 

поле должно быть 2 единичных элемента, а именно: 0 – относительно опе-
рации сложения и 1 – относительно операции умножения. Такое поле явля-
ется двоичным, т. е. GF(2).  

Правила сложения и умножения определены как действия по модулю 

2 и в GF(2) однозначно задаются следующими таблицами – сложения и ум-
ножения. 

+ 

0 

1 



0 

1 

0 

0 

1 

0 

0 

0 

1 

1 

0 

1 

0 

1 

Поле  GF(2)  является  простым.  Расширенное  двоичное  поле  GF(2

m

)  в 

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

2

) содержит следующие элементы: 00, 10, 01, 11. 

Операция  сложения  последовательностей  в  этом  поле  осуществляется  по-
разрядным сложением символов, стоящих на одинаковых позициях сумми-
руемых  последовательностей  с  использованием  указанной  выше  таблицы. 
Например, 00+11=11, 10+11=01 и т. д.  

Операция умножения выполняется по правилам умножения многочле-

нов,  для  этого  двоичные  последовательности  представляются  в  виде  мно-
гочленов от формальной переменной α: 

00=0, 10=1, 01= α, 11=1+α. 

Для  сохранения  разрядности  элементов  поля  GF(2

m

)  умножение  эле-

ментов  поля  производится  по  модулю  некоторого  неприводимого  много-
члена π(α) степени m. Для поля GF(2

2

) таким неприводимым многочленом 

является  π(α)=1+  α+  α

2

.  Это  единственный  неприводимый  многочлен  сте-

пени 2 над полем GF(2). 

Таблицы сложения и умножения для поля GF(2

2

) 

+ 

0 

1 

α 

1+α   

× 

0 

1 

α 

1+α   

0 
1 
α 

1+α 

0 
1 
α 

1+α 

1 
0 

1+α 

α 

α 

1+α 

0 
1 

1+α 

α 
1 
0 

0 
1 
α 

1+α 

0 
0 
0 
0 

0 
1 
α 

1+α 

0 
α 

1+α 

1 

0 

1+α 

1 
α 

Приведенные таблицы для GF(2) и GF(2

2

) подтверждают выполнение 

в  этих  полях  всех  аксиом  поля,  в  том  числе  единственность  единичных и 
обратных  элементов.  Кроме  того,  можно  сделать  вывод,  что  расширенное 
поле содержит основное поле. Как для основного поля  2=0, так и для рас-
ширенного  поля  π(α)=1+α+α

2

=0,  т. е.  α  является  корнем  π(x)=1+x+x

2

.

Вто-

рым корнем π(x) является 1+α, что можно проверить прямой подстановкой. 
Очевидно, что 1+α=α

2

. Значит, все ненулевые элементы GF(2

2

) есть степе-