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

 
 

 

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

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

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

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

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

 
 

 
 
 

 

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

 
 

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

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

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

И ПРИЛОЖЕНИЯ  

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

 

 

Монография 

 
 
 
 

 
 

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

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

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. Алгебра полиномов над полями Галуа 

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