Москва
ИНФРА-М
2016

КОНЕЧНЫЕ ПОЛЯ 
В ТЕЛЕКОММУНИКАЦИОННЫХ 
ПРИЛОЖЕНИЯХ.
ТЕОРИЯ И ПРИМЕНЕНИЕ FEC, CRC
И M-ПОСЛЕДОВАТЕЛЬНОСТЕЙ

Å.Ã. ÂËÀÑÎÂ

ПРАКТИЧЕСКОЕ ПОСОБИЕ

НАУКА и ПРАКТИКА

Власов Е.Г.
Конечные поля в телекоммуникационных приложениях. Тео-
рия и применение FEC, CRC и M-последовательностей : практич. 
пособие / Е.Г. Власов. — М. : ИНФРА-М, 2016. — 285 с. + Доп. ма-
териалы [Электронный ресурс; Режим доступа http://www.znanium.
com]. — (Наука и практика). — www.dx.doi.org/10.12737/16990.

ISBN 978-5-16-009437-3 (print)
ISBN 978-5-16-100542-2 (online)

Систематически изложены основные прикладные направления тео-
рии конечных полей в цифровых телекоммуникациях. Основное внима-
ние уделено связи теоретических аспектов с практическими методами 
применения конечных полей. Получены все необходимые формулы, ле-
жащие в основе синтеза и анализа устройств реализации основных при-
ложений конечных полей. Приведены примеры использования рассмо-
тренных методов и их аппаратной реализации в реальных современных 
системах цифровой связи.
Книга предназначена как для студентов телекоммуникационных ву-
зов, так и для специалистов в области цифровых систем связи по разра-
ботке кодов проверки и исправления ошибок, а также методов цифрового 
скремблирования.
УДК 512.624
ББК 32.88

УДК 512.624
ББК 32.88
 
В58

©  Власов Е.Г., 2016
ISBN 978-5-16-009437-3 (print)
ISBN 978-5-16-100542-2 (online)

В58

Подписано в печать 21.12.2015.
Формат 6090/16. Печать цифровая. Бумага офсетная.
Гарнитура Newton. Усл. печ. л. 17,82.
Тираж 500 экз. (I—120). Заказ  № 00000

ТК 459350-441970-211215

ООО «Научно-издательский центр ИНФРА-М»
127282, Москва, ул. Полярная, д. 31В, стр. 1.
Тел.: (495) 280-15-96, 280-33-86.     Факс: (495) 280-36-29.
E-mail: books@infra-m.ru                 http: //www.infra-m.ru

ФЗ 
№ 436-ФЗ
Издание не подлежит маркировке 
в соответствии с п. 1 ч. 2 ст. 1

Отпечатано в типографии ООО «Научно-издательский центр ИНФРА-М»
127282, Москва, ул. Полярная, д. 31В, стр. 1
Тел.: (495) 280-15-96, 280-33-86. Факс: (495) 280-36-29

Материалы, отмеченные знаком 
, доступны 
в электронно-библиотечной системе znanium (www.znanium.com)

Предисловие

