Конечные поля в телекоммуникационных приложениях. Теория и применение FEC, CRC, M-последовательностей

КОНЕЧНЫЕ ПОЛЯ 

В ТЕЛЕКОММУНИКАЦИОННЫХ 

ПРИЛОЖЕНИЯХ.

ТЕОРИЯ И ПРИМЕНЕНИЕ FEC, CRC

И M-ПОСЛЕДОВАТЕЛЬНОСТЕЙ

Å.Ã. ÂËÀÑÎÂ

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

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

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

202

Власов Е.Г.

Конечные поля в телекоммуникационных приложениях. Теория 

и применение FEC, CRC и M-последовательностей : практи ческое пособие / Е.Г. Власов. — Москва : ИНФРА-М, 2024. — 285 с. + 
Доп. материалы [Электронный ресурс]. — (Наука и практика). — 
DOI 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

Подписано в печать 08.02.2024.

Формат 6090/16. Печать цифровая. Бумага офсетная.

Гарнитура Newton. Усл. печ. л. 17,82.

ППТ12. Заказ  № 00000

ТК 459350-2136566-211215

ООО «Научно-издательский центр ИНФРА-М»

127214, Москва, ул. Полярная, д. 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

Отпечатано в типографии ООО «Научно-издательский центр ИНФРА-М»

127214, Москва, ул. Полярная, д. 31В, стр. 1

Тел.: (495) 280-15-96, 280-33-86. Факс: (495) 280-36-29

Материалы, отмеченные знаком 
, доступны 

в электронно-библиотечной системе Znanium

Предисловие

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

является специалистом в области телекоммуникаций или как минимум знаком
с основными технологиями современной цифровой связи.
Все рассмотренные примеры основаны на международных нормативных документах в области телекоммуникаций. В основном это уже упомянутые рекомендации ITU-T, а также несколько стандартов международного Института инженеров электротехники и электроники (Institute of Electrical and Electronics Engineers, IEEE). Эти две ветви нормативных документов, по сути, полностью перекрывают область стандартизации повсеместно используемых систем цифровой
связи.
Следует отметить, что несмотря на термин «рекомендации» документы ITU-T
для производителей телекоммуникационного оборудования всего мира давно
приобрели статус стандартов. Дело в том, что полноправные стандарты Американского национального института стандартов (American National Standards Institute, ANSI) и Европейского института телекоммуникационных стандартов (European 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.