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

НАУКА и ПРАКТИКА
Е.Г. ВЛАСОВ
КОНЕЧНЫЕ ПОЛЯ 
В ТЕЛЕКОММУНИКАЦИОННЫХ 
ПРИЛОЖЕНИЯХ
ТЕОРИЯ И ПРИМЕНЕНИЕ FEC, CRC 
И M-ПОСЛЕДОВАТЕЛЬНОСТЕЙ
ПРАКТИЧЕСКОЕ ПОСОБИЕ
2-е издание, доработанное и дополненное
Москва
ИНФРА-М
2025

УДК 512.624(075.8)
ББК 22.144.73я73
 
В58
Р е ц е н з е н т ы:
Когновицкий О.С., доктор технических наук, профессор, почетный 
профессор Санкт-Петербургского государственного университета телекоммуникаций имени профессора М.А. Бонч-Бруевича;
Кудряшов Б.Д., доктор технических наук, профессор, приглашенный профессор Тартуского университета;
Антонова В.М., кандидат технических наук, доцент, заведующий 
кафедрой Московского технического университета связи и информатики
Власов Е.Г.
В58  
Конечные поля в телекоммуникационных приложениях. Теория 
и применение FEC, CRC и M-последовательностей : практическое пособие / Е.Г. Власов. — 2-е изд., дораб. и доп. — Москва : ИНФРА-М, 
2025. — 437 с. + Доп. материалы [Электронный ресурс]. — (Наука 
и практика). — DOI 10.12737/2161305.
ISBN 978-5-16-020147-4 (print)
ISBN 978-5-16-112685-1 (online)
В практическом пособии систематически изложены основные прикладные направления теории конечных полей в цифровых телекоммуникациях. Основное внимание уделено связи теоретических аспектов с практическими методами применения конечных полей. Получены все необходимые 
формулы, лежащие в основе синтеза и анализа устройств реализации основных приложений конечных полей. Приведены примеры использования 
рассмотренных методов и их аппаратной реализации в реальных современных системах цифровой связи.
Предназначено как для студентов телекоммуникационных вузов, так 
и для специалистов в области цифровых систем связи, связанных с разработкой кодов проверки и исправления ошибок, а также методов цифрового 
скремблирования.
УДК 512.624(075.8)
ББК 22.144.73я73
Материалы, отмеченные знаком 
, 
доступны в электронно-библиотечной системе Znanium
ISBN 978-5-16-020147-4 (print)
ISBN 978-5-16-112685-1 (online)
© Власов Е.Г., 2025

Предисловие ко второму изданию
Дорогой читатель!
Рад представить Вам второе издание своей книги, посвященной практическим приложениям замечательного и красивейшего раздела алгебры. Благодарю издательство «ИНФРА-М» за такую возможность.
С момента выхода первой книги в 2016 году меня не покидала идея
второго, более полного издания. В новом издании я постарался реализовать все творческие планы и идеи.
Отмечу, что во втором издании книги углублены сведения о строении
полей расширения (параграфы 1.4 и 1.6) и тема линейных рекуррентных
последовательностей над полем (гл. 3). Существенно улучшен материал
о структуре и свойствах поля, построенного по степеням корня примитивного многочлена (подпараграф 1.4.4). Рассмотрена связь порядков
элементов конечного поля расширения с числами Мерсенна и Каннингема (подпараграфы 1.6.3 и 1.6.4). Также сильнее развита связь прямых и
обратных линейных рекуррентных последовательностей над полем. Как
и в первом издании, анализ основан на отображении элементов линейной рекуррентной последовательности над полем расширения в элементы линейной рекуррентной последовательности над простым полем. Однако при этом сильнее развит вопрос связи прямых и обратных последовательностей и согласования их начальных состояний.
Среди материала, ранее не вошедшего в первое издание, отмечу один
из наиболее эффективных известных методов декодирования кодов РС и
БЧХ — алгоритм Берлекэмпа – Месси, более известный по аббревиатуре
БМА (подпараграф 3.6.2). При этом особое внимание уделено теме вспомогательного регистра, формирующего опорную невязку. В литературе
подробный анализ этого вопроса найти не удалось. Рассмотрен алгоритм
Форни поиска значений ошибок недвоичных кодов БЧХ (подпараграф
2.5.5).
Кроме того, предложено решение задачи определения произвольного
элемента линейной рекуррентной последовательности над полем (параграф 3.5), что в целом выходит за рамки практического пособия, однако
указанное решение выражено в общем виде, что несколько упрощает искомые выводы.
Также в подпараграфе 1.3.1 приводится матричная запись умножения
многочленов. Нельзя сказать, что это представляется какой-то особенной
новизной, однако позволяет лучше понять и запомнить структуру выра3