Существует ряд тем, традиционно находящихся за гранью понимания широ-
кого круга специалистов эксплуатации систем цифровой связи. Одна из них свя-
зана с применением обширной области современной высшей алгебры, изучаю-
щей объекты, называемые конечными полями.
В настоящее время конечные поля нашли применение в цифровых телеком-
муникационных системах в трех основных направлениях: кодирование с обнару-
жением ошибок, кодирование с исправлением ошибок, а также формирование
псевдослучайных последовательностей.
Программы специальностей вузов, подготавливающих специалистов для ра-
боты в области систем связи, в той или иной мере предусматривают знакомство
с помехоустойчивыми кодами. Причем знакомство это, как правило, сугубо озна-
комительное. Однако кодам с обнаружением ошибок и псевдослучайным после-
довательностям внимание, по сути, совсем не уделяется.
Отсутствие базы знаний является причиной вопросов, возникающих при изу-
чении международных документов стандартизующих организаций. Специалисты
систем связи, сталкивавшиеся с нормативными документами, знают, о чем речь.
В частности, в рекомендациях сектора стандартизации телекоммуникаций Меж-
дународного телекоммуникационного союза (International Telecommunication Un-
ion - Telecommunication Standardization Sector, ITU-T) в разделах описания кодов
и псевдослучайных последовательностей приводятся функциональные схемы
устройств, а также соответствующие порождающие многочлены. Кажущаяся про-
стота описания указанных устройств порой совершенно сбивает с толку и наво-
дит на ошибочную мысль о том, что методы, лежащие в их основе, ничего слож-
ного под собой не имеют. Однако тот, кто хоть раз всерьез задавался этим во-
просом, знает, насколько далеко от истины это первое впечатление и как на са-
мом деле трудно добраться до «верхушек», приведенных в рекомендациях
ITU-T.
Ситуация осложняется тем, что литература, посвященная соответствующему
математическому аппарату, подчас понятна лишь специалистам чисто матема-
тических направлений. Учитывая объем новых для большинства инженеров зна-
ний, данную книгу пришлось написать в менее строгом по сравнению с классиче-
ской литературой по алгебре изложении.
В книге приводятся примеры практического применения рассмотренных ме-
тодов кодирования и генерации псевдослучайных последовательностей в сетях
обоих направлений современной цифровой связи: сетях с коммутацией каналов
и сетях с коммутацией пакетов. Однако рассмотрение основных принципов кон-
кретных технологий выходит за рамки этой книги. Предполагается, что читатель

является специалистом в области телекоммуникаций или как минимум знаком
с основными технологиями современной цифровой связи.
Все рассмотренные примеры основаны на международных нормативных до-
кументах в области телекоммуникаций. В основном это уже упомянутые реко-
мендации ITU-T, а также несколько стандартов международного Института ин-
женеров электротехники и электроники (Institute of Electrical and Electronics Engi-
neers, IEEE). Эти две ветви нормативных документов, по сути, полностью пере-
крывают область стандартизации повсеместно используемых систем цифровой
связи.
Следует отметить, что несмотря на термин «рекомендации» документы ITU-T
для производителей телекоммуникационного оборудования всего мира давно
приобрели статус стандартов. Дело в том, что полноправные стандарты Амери-
канского национального института стандартов (American National Standards Insti-
tute, ANSI) и Европейского института телекоммуникационных стандартов (Euro-
pean Telecommunications Standards Institute, ETSI) фактически полностью дубли-
руют материал рекомендаций ITU-T, касающихся той же области применения.
Это обусловлено тем, что частью стандартов становятся только самые фунда-
ментальные вещи, остальное же рекомендуется в достаточно свободной форме
(факультативно). Таким образом, не все рекомендации становятся стандартами.
Однако специалистами ITU-T разработано множество замечательных приложе-
ний, которые охотно используются производителями оборудования в факульта-
тивном порядке и существенно облегчают жизнь современным связистам.
Все возникшие вопросы по теме данной книги можно отправить автору на ад-
рес электронной почты: finfields@mail.ru.

Глава 1

Сведения о конечных полях

В основе всех рассматриваемых ниже приложений лежит единая теория, ко-
торая часто выделяется в отдельную область современной высшей (общей или
абстрактной) алгебры, - теория конечных полей.
К вопросу изучения конечных полей можно подойти разными способами. Од-
нако, поскольку конечные поля являются основной темой этой книги, мы поста-
раемся уделить им наибольшее внимание и как можно глубже раскрыть их струк-
туру.
Задавшись вопросом глубокого внедрения в структуру чего-либо, необходимо
понимать, что в своих поисках нельзя уйти дальше неких элементарных состав-
ляющих, далее уже не делимых. Примерно такую роль играют в математике тео-
рия множеств и теория чисел. Таким образом, в поисках элементарных основ ко-
нечных полей нельзя уйти дальше теории чисел и теории множеств.
Мы подойдем к вопросу так, как к нему подходят алгебраисты, и получим ко-
нечное поле, опираясь на фундаментальные понятия математики.
Собственно, можно было бы пойти куда более коротким путем. Однако в этом
случае конечные поля будут казаться «взятыми с потолка». У любознательного
читателя все равно останется ощущение недосказанности, побуждающее к даль-
нейшим поискам, которые рано или поздно приведут к тем же самым фундамен-
тальным основам из теории чисел и теории множеств.
Следует заранее предупредить читателя, что не стоит беспокоиться насчет
высокой сложности предлагаемого материала. С учетом специфики рассмотрен-
ных далее практических приложений мы постараемся изложить его более дос-
тупно по сравнению с учебниками по абстрактной алгебре [8], [13]1.
Нам также понадобятся сведения о базовых алгебраических структурах, с ко-
торых мы начнем эту главу.

