Дифференцирование полиномов нескольких переменных над полями Галуа и приложения к кодам Рида-Маллера

 
 

 

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ 

РОССИЙСКОЙ ФЕДЕРАЦИИ 

Федеральное государственное автономное образовательное 

учреждение высшего образования 

«ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ» 

 
 

 
 
 

 

Н. С. Могилевская 

 
 

ДИФФЕРЕНЦИРОВАНИЕ ПОЛИНОМОВ  

НЕСКОЛЬКИХ ПЕРЕМЕННЫХ  

НАД ПОЛЯМИ ГАЛУА  

И ПРИЛОЖЕНИЯ  

К КОДАМ РИДА–МАЛЛЕРА 

 

 

Монография 

 
 
 
 

 
 

Ростов-на-Дону – Таганрог 

Издательство Южного федерального университета 

2022

 
 

 

УДК 004.8:519.711.3(035.3) 
ББК 32.811.7 я44 

М 74 

Печатается по решению комитета при ученом совете 

Южного федерального университета по естественнонаучному 

и математическому направлению науки и образования 

(протокол № 8 от 6 июля 2022 г.) 

Рецензенты: 

доктор физико-математических наук, профессор  

кафедры высшей математики МФТИ В. А. Стукопин; 

доктор физико-математических наук, профессор кафедры алгебры  

и дискретной математики ИММиКН ЮФУ  В. А. Скороходов; 

кандидат технических наук доцент кафедры экономики,  

менеджмента и торгового дела Тульского филиала  

РЭУ им. Г. В. Плеханова Е. В. Панферова 

 

Могилевская, Н. С. 

М 74  
Дифференцирование полиномов нескольких переменных над 

полями Галуа и приложения к кодам Рида–Маллера : монография / 
Н. С. Могилевская ; Южный федеральный университет. – Ростов-на-
Дону ; Таганрог : Издательство Южного федерального университета, 
2022. – 122 с. 

ISBN 978-5-9275-4199-7 
DOI 10.18522/801302651 
Монография посвящена разработке методов обеспечения помехоустойчивости 
информационных коммуникаций для целей передачи и хранения информации. 
Получены результаты, связанные с дифференцированием и интегрированием 
полиномов нескольких переменных, заданных над полями Галуа. 
Эти результаты используются для построения новых алгоритмов декодирования 
некоторых кодов Рида–Маллера. Один из предложенных декодеров кодов 
Рида–Маллера второго порядка может быть применен для произвольных полей 
Галуа нечетной мощности или мощности 2. Два других построенных декодера 
кодов, заданных над полями мощности 2 и 3, превосходят многие известные 
декодеры по уровню корректирующей способности. Показано одно возможное 
практическое применение таких декодеров. 

Предназначена тем, кто работает в области проектирования надежных систем 
хранения и передачи данных, преподает и изучает эти дисциплины, а 
также интересующимся приложениями теории кодирования, а именно кодов 
Рида–Маллера. 

УДК 004.8:519.711.3(035.3) 

ББК 32.811.7 я44 

ISBN 978-5-9275-4199-7 

  
 
 
© Южный федеральный университет, 2022 

© Могилевская Н. С., 2022 

© Оформление. Макет. Издательство  

Южного федерального университета, 2022 

ОГЛАВЛЕНИЕ 

Введение....................................................................................................................................
Глава 1. Полиномы нескольких переменных над полями Галуа 

и их дифференцирование..........................................................................
1.1. Алгебра полиномов над полями Галуа..........................................

1.1.1. Моном, полином и их степени................................................
1.1.2. Градуировка алгебры полиномов.........................................

1.2. Дифференцирование и интегрирование полиномов............

1.2.1. Оператор дифференцирования..............................................
1.2.2. Представление полиномов второй степени 

и их производных полиномов через 
квадратичные формы..................................................................

1.2.3. Интегрирование полиномов второй степени................

1.3. Аналоги оператора дифференцирования....................................