жения умножения двух многочленов. Тем не менее такую форму представления указанной операции нигде в литературе найти не удалось.
По сравнению с первым изданием существенно улучшен материал,
посвященный аппаратному формированию остатков от деления многочленов над полем GF(q) (параграф 2.3).
Примеры применения актуализированы в соответствии с последними
изданиями стандартов и рекомендаций. Все рассмотренные примеры основаны на актуальных версиях международных нормативных документов:
- рекомендаций сектора стандартизации телекоммуникаций Международного телекоммуникационного союза (International Telecommunication Union – Telecommunication Standardization Sector, ITU-T);
- стандартов международного Института инженеров электротехники
и электроники (Institute of Electrical and Electronics Engineers, IEEE).
Отмечу также, что рассмотренные в примерах варианты реализации
приложений на основе конечных полей, являются типовыми. Все прочие
аналогичные примеры могут быть проанализированы на основе примеров этой книги. При этом особая ценность видится в материале примеров главы 4. В частности, подробно рассмотрен вопрос обоснованности
выбора порождающих многочленов кодов CRC, рекомендуемых ITU-T
для проверки ошибок сигналов иерархии PDH, в частности сигнала Е1.
Выражаю благодарность рецензентам за помощь и ценные подсказки.
Также выражаю благодарность Цонке Байчевой из Института математики и информатики Болгарской академии наук за предоставленный особо
ценный материал, использованный при подготовке главы 4.
Надеюсь, что проделанная работа окажется полезной. Все возникшие
вопросы по теме данной книги можно направить автору по адресу электронной почты finfields@mail.ru.
Е.Г. Власов
4

Введение
Конечное поле как математический объект известно и изучается с начала XIX века. При этом способствовавшие его открытию исследования
относятся к XVII  и XVIII  векам.  Однако практический интерес к этой
области возник примерно в 50-х годах прошлого века. В 1950-1970-х гг.
данная отрасль испытала бурное развитие: было открыто много хороших
помехоустойчивых кодов и эффективные методы их декодирования, метод обнаружения ошибок на основе алгебраических кодов. Вниманию,
вызвавшему поток исследований в этой области, способствовало появление в 1948 и 1949 гг. классических работ Клода Шеннона по теории
информации. Также на алгебраической основе были исследованы рекуррентные последовательности.
В этой книге предлагается обзор основных применяемых в современных телекоммуникациях методов на основе обширной и относительно
молодой области алгебры, известной как теория конечных полей.
В первой главе книги рассмотрены базовые теоретические сведения,
необходимые для понимания материала последующих глав, которые посвящены отдельным видам практического применения конечных полей в
телекоммуникациях. К фундаментальным трудам по данной теме следует в первую очередь отнести перевод книги австралийского и австрийского авторов Р. Лидла и Г. Нидеррайтера [18], книгу на основе трудов
К.Ф. Гаусса [7], а также классические учебники по теории чисел, в первую очередь [3], [6] и [31]. Отметим при этом, что более подробный обзор литературы приведен в начале каждой главы.
Во второй главе рассмотрен необходимый теоретический материал и
основные виды наиболее часто применяемых помехоустойчивых кодов.
Подробно рассмотрен вопрос аппаратной реализации циклического кодирования, приведены функциональные и аппаратные схемы. Рассмотрены методы декодирования линейных и циклических кодов. Среди
наиболее выдающихся трудов в данной области необходимо отметить
классические книги Т. Касами и др. [11], Р. Блейхута [2], [37], [38], У.
Петерсона и Э. Уэлдона [28], а также Мак-Вильямса и Н.Дж.А. Слоэна
[19].
Третья глава посвящена линейным рекуррентным последовательностям над полями расширения и простыми полями, а также связи между
указанными последовательностями. Рассмотрены вопросы формирования элементов поля расширения на основе схем регистров сдвига, приведены функциональные схемы и схемы аппаратной реализации. Также
5