1.1. Базовые алгебраические структуры

Группой называется некоторое множество с определенной для каждой пары
элементов операцией. Обычно для обозначения группы используется буква G,
а для обозначения групповой операции - символ «*» (однако возможны и другие

1 Тем не менее указанные книги рекомендуются как хороший источник более глубоких
знаний по алгебре.

обозначения). Для обозначения группы G с групповой операцией * используется
запись (G, *).
При этом должны выполняться следующие аксиомы.
1. Замкнутость. Результатом групповой операции над двумя элементами a
и b группы G является элемент c, также принадлежащий группе G.
2. Существование единичного элемента. В любой группе должен существо-
вать элемент e такой, что для любого элемента a справедливо: a*e = e*a = a.
Элемент e называется единичным элементом группы.
3. Существование обратного элемента. Для любого элемента a группы суще-
ствует элемент b такой, что a*b = b*a = e, где e - единичный элемент группы.
4. Ассоциативность. Для любых трех элементов a, b и c группы справедливо
равенство a*(b*c) = (a*b)*c.
Условие a*b = b*a, где a и b - произвольные элементы группы, выполняется
не для всех групп.
Группа называется коммутативной или абелевой группой, если выполняет-
ся дополнительная аксиома.
5. Коммутативность. Для любых a и b справедливо a*b = b*a.
Операция *, используемая в определении группы, относится к операциям, ко-
торые называются в общей алгебре бинарными.
Бинарная операция на произвольном множестве M - это правило1, по кото-
рому любым двум элементам M, взятым в определенном порядке, сопоставля-
ется элемент того же множества M.
Примером общеизвестной бинарной операции может служить правило, за-
дающее разность двух чисел на множествах ℤ, ℚ и ℝ.
Необходимо отметить, что равенства a*e = e*a = a и a*b = b*a = e в аксиомах
3 и 4 справедливы для всех групп.

Пример 1.1.1. Свойствами группы обладает, например, множество ℤ целых
чисел относительно групповой операции - арифметического сложения.

В примере 1.1.1 действию над объектами - элементами группы соответствует
групповая операция. Однако элементами групп могут быть любые объекты, под-
дающиеся аналитическому описанию. В том числе действия над объектами.

Пример 1.1.2. Пусть, например, даны три буквы, произвольно пронумерован-
ные числами 1, 2 и 3. Определим элемент группы как перестановку номеров
букв: (1 2 3) - (1 3 2). Обозначим элемент, соответствующий такой перестановке,

1 Существует и другое, более строгое определение, основанное на понятии отображе-
ния множества в множество: бинарная операция - это отображение M 2 в M. Мы рассмот-
рим вопросы, связанные с отображениями, ниже (см. подпараграф 1.2.3).

буквой a. Другим элементом группы (элементом b) может быть перестановка
(1 2 3) - (3 1 2). Из комбинаторики известно, что всего существует 3! = 6 таких пе-
рестановок. Групповая операция a*b в такой группе может быть определена как
последовательное применение перестановки, соответствующей элементу a, за-
тем перестановки, соответствующей элементу b.

Группа примера 1.1.1 является абелевой и содержит бесконечное число эле-
ментов. Группа примера 1.1.2, напротив, содержит конечное число элементов.
Группа, содержащая конечное число элементов, называется конечной груп-
пой. Число элементов конечной группы G называется порядком группы G
и обозначается как | G |.
Конечные группы представляют для нас наибольший интерес. В дальнейшем
мы будем иметь дело исключительно с конечными абелевыми группами. Группа
из примера 1.1.2 является конечной, но не абелевой. Рассмотрим теперь пример
конечной абелевой группы.

Пример 1.1.3. Определим множество наборов длины n, в качестве символов
которых выступают числа 0 и 1. Всего существует 2n таких наборов. Для задания
операции сложения элементов множества нам понадобится определение сложе-
ния по модулю 2. Сложение по модулю 2 является частным случаем сложения
по модулю q, где q - целое положительное число. К сложению по модулю q мы
еще вернемся ниже. Пока же определим сложение по модулю 2 как операцию
над числами 0 и 1, задаваемую соотношениями: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 +
+ 1 = 0.
Нетрудно заметить, что сложение по модулю 2 для чисел 0 и 1 соответствует
операции, известной в алгебре логики (булевой алгебре) под названием «исклю-
чающее или». Наряду с операциями логического сложения и умножения, исклю-
чающее или составляет основу работы цифровых устройств.
Выберем в качестве операции над парами элементов рассмотренного мно-
жества поэлементное сложение по модулю 2. Пусть, например, n = 4. Рассмот-
рим групповую операцию a*b для двух элементов a = (a1, a2, a3, a4) = 0010 и b =
= (b1, b2, b3, b4) = 1010: a*b = (a1 + b1, a2 + b2, a3 + b3, a4 + b4) = 1000 (здесь «+» оз-
начает сложение по модулю 2).
Очевидно, что в результате сложения двух наборов по модулю 2 не может
появиться набор, содержащий числа, отличные от 0 и 1. Следовательно, резуль-
тат принятой операции над любыми элементами рассматриваемого множества
принадлежит тому же множеству, а значит, выполняется условие замкнутости
относительно выбранной операции. Единичным элементом в данном случае бу-
дет набор из n нулей. По свойствам сложения по модулю 2, для любого элемен-
та a справедливо a *a = e, где e - единичный элемент, которому соответствует

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

Обычно для обозначения групповых операций абелевых групп используется
символ «·» или символ «+». Группы с обозначением групповой операции симво-
лом «·» называются мультипликативными, а группы с обозначением операции
символом «+» - аддитивными. При использовании указанных обозначений груп-
повые операции аддитивной и мультипликативной групп принято называть сло-
жением и умножением соответственно. Однако, как мы уже убедились, несмотря
на сходство обозначений и терминологии с арифметическими операциями сло-
жения и умножения, в общем случае групповая операция может не соответство-
вать обычному арифметическому сложению или умножению. Тем не менее по-
добная терминология оказывается очень удобной.
Единичный элемент аддитивной группы принято обозначать символом «0»
и называть нулем, а мультипликативной - символом «1» и называть единицей.
Элемент, обратный элементу a, в случае аддитивной группы обозначается –a
и называется обратным аддитивным элементом. Элемент, обратный элемен-
ту a, в случае мультипликативной группы обозначается a –1 и называется обрат-
ным мультипликативным элементом.
К рассмотренной в примере 1.1.3 конечной абелевой группе удобно было бы
применять терминологию аддитивной группы и использовать 0 в качестве обо-
значения единичного элемента e, так как единичным элементом группы является
нулевой набор. При этом введенную групповую операцию сложения (сложение
по модулю 2) удобно обозначать символом «+», так как в основе групповой опе-
рации, в конечном счете, лежит операция арифметического сложения.
Рассмотрим последовательность a, a *a, a *a*a, ..., где a - произвольный эле-
мент некоторой конечной группы (G, *). Пусть (G, *) = (G, ·) - мультипликативная
конечная группа. Введем обозначение a·a· ... ·a = a n, где n – 1 - число последо-
вательных групповых операций над элементом a группы. Такое обозначение
достаточно условно, так как в общем случае элементы групп не являются чис-
лами, а групповая операция мультипликативной группы в общем случае не яв-
ляется арифметическим умножением. Однако такое обозначение дает удобную
форму записи результата групповых операций над одним и тем же элементом.
Используя обозначение степени элемента мультипликативной группы, по-
следовательность a, a *a, a *a *a, ... можно записать следующим образом: a, a 2,
a 3, ... . Поскольку группа G конечна, то в силу замкнутости группы относительно