1.3.1. Векторное дифференцирование...........................................
1.3.2. Мультипликативное дифференцирование.....................

1.4. 𝑞-ичные коды Рида-Маллерa младших порядков...................

1.4.1. Полиномиальное представление q-ичных кодов 

Рида–Маллера. Оператор кодирования............................

1.4.2. Корректирующая способность кодов 

Рида–Маллера..................................................................................

1.4.3. Коммутативность операторов кодирования 

и дифференцирования................................................................

Глава 2. Декодеры кодов Рида–Маллера второго порядка....................

2.1. Декодеры помехоустойчивых кодов в схеме передачи 

данных.............................................................................................................

2.2. Способ организации декодеров, использующих 

редукцию к кодам меньшего порядка...........................................

2.3. Декодер кодов RMq(2, m) с жестким входом...............................

2.3.1. Алгоритм декодирования.........................................................
2.3.2 Обоснование корректности декодера 

(алгоритм 2.1)..................................................................................

7

10
10
11
12
15
15

17
22
25
26
27
31

31

33

37
39

39

44
47
47

48

2.4. Вероятностный декодер с мягким входом для 

двоичных РМ-кодов.................................................................................
2.4.1. Модели двоичных каналов.......................................................
2.4.2. Модель двоичного полунепрерывного 

помехоустойчивого канала......................................................

2.4.3. Условие гладкости.........................................................................
2.4.4. Вероятностный алгоритм декодирования 

бинарных РМ-кодов с мягким входом................................

2.4.5. Обоснование корректности декодера 

(алгоритм 2.2)..................................................................................

2.5. Вероятностный декодер с мягким входом для троичных 

РМ-кодов.........................................................................................................
2.5.1. Модели троичных каналов.......................................................
2.5.2. Модель троичного полунепрерывного 

помехоустойчивого канала......................................................

2.5.3. Алгоритм декодирования.........................................................
2.5.4. Обоснование корректности декодера 

(алгоритм 2.3)..................................................................................

2.5.5. Вычислительный пример работы декодера 

кода RM3(2,2)...................................................................................

Глава 3. Об одном практическом приложении 

вероятностных декодеров........................................................................
3.1. Общая модель информационно-аналитической системы 

канала наблюдения..................................................................................
3.1.1. Структура каналов........................................................................
3.1.2. Модель наблюдателя...................................................................
3.1.3. О предварительной оценке свойств приемных 

блоков наблюдателем.................................................................

3.2. Информационно-аналитическая система канала 

наблюдения, организованная с использованием кодов 
Рида–Маллера..............................................................................................
3.2.1. Модель ИАС КН, уточненная на случай бинарных 

РМ-кодов и их декодеров...........................................................

3.2.2. Экспериментальное исследование ИАС КН,

организованной с использованием двоичных 
кодов Рида–Маллера....................................................................

Заключение.......................................................................................................................
Литература.......................................................................................................................

51
52

53
57

59

62

67
68

70
75

78

84

89

93
93
95

96

102

102

106
112
113

СПИСОК СОКРАЩЕНИЙ 

 QСК – q-ичный симметричный канал. 

 БИВВ – блок имитации внешних воздействий. 

 БММО – блок математической модели объекта. 

 БОР – блок обработки результатов. 

 БУИМ – блок управления имитационной модели. 

 ДСК – двоичный симметричный канал. 

 ИАС КН – информационно-аналитическая система канала 

наблюдения. 

 ИМ ЦПК – имитационная модель цифрового помехоустойчи-

вого канала связи. 

 ИС ОПСАПК – информационная система оценки применимо-

сти схем алгебраического помехоустойчивого кодирования. 

 ОСШ – отношение «сигнал/шум». 

 РМ-код – код Рида–Маллера. 

 

СПИСОК ОБОЗНАЧЕНИЙ 

 ℕ0 – множество натуральных чисел, объединенное с нулем.  

 ℕ0

𝑚 – декартово произведение 𝑚 экземпляров множества ℕ0.  

 𝔽𝑞

(𝑟)[𝑥1, . . . , 𝑥𝑚 ] – кольцо полиномов от 𝑚 переменных, задан-

ных над полем Галуа 𝔽𝑞, степень полиномов не превосходит 𝑟. 

 𝔽𝑞[𝑥1, 𝑥2, … 𝑥𝑚] – алгебра полиномов от 𝑚 переменных, за-

данных над полем Галуа 𝔽𝑞, 𝑞 = 𝑝𝑚, где 𝑝 – простое, 𝑚 – 

натуральное число.  

 Order𝑞

𝑚 = {α̅1, … , α̅𝑛} – упорядоченный набор из 𝑛 = 𝑞𝑚 век-

торов, где α̅𝑗 = (α𝑗1, α𝑗2, … , α𝑗𝑚), 0 ≤ α𝑗𝑖 < 𝑞, в котором элемен-

ты расположены по возрастанию ρ(α̅), а при одинаковых 

значениях ρ(α̅) упорядочены лексикографически. В част-

ности, α̅1 = 0̅. 

 𝑅𝑀𝑞(𝑟, 𝑚) – код Рида–Маллера с параметрами 𝑟 (порядок 

кода) и 𝑚, заданный над полем Галуа мощности 𝑞. 

 ρ(α̅) – сумма значений α𝑖 вектора α̅ = (α1, … , α𝑚) ∈ 𝑁0

𝑚 как 

целых неотрицательных чисел, α̅ = (α1, . . . , α𝑚) ∈ 𝑁0

𝑚. 

ВВЕДЕНИЕ 

Во всех существующих системах передачи и хранения дан-

ных на данные воздействуют непреднамеренные ошибки, по-
вреждающие их. Для защиты от случайных ошибок использу-
ются различные типы алгебраических помехоустойчивых ко-
дов [37; 45; 53; 56; 57; 63].  

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

связи является стандартной практикой, однако у помехоустой-
чивых кодов есть также иные приложения, например в крип-
тографии [5; 40; 62].  

Несмотря на существование большого количества помехо-

устойчивых кодов, алгоритмов их кодирования и декодирова-
ния, разработка новых декодеров к уже известным кодам яв-
ляется актуальной задачей (см., например, [31; 39; 96; 103]). 
Новые декодеры могут превосходить существующие по каким-
либо параметрам, например по скорости работы, уровню кор-
ректирующей способности, или обладать меньшими техниче-
скими требованиями к аппаратуре. 

В данной работе рассматривается задача дифференцирова-

ния и интегрирования полиномов нескольких переменных, за-
данных над полями Галуа; полученные результаты использу-
ются для построения новых алгоритмов декодирования неко-
торых кодов Рида–Маллера; показано одно возможное практи-
ческое применение таких декодеров.  

Рассмотрим структуру работы.  
Первая глава посвящена полиномам нескольких переменных, 

заданных над полями Галуа, причем рассматриваются поля мощ-
ности 2 или 𝑞 = 𝑝𝑟, где 𝑝(> 2) – простое, а 𝑟 – натуральное число. 

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

Во второй главе с использованием описанных выше теоре-

тических результатов построено три новых декодера кодов 
Рида–Маллера второго порядка. Новый детерминированный 
декодер с жестким входом основан на редукции зашумленных 
кодовых слов кодов Рида–Маллера второго порядка к зашум-
ленным словам кода Рида–Маллера первого порядка. Для де-
кодирования слов кода первого порядка предлагается исполь-
зовать произвольный сторонний декодер. Из результатов ра-
боты стороннего декодера восстанавливается исходный ин-
формационный полином кода Рида–Маллера второго порядка. 
Построенный декодер может работать с кодами Рида–Маллера 
второго порядка, заданными над двоичным полем Галуа или 
полем Галуа нечетной мощности. 

На основе созданного детерминированного декодера с 

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

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

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

Модель системы каналов уточнена на случай использова-

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

 
 

ГЛАВА 1. ПОЛИНОМЫ НЕСКОЛЬКИХ 
ПЕРЕМЕННЫХ НАД ПОЛЯМИ ГАЛУА  
И ИХ ДИФФЕРЕНЦИРОВАНИЕ 

В главе приведены необходимые результаты и факты о 

дифференциальном и интегральном исчислении для полино-
мов нескольких переменных, заданных над полями Галуа 𝔽𝑞, 
где 𝑞 – мощность поля. Отметим, что мощность поля – это все-
гда число вида 𝑞 = 𝑝𝑟, где 𝑝 – простое, а 𝑟 – натуральное число. В 
работе рассматриваются поля Галуа мощности 𝑞 = 2 и нечетной 
мощности 𝑞 = 𝑝𝑟, где 𝑝(> 2) – простое, а 𝑟 – натуральное число, 
т. е. из рассмотрения исключены поля вида 𝔽2𝑟. Отметим, что в 
случае произвольных полей мощности 𝑞 = 2𝑟 вопросы диффе-
ренцирования и интегрирования полиномов вызывают опре-
деленную трудность и в данной работе не исследуются. 

Основное количество публикаций, которые рассматривают 

задачи дифференцирования полиномов нескольких перемен-
ных, посвящено случаю двоичных полей [3; 6; 11; 43; 44], неко-
торые результаты для полей простой мощности изложены в 
[15; 54]. В работе Б. А. Погорелова рассматривается принципи-
ально иной способ дифференцирования полиномов, заданных 
над полями Галуа [55].  

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

ваны нами в работах [13; 21; 26; 28; 29]. 

1.1. Алгебра полиномов над полями Галуа 

В работе будут рассматриваться полиномы нескольких пе-

ременных, определенные над конечными полями. Приведем 

необходимые сведения, связанные с такими полиномами. По-
дробное изложение этой теории можно найти, например, в ра-
ботах [10, с. 203–209; 43, с. 54–62; 54, c. 72–76]. 

1.1.1. Моном, полином и их степени 

Рассмотрим 𝔽𝑞[𝑥1, 𝑥2, … 𝑥𝑚] – алгебру полиномов от 𝑚 пере-

менных над полем Галуа 𝔽𝑞, 𝑞 = 𝑝𝑚, где 𝑝 – простое, 𝑚 – нату-
ральное число. Пусть ℕ0 – это множество натуральных чисел, 
объединенное с нулем, а ℕ0

𝑚 – декартово произведение 𝑚 эк-

земпляров множества ℕ0.  

Полиномы из 𝔽𝑞[𝑥1, 𝑥2, … 𝑥𝑚] будем записывать в виде ко-

нечной суммы мономов 

 
𝑓(𝑥̅) = ∑
 
𝑘1
α1=0 ∑
 
𝑘2
α2=0 … ∑
 
𝑘𝑚
α𝑚=0 𝑓α1,α2,…,α𝑚𝑥1

α1𝑥2

α2 … 𝑥𝑚

α𝑚 (1.1) 

или в сокращенном виде  

 
𝑓(𝑥̅) = ∑  
α̅ 𝑓α̅𝑥̅α̅, 
(1.2) 

где α̅ = (α1, . . . , α𝑚) ∈ ℕ0

𝑚, а под 𝑥̅α̅ будем понимать 𝑥1

α1𝑥2

α2. . . 𝑥𝑚

α𝑚. 

Далее будем предполагать, что в выражении (1.2) только ко-
нечное количество коэффициентов 𝑓α̅ отлично от нуля и все 
мономы различные. 

Введем обозначение ρ(α̅) = α1 + α2 + . . . + α𝑚, где α̅ = 

= (α1, . . . , α𝑚) ∈ 𝑁0

𝑚. Степень монома 𝑥̅α̅ = 𝑥1

α1. . . 𝑥𝑚

α𝑚 определя-

ется формулой:  

𝑑𝑒𝑔(𝑥̅α̅) = ρ(α̅). 

Степень ненулевого полинома 𝑓 ∈ 𝔽𝑞[𝑥1, 𝑥2, . . . , 𝑥𝑚] определя-

ется как максимум степеней мономов, входящих в разложение 
(1.2) с ненулевыми коэффициентами, т. е.  

𝑑𝑒𝑔(𝑓) = 𝑚𝑎𝑥{𝑑𝑒𝑔(𝑓α̅𝑥̅α̅), 𝑓α̅ ≠ 0, α̅ ∈ 𝑁0

𝑚}. 

Следует отметить, что различные полиномы как функции мо-

гут совпадать. Например, рассмотрим полиномы 𝑓, 𝑔 ∈ 𝔽2[𝑥1, 𝑥2]: 

𝑓 = 𝑥1

2 + 𝑥2;  𝑔 = 𝑥1 + 𝑥2. 

Очевидно, что 𝑓 = 𝑔, так как в поле 𝔽2 справедливо равен-

ство 𝑥2 = 𝑥. 

Лемма 1.1. Пусть 𝑓 ∈ 𝔽𝑞[𝑥1, . . . , 𝑥𝑚]. Если deg(𝑓) > 𝑚(𝑞 − 1), 

то найдется такой полином 𝑔 ∈ 𝔽𝑞[𝑥1, . . . , 𝑥𝑚], который как функ-
ция совпадает с полиномом 𝑓, и при этом в каждом мономе сте-
пень любого 𝑥𝑖 не превосходит (𝑞 − 1), т. е. deg(𝑔) ≤ 𝑚(𝑞 − 1).  

Доказательство. 
Мономы 
полинома 
𝑓 
имеют 
вид 

𝑓α̅𝑥̅α̅=𝑓α̅𝑥1

α1. . . 𝑥𝑚

α𝑚, где α̅ = (α1, α2, . . . , α𝑚) ∈ 𝑁0

𝑚. В силу того, что 

𝑥𝑞 = 𝑥 для любого 𝑥 ∈ 𝔽𝑞 (см. [41, т. 1, с. 66]), получаем, что как 
функция любой моном совпадает с таким другим мономом, у 
которого степень любого 𝑥𝑖 не превосходит (𝑞 − 1). Так как мо-
ном 𝑓α̅𝑥1

α1. . . 𝑥𝑚

α𝑚 содержит 𝑚 переменных, то он как функция 

совпадает с таким мономом, степень которого не превосходит 
значения 𝑚(𝑞 − 1).  

Следуя [54, c. 72], полиномы, удовлетворяющие лемме 1.1, 

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

1.1.2. Градуировка  

алгебры полиномов  

Далее в работе будет удобно уметь сопоставлять полиному 

𝑓 ∈ 𝔽𝑞[𝑥1, . . . , 𝑥𝑚] вектор его коэффициентов, а также уметь со-
поставлять 𝑓 его значения, вычисленные во всех возможных 
точках 𝑥1, … , 𝑥𝑚, 𝑥𝑖 ∈ 𝔽𝑞

𝑚, 𝑖 = 1, 𝑞𝑚
̅̅̅̅̅̅̅. Для выполнения обоих этих 

действий удобно ввести понятие упорядоченных наборов. 

Во множестве ℕ0

𝑚 выделим упорядоченный набор из 𝑛 = 𝑞𝑚 

векторов  

 
Order𝑞

𝑚 = {α̅1, … , α̅𝑛}, 
(1.3) 

где α̅𝑗 = (α𝑗1, α𝑗2, … , α𝑗𝑚), 0 ≤ α𝑗𝑖 < 𝑞, элементы которого распо-

ложены по возрастанию ρ(α̅), а при одинаковых значениях ρ(α̅) 
упорядочены лексикографически. В частности, α̅1 = 0̅.