в этой главе рассмотрен двойственный базис поля расширения, его применения для формирования элементов поля расширения и реализации
последовательностей над простым полем. Кроме того, рассмотрены задачи согласования начальных элементов схем прямых и обратных последовательностей, а также выражения произвольного элемента последовательности в аналитическом виде. В качестве основной литературы
по теме последовательностей может служить книга А.И. Маркушевича
[21], по теме двойственного базиса — книги О.С. Когновицкого [13]
и Р.Дж. Мак-Элиса [41]. По теме последовательностей над полем необходимо особо отметить книгу О.С. Когновицкого [13].
В четвертой главе рассмотрены коды, часто выделяемые в отдельный
класс кодов — коды с обнаружением ошибок. Необходимо отметить, что
литературы по кодам CRC крайне мало. В основном это первоисточники
в виде научных статей, основная из которых — статья авторов метода
CRС У. Петерсона и Д. Брауна [42], а также различные последующие исследования, основной целью которых было уменьшение избыточности
при приемлемых обнаруживающих ошибки свойствах. В этой связи подготовка материала по данной теме заняла особенно много времени. Однако теперь материал главы может служить хорошим обобщением и систематизацией.
Все главы сопровождаются актуальными, основанными на нормативных документах примерами применения рассмотренных методов в современных системах цифровой связи.
6

Глава 1
Сведения о конечных полях
В основе всех рассмотренных ниже приложений лежит единая теория, которая часто выделяется в отдельную область высшей (общей или
абстрактной) алгебры, — теория конечных полей.
К вопросу изучения конечных полей можно подойти разными способами. Однако, поскольку конечные поля являются основной темой этой
книги, мы постараемся уделить им наибольшее внимание и как можно
глубже раскрыть их структуру.
Задавшись вопросом глубокого внедрения в структуру чего-либо, необходимо понимать, что в своих поисках нельзя уйти дальше неких элементарных составляющих, далее уже не делимых. Примерно такую роль
играют в математике теория множеств и теория чисел.
Мы подойдем к вопросу так, как к нему подходят алгебраисты, и получим конечное поле, опираясь на фундаментальные понятия математики. Конечно, можно было бы пойти куда более коротким путем. Однако у любознательного читателя все равно останется ощущение недосказанности, побуждающее к дальнейшим поискам, которые рано или
поздно приведут к тем же самым фундаментальным основам из теории
чисел и теории множеств. Кроме того, такой подход способствует более
глубокому пониманию предмета.
Следует заранее предупредить читателя, что не стоит беспокоиться
насчет высокой сложности предлагаемого материала. С учетом специфики рассмотренных далее практических приложений мы постараемся
изложить его более доступно по сравнению с учебниками по абстрактной алгебре. Тем не менее ряд книг будет полезен в качестве факультатива к материалу этой главы.
Хорошим базовым источником дополнительных сведений по теории
групп будет книга П.С. Александрова [1], по теории множеств — книга
Ю.Е. Пензова [26]. Более глубокие, фундаментальные сведения по теме
множеств можно найти в классическом учебнике польских авторов
К. Куратовского и А. Мостовского [16].
По теории чисел особо рекомендуется книга, основанная на первоисточнике знаний в данной области — трудах К.Ф. Гаусса [7], классические учебники А.А. Бухштаба [3], И.М. Виноградова [6], А.К. Сушкевича [31], а также перевод книги С. Коутинхо под редакцией С.К. Ландо
7

[14]. Хорошим дополнением по теме простых чисел будет переводная
книга польского автора В. Серпинского [30].
По предмету абстрактной алгебры в целом, для углубленного изучения будут полезными книги М.М.  Глухова и др.  [8],  а также перевод
книги С. Ленга под редакцией А.И. Кострикина [17]. По теме непосредственно конечных полей в качестве практически всеобъемлющего источника сведений из данной области рекомендуется двухтомный перевод книги австралийского и австрийского авторов Р. Лидла и Г. Нидеррайтера [18].
С практической точки зрения наиболее ценной представляется книга
американского автора Р.Дж. Мак-Элиса на английском языке [41].
По материалу параграфа 1.7 в качестве дополнительного источника
рекомендуется книга В.А. Ильина и Э.Г. Позняка [10].
1.1. Базовые алгебраические структуры
1. Группой называется непустое множество G элементов произвольной природы с операцией над этими элементами. Для обозначения группы G с операцией o  используется запись: (
)
,
G o .
При этом для групповой операции выполняются следующие аксиомы.
1.
Замкнутость. Для каждой пары элементов a и b из G результат
групповой операции a b
o , также принадлежит G (является элементом G).
2.
Ассоциативность. Для любых элементов a, b и c группы G справедливо равенство:
(
)
(
)
a
b c
a b
c
=
o
o
o
o .
3.
Существование единичного (нейтрального) элемента. В группе
G существует такой элемент e, что a e
e a
a
=
=
o
o
 для любого элемента a
группы G. Элемент e называется единичным (нейтральным) элементом
группы.
4.
Существование обратного элемента. Для любого элемента a из
G существует такой элемент b, что a b
b a
e
=
=
o
o
, где e — единичный
элемент группы.
Группа называется коммутативной, или абелевой группой, если выполняется дополнительная аксиома.
5.
Коммутативность. Для любых элементов a и b из G справедливо: a b
b a
=
o
o
.
Операция o , используемая в определении группы, относится к операциям, которые называются в общей алгебре бинарными.
8

Бинарная операция на непустом множестве M — это закон1, по которому каждой паре элементов из M сопоставляется элемент того же
множества M.
Примером бинарной операции могут служить сумма и разность двух
чисел на множествах ¢ , ¤ и ¡ .
Пример 1.1.1. Свойствами группы обладает, например, множество ¢
целых чисел относительно групповой операции — сложения целых чисел. Такая группа является абелевой группой в силу коммутативности
сложения целых чисел.
В примере 1.1.1 действию над объектами — элементами группы —
соответствует групповая операция. Однако элементами групп могут
быть любые объекты, поддающиеся аналитическому описанию, в том
числе действия над объектами.
Пример 1.1.2. Пусть, например, даны три элемента некоторого (произвольного) множества, пронумерованные числами 1, 2 и 3. Определим
элемент группы как перестановку номеров: (
)
(
)
12 3
13 2
®
. Обозначим
элемент, соответствующий такой перестановке, буквой a. Другим элементом группы (элементом b) может быть, например, перестановка номеров (
)
(
)
12 3
31 2
®
. Из комбинаторики известно, что всего существует
3!
6
=
 таких перестановок. Групповая операция a b
o  в такой группе может быть определена как последовательное применение перестановки,
соответствующей элементу a, а затем перестановки, соответствующей
элементу b.
Группа примера 1.1.1 содержит бесконечное число элементов. Группа
примера 1.1.2, напротив, содержит конечное число элементов. Таким образом, существуют группы, содержащие как конечное, так и бесконечное число элементов.
1 Более строгое определение основано на понятии отображения множества в
множество: бинарная операция — это отображение M ´ M в M, где M ´ M обозначает множество упорядоченных пар (a, b), где a и b — элементы M. Однако
мы будем рассматривать вопросы, связанные с отображениями, ниже (см. подпараграф 1.2.3).
9

Группа, содержащая конечное число элементов, называется конечной группой. Число элементов конечной группы 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. Пусть, например,
4
n =
.
Введем групповую операцию a b
o  для пары элементов
(
)
1
2
3
4
,
,
,
a
a a
a
a
=
и
(
)
1
2
3
4
,
,
,
b
b b b b
=
 следующего вида:
(
)
1
1
2
2
3
3
4
4
,
,
,
a b
a
b a
b
a
b a
b
=
+
+
+
+
o
,
где «+» означает сложение по модулю 2. Тогда, например, для
0010
a =
и
1010
b =
 получим:
1000
a b =
o
.
Очевидно, что в результате сложения двух наборов по модулю 2 не
может появиться набор, содержащий числа, отличные от 0 и 1. Следовательно, результат принятой операции над любыми элементами рассматриваемого множества принадлежит тому же множеству, а значит, выполняется аксиома замкнутости относительно выбранной операции. Единичным элементом в данном случае будет набор из n нулей. По определению сложения по модулю 2,  для любого элемента a справедливо:
a a
e
=
o
, где e — единичный элемент, которому соответствует набор из n
нулей. Сложение по модулю 2 является ассоциативным (по определению). Поэтому поэлементное сложение наборов из n нулей и единиц
также будет обладать ассоциативностью. То же самое касается коммутативности. Таким образом, рассматриваемое множество относительно заданной над его элементами операции — сложения по модулю 2 — действительно является группой, а именно конечной абелевой группой.
10