умножения такая последовательность не может быть бесконечной и при некото-
ром значении степени элемента a начнет повторяться. Очевидно, что первым
повторяющимся элементом будет исходный элемент a. Также очевидно, что по-
следний неповторяющийся элемент равен единичному элементу группы G.
Пусть a - некоторый элемент конечной группы G и c - наименьшая натураль-
ная степень элемента a, для которой выполняется равенство a c = e. Число c на-
зывается порядком элемента a конечной группы G.
Группа, все элементы которой образованы степенями одного элемента, на-
зывается циклической группой.
Очевидно, что порядок циклической группы совпадает с порядком ее элемен-
та, степени которого образуют все ненулевые элементы группы.
При определении циклической группы мы пользовались мультипликативной
терминологией. Далее, говоря о циклических группах, мы также будем использо-
вать эту терминологию, так как нас в большей степени будут интересовать муль-
типликативные циклические группы. Однако циклическая группа может быть оп-
ределена также с использованием аддитивной терминологии и обозначения a +
+ a + a + ... + a = n·a для n последовательных групповых операций.
Говоря по-простому, группа является объектом, в котором можно выполнять
сложение или умножение.
Следующей важной для нас алгебраической структурой является структура
под названием кольцо.
Кольцом называется множество с двумя определенными над его элемента-
ми бинарными операциями. Бинарные операции кольца называются сложением
и умножением и обозначаются символами «+» и «·» соответственно. Кольцо обо-
значается как R или (R, +, ·).
Для колец должны выполняться следующие аксиомы.
1. Множество элементов кольца образует абелеву группу относительно опе-
рации сложения.
2. Замкнутость. Произведение любых элементов a и b кольца также принад-
лежит этому кольцу.
3. Ассоциативность. Для любых a, b и c справедливо: a·(b·c) = (a·b)·c.
4. Дистрибутивность. Для любых a, b и c справедливо: a·(b + c) = a·b + a·c
и (b + c)·a = b·a + c·a.
Поскольку кольцо, согласно аксиоме 1, образует абелеву группу относитель-
но сложения, то сложение в кольце всегда коммутативно. Кроме того, в любом
кольце всегда существует единичный элемент относительно сложения, также со-
гласно аксиоме 1. В соответствии с терминологией абелевых групп этот элемент
называется нулем и обозначается как 0.

Единичный элемент относительно умножения существует не в любом кольце.
При этом кольцо, в котором существует единичный элемент относительно умно-
жения, называется кольцом с единицей или коммутативным кольцом. Единич-
ный элемент коммутативного кольца относительно умножения называется еди-
ницей и обозначается как 1.
Согласно аксиоме 1, каждый элемент кольца имеет обратный элемент отно-
сительно операции сложения. Обратные элементы относительно умножения мо-
гут существовать только в кольце с единицей.
В коммутативном кольце для элемента a может существовать элемент b та-
кой, что a·b = 1. Если такой элемент b существует, то он называется правым об-
ратным к a. Подобным образом, если существует элемент c такой, что c·a = 1,
то c называется левым обратным к a.
Если элемент кольца R имеет как левый обратный, так и правый обратный,
то этот элемент называется обратимым. В случае обратимого элемента оба об-
ратных элемента совпадают, а обратный элемент обратимого элемента a обо-
значается как a –1.

Пример 1.1.4. В качестве примера кольца снова можно привести множество
ℤ целых чисел, которое образует коммутативное кольцо относительно арифме-
тического сложения и умножения. Единицами такого кольца являются числа ±1.

Пример 1.1.5. Другим важным для нас примером кольца является множество
всех многочленов от x с вещественными коэффициентами. Это множество обра-
зует кольцо с единицей относительно сложения и умножения многочленов. Еди-
ницей кольца в этом случае является многочлен нулевой степени (p(x) = 1).

Можно сказать, что по сравнению с группой кольцо представляет собой объ-
ект дальнейшего развития алгебраических структур относительно операций над
их элементами. В кольце можно складывать и умножать. Логично было бы пред-
положить, что должна также существовать структура, элементы которой можно
было бы, помимо сложения и умножения, также вычитать и делить. Такой струк-
турой является поле.
Полем называется множество с двумя бинарными операциями над его эле-
ментами, называемыми сложением и умножением. При этом выполняются сле-
дующие аксиомы.
1. Множество элементов поля образует абелеву группу относительно опера-
ции сложения.
2. Множество всех ненулевых элементов поля образует абелеву группу от-
носительно операции умножения.
3. Дистрибутивный закон. Для любых a, b и c из поля справедливо равенст-
во: (a + b)·c = a·c + b·c.