Коды Рида-Маллера как групповые коды тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат наук Тумайкин, Илья Николаевич

• Тумайкин, Илья Николаевич
• кандидат наук
• 2017

Оглавление диссертации кандидат наук Тумайкин, Илья Николаевич

Содержание

Введение

1 Предварительные сведения и результаты

2 Совпадения базисных кодов Рида—Маллера со степенями радикала

3 Строение графа включений базисных кодов и степеней радикала

3.1 Включения вида з Мп(т, к)

3.2 Включения вида Мп(т, к) з Ж3а

4 Совпадения идеалов (т,к)

5 Базисы кодов Рида—Маллера

5.1 Элементы Тг(и)

5.2 Элементы Тг(£и)

5.3 Произведения вида Тг(£и) • Тг(хм^)

5.4 Базисы кодов Рида-Маллера

6 Перенос результатов для идеалов Мп(т,к) на случай идеалов 'Я.Мж(т,к)

6.1 Равенство ШяПМж(т,к) = Тг(ШяМж(т,к))

6.2 Совпадения кодов Рида-Маллера со степенями радикала Шд

6.3 Строение графа включений кодов Рида-Маллера и степеней радикала

6.3.1 Включения вида з %МЖ (т, к)

6.3.2 Включения вида ПМП(т, к) з

Заключение

Список литературы

Приложение: графы включений базисных кодов Рида—Маллера и степеней

радикала

Введение диссертации (часть автореферата) на тему «Коды Рида-Маллера как групповые коды»

Введение

Код с исправлением ошибок — это способ представления информации, обеспечивающий её надёжную передачу по каналу связи с помехами. Теория помехоустойчивого кодирования — обширная и постоянно развивающаяся область математики, включающая в себя разделы алгебры, комбинаторики, теории вероятностей, геометрии и теории чисел. Фундаментальная проблема теории кодирования состоит в эффективном обнаружении искажений, возникших при передаче данных, и восстановлении исходного сообщения. Первые работы, посвящённые проблемам помехоустойчивой передачи информации, были опубликованы К.Э. Шенноном в 1948 году. В настоящее время вопросы, связанные с надёжным обменом информацией, являются как никогда актуальными, что связано, прежде всего, с развитием компьютерных и телекоммуникационных технологий.

В основе помехоустойчивого кодирования лежит следующий принцип: перед передачей сообщения к нему добавляют полученную с помощью некоторого алгоритма избыточную информацию, которая позволяет принимающей стороне обнаружить и устранить возникшие искажения. Процессы добавления избыточной информации и последующего восстановления исходного сообщения называют кодированием и декодированием, соответственно. С каждым кодом связаны перечисленные ниже базовые понятия.

• Множество сообщений. Данное множество определяется алфавитом и длиной сообщения. В самом простом и практически важном случае алфавит — это множество {0,1}. В общем случае алфавит, как правило, состоит из элементов конечного поля . Сообщения являются словами одинаковой длины к в выбранном алфавите.

• Множество кодовых слов. В результате кодирования сообщения получается новое слово в том же алфавите, которое называется кодовым словом. Кодовые слова являются словами одинаковой длины п в выбранном ранее алфавите. Множество всех кодовых слов обычно отождествляют с кодом. Число п называют длиной кода.

• Алгоритмы кодирования и декодирования. Алгоритм кодирования определяется функцией, действующей из множества сообщений в множество кодовых слов. Алгоритм декодирования — функцией, действующей из множества кодовых слов в множество сообщений.

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

Известно, что коды Рида-Маллера допускают несколько эквивалентных определений: с помощью булевых функций [8], с помощью конечных геометрий [4], с помощью идеалов в кольце многочленов [4], с помощью идеалов групповой алгебры [7]. Данная диссертация опирается на теоретико-кольцевой метод изучения кодов Рида-Маллера [2], предложенный в 2012 году группой учёных: Коусело, Гонсалес, Марков, Мартинес, Нечаев. В основе этого метода лежит понятие базисного кода Рида-Маллера.

Замечание. Далее будем называть коды Рида-Маллера обычными кодами Рида-Маллера, чтобы отличать их от базисных кодов Рида-Маллера.

Перейдём к построению обычных кодов Рида-Маллера. Пусть А — конечное коммутативное кольцо с единицей, О — группа порядка п с единицей е. Зафиксируем некоторое упорядочивание элементов группы О такое, что О = {е = д1,... ,дп}. Рассмотрим групповое кольцо АО. Тогда любое подмножество I С АО определяет код К(1) длины п в алфавите А равенством

П )

К(1) = \(аь...,ап)е Ап : ^ агдг е П.

г-1

Если I — идеал АО, то код К(1) называется групповым кодом в кольце АО. Далее будем отождествлять идеал I и соответствующий ему групповой код К(1). Отметим, что АО также является групповой алгеброй над кольцом А.

Положим А = — конечное поле характеристики р и порядка q = р, О = Н — элементарная абелева группа, изоморфная аддитивной группе поля , и пусть ф — соответствующий изоморфизм. Рассмотрим — подполе порядка п = рх в поле ¥д. Пусть шп (г) — сумма цифр в п-ичном представлении числа г. Тогда базисный код Рида-Маллера порядка к — это групповой код Мп (к) длины q в алфавите , где идеал Мп(к) определён равенством

Мп (к)" _^ ¥ч( 2 (Ф(Ь))гЛ.

ге0,д— 1: (г)^к ^ НеИ '

Рассмотрим 1г — функцию следа из поля в подполе . Определим отображение Тг:

Тг( X анЬ) " X ^г(аи)Н, ан е .

^ НеИ ' НеИ

Тогда Тг(Мп(к)) является идеалом Н, а групповой код Тг(Мп(к)) длины q в алфавите — это обычный код Рида-Маллера порядка к [2].

Алгебраическая структура обычных кодов Рида-Маллера над простым полем хорошо изучена: классический результат, впервые полученный Берманом [1] и позже обобщённый Шарпен [5], гласит, что в данном случае обычные коды Рида-Маллера совпадают со степенями радикала указанной выше групповой алгебры. Однако, вопрос о совпадении обычных кодов Рида-Маллера и степеней радикала в случае непростого поля оставался без подробного рассмотрения в известных автору диссертации работах. Вопрос об условиях, описывающих теоретико-множественные включения между обычными кодами Рида-Маллера и степенями радикала, оставался полностью неисследованным.

Цель работы

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

Научная новизна

Результаты данной диссертации являются новыми, получены автором самостоятельно и заключаются в следующем:

1. Исследованы совпадения базисных кодов Рида-Маллера со степенями радикала соответствующей групповой алгебры. Доказано отсутствие нетривиальных совпадений в случае непростого подполя.

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

3. На основе развитых в данной работе методов получены аналоги вышеперечисленных результатов для обычных кодов Рида-Маллера:

• Доказано отсутствие нетривиальных совпадений обычных кодов Рида-Маллера со степенями радикала соответствующей групповой алгебры в случае непростого поля.

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

Методы исследования

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

Теоретическая и практическая ценность

Работа имеет теоретический характер. Вместе с тем, полученные результаты применимы в практических задачах теории кодирования и вносят вклад в теорию обычных и базисных кодов Рида-Маллера.

Апробация диссертации

Результаты диссертации освещались автором на семинарах кафедры высшей алгебры механико-математического факультета МГУ:

• научно-исследовательский семинар по алгебре;

• семинар "Кольца и модули".

Публикации

Основные результаты данной работы опубликованы в [11], [12], [13].

Структура диссертации

Работа состоит из введения, шести разделов, заключения, списка литературы и приложения. Библиография содержит 13 наименований. Текст диссертации изложен на 52 страницах.

Краткое содержание диссертации по разделам

Раздел 1 носит вспомогательный характер: здесь приводятся необходимые определения и формулировки базовых фактов, которые используются в данной научной работе.

Раздел 2 описывает совпадения базисных кодов Рида-Маллера со степенями радикала соответствующей групповой алгебры. Кратко изложен известный случай простого подполя и подробно исследован случай непростого подполя. Доказана теорема 2.1, которая показывает, что в случае непростого подполя есть только три таких тривиальных совпадения.

Раздел 3 посвящён изучению теоретико-множественных включений между базисными кодами Рида-Маллера и степенями радикала. Последовательно рассмотрен сначала случай включения базисных кодов в степени радикала, затем — включения степеней радикала в базисные коды. В обоих случаях получены необходимые и достаточные условия указанных включений.

В первом случае теоретико-кольцевые критерии описаны в теоремах 3.1 и 3.2, теоретико-множественные критерии — в утверждении 3.9, числовые критерии — в теореме 3.5. Во втором случае теоретико-множественные критерии описаны в утверждении 3.10, числовые критерии — в теореме 3.6.

В разделе 4 подробнее исследованы произведения радикала и базисных кодов, которые определяют упомянутые выше теоретико-кольцевые критерии включения базисных кодов в степени радикала.

В разделе 5 построены базисы специального вида для обычных кодов Рида-Маллера. Данные базисы состоят из образов базисных элементов базисных кодов Рида-Маллера под действием отображения Тг и являются связующим звеном при рассмотрении базисных и обычных кодов в совокупности. Основным результатом раздела является теорема 5.4, а непосредственная конструкция указанных базисов содержится в предшествующих данной теореме утверждениях.

Раздел 6 посвящён доказательству результатов для обычных кодов Рида-Маллера аналогичных результатам, полученным для базисных кодов в разделах 2 и 3. Существенную роль здесь играют базисы, рассмотренные в предыдущем разделе.

В подразделе 6.2 исследованы совпадения обычных кодов Рида-Маллера со степенями радикала в случае непростого поля. Доказана теорема 6.1, которая показывает, что, подобно базисным кодам, в случае непростого поля есть только три таких тривиальных совпадения.

В подразделе 6.3 изучены теоретико-множественные включения между обычными кодами Рида-Маллера и степенями радикала и получены необходимые и достаточные условия этих включений. В случае включения кодов в степени радикала теоретико-кольцевые критерии описаны в теоремах 6.2 и 6.3, теоретико-множественные критерии — в утверждении 6.7, числовые критерии — в теореме 6.5. В случае включения степеней радикала в обычные коды теоретико-множественные критерии описаны в утверждении 6.8, числовые критерии — в теореме 6.6. Отметим, что теоретико-множественные и числовые критерии одинаковы для базисных и обычных кодов Рида-Маллера.

Благодарности

Автор выражает глубокую благодарность за постановку задач, руководство работой и поддержку своему научному руководителю Виктору Тимофеевичу Маркову.

1 Предварительные сведения и результаты

Пусть р — простое число и д = р1, I ^ 1. Рассмотрим поле Q = ¥д характеристики р и порядка д. Пусть д = пт, где т > 1, I = Лт, п = рЛ, Л ^ 1. Рассмотрим поле Р = характеристики р и порядка п. Пусть группа (И, •) изоморфна аддитивной группе поля Q. Рассмотрим групповую алгебру Б = QH и групповую алгебру Д = РИ. Радикалы алгебр Б и Д обозначим и Шд, соответственно. Пусть ф : (И, •) ^ +) — указанный выше изоморфизм.

Рассмотрим следующие элементы:

Ui =

heH

2 (ф(й))й е Б, г е 0, д — 1.

ЬеИ

Определение 1.1. п-весом числа г назовём сумму цифр в его п-ичном представлении и обозначим (г). Заметим, что (г) е 0, т(п — 1) при г е 0, д — 1. Аналогично вводится р-вес.

Определение 1.2 ([2]). Для всех к е 0,ш(п — 1) определим базисный код Рида-Маллера порядка к над полем Q равенством

Мж (m, к) = Yj Qui

ie0,q-l

Утверждение 1.1 ([2]). (т,к) является идеалом в Б и линейным кодом над Q с кодовыми параметрами [д, МП(т, к),^(т, к)], где МП(т, к) — размерность идеала (т, к), которая равна числу расстановок г ^ к шаров по т лункам 'так, что в каждой лунке меньше п шаров:

m (-к)-£ (m х^) -i (i (-i)j cm )(m - m nj));

dn(m, к) = (p + 1)пк, где к и p — частное и остаток от деления m(n — 1) — к на (п — 1), т.е. m(n — 1) — к = к(п — 1) + p, где 0 < p < п — 1.

Замечание 1.1. Известно, что Мп(m,m(n — 1)) = S и Мп(m,m(n — 1) — 1) = [2]. Непосредственно из определения следует, что Мп(m, 0) = Quo.

Утверждение 1.2 ([2]). Множество {ui : i е 0,q — 1, 0 ^ (i) ^ к} — базис Мп(m^). Определение 1.3 ([3,10]). Функцию следа trQ из поля Q в поле P определим равенством

trQ(a) = а + ап + ап2 Н-----b а*™'1, а е Q.

Определение 1.4 ([2]). Пусть tr = trQ — функция следа из поля Q в поле P. Определим

функцию следа Тг = TrR из алгебры S в алгебру R равенством

Тг 2 ahh \ = X tr{ah)k, ah e Q.

\heH J heE

Утверждение 1.3 ([2]). Тг : 5 ^ Я — эпиморфизм модулей, и образ любого ненулевого идеала в 5 является ненулевым идеалом в Я.

Определение 1.5 ([2]). Обозначим %МЖ(т,к) " Тг(Мп(т,к)).

Утверждение 1.4 ([2]). %МП(т,к) является идеалом в Я и линейным кодом над Р с кодовыми параметрами \д_, Мп(т, к), ¿п(т, к)]. Код %МЖ(т, к) является кодом Рида-Маллера порядка к над полем Р.

Значительная часть дальнейших результатов опирается на следующие известные факты.

Лемма 1.1 ([2]). Для любых в,Ь е — 1 имеют место соотношения:

пзщ " 0, если в + Ь ^ q — 2;

" Озщ, где Оз " — (—1)" —(—1)*', если в + Ь " q — 1 + 5 < 2(q — 1);

Пд-1Пд-1 " —По — Пд-1.

Замечание 1.2. Отметим, что оз е

Теорема 1.1 (Люка [8]). Пусть т,п — целые неотрицательные числа, пусть р — простое число. Пусть [т]р " [тз,...,т0] и [п]р " [пз,... ,п0] — р-ичные представления т и п, соответственно. Тогда

{_ {m^^b ' ^

( ) " ( ) mod p.

W UV

Следствие 1.1. Если в условиях предыдущей теоремы для некоторого i e 0, s выполнено m.' < П', тогда (m) " 0 mod p.

2 Совпадения базисных кодов Рида—Маллера со

степенями радикала Шб

Известно, что при А = 1 коды Рида-Маллера являются степенями радикала Шд [1,5], а базисные коды Рида-Маллера при этом совпадают со степенями радикала Шв [2]. Цель данного раздела — показать, что при А Ф 1 подобных совпадений базисных кодов, кроме тривиальных случаев, нет.

Лемма 2.1 ([6]). Количество различных ненулевых степеней равно 1(р — 1). Лемма 2.2. Для всех целых р ^ 2 выполнено неравенство

1(р — 1) ^ т(п — 1), (1)

причём равенство достигается только при А = 1.

Доказательство. Случай А = 1 очевиден. Пусть А > 1, тогда неравенство (1) можно переписать в виде А < . Сокращая в правой части, получаем А < 1 + р + ■ ■ ■ + рх"1. Число слагаемых справа равно А, что завершает доказательство. □

Из лемм 2.1 и 2.2 вытекает, что в общем случае все базисные коды не могут совпадать со степенями радикала. В самом деле, согласно неравенству (1) заключаем, что для любого подполя Р поля Q, кроме простого, количество базисных кодов Рида-Маллера больше количества степеней радикала.

Совпадения базисных кодов со степенями радикала в случае простого подполя описываются следующим утверждением.

Утверждение 2.1 ([2]). Пусть ] е 0,1(р — 1), тогда выполнено равенство

Мр(1,з)= ж^4.

Замечание 2.1. В предыдущем утверждении мы рассматриваем также нулевую степень радикала, которую естественно положить равной Б.

Совпадения базисных кодов со степенями радикала существуют и в случае произвольного непростого подполя Q. Все они являются тривиальными и описываются следующим утверждением.

Утверждение 2.2. Пусть А Ф 1, тогда выполнены равенства

Мп(т, 0) = Мр(1, 0), Мп (т,т(п — 1) — 1) = Мр(1,1(р — 1) — 1), Мп(т, т(п — 1)) = Мр(1,1(р — 1)).

Доказательство. Непосредственно следует из замечания 1.1 и утверждения 2.1. □

Покажем, что при Л Ф 1 других совпадений базисных кодов со степенями радикала нет. Введём необходимые определения.

Определение 2.1. п-записью числа Ь назовём его п-ичное представление и обозначим [Ь]п. Аналогично вводится р-запись. Для Ь е 0, д — 1 отождествим [Ь]п и соответствующий элемент {0,... , п — 1}т. Аналогично отождествим [Ь]р и соответствующий элемент {0,...,р — 1}1. Элементы, составляющие [Ь]п, назовём п-координатами. Аналогично вводятся р-координаты.

Определение 2.2. Для Ь е 0, д — 1 введём понятие Л-группы. Для этого разобьём [Ь]р на т групп, каждая из которых состоит из Л подряд идущих р-координат. Каждую полученную группу назовём Л-группой. Легко видеть, что между Л-группами и п-координатами существует взаимно-однозначное отображение. На множестве Л-групп введём отношение порядка, совпадающее с упорядочиванием по старшинству соответствующих п-координат.

Определение 2.3. Для Ь е 0,д — 1, ¿ е 0, Л — 1 введём понятие ¿-слоя. Для этого каждой р-координате внутри каждой Л-группы Ь присвоим номер от 0 до (Л — 1) в соответствии с упорядочиванием по старшинству р-координат внутри данной Л-группы как элементов [Ь]р. Упорядоченный набор р-координат с номерами г назовём ¿-слоем. Несложно понять, что между элементами ¿-слоя и п-координатами существует взаимно-однозначное отображение. На элементах г-слоя введём отношение порядка, совпадающее с упорядочиванием по старшинству соответствующих п-координат. Если значение г не требует уточнения, будем называть ¿-слой просто слоем.

Определение 2.4. Весом ¿-слоя назовём сумму его элементов.

л

Замечание 2.2. Пусть Ь е 0, д — 1 и г е 0, Л — 1, тогда

[Ь]п = [вт-1,...,во], где в = ад-1 лрЛ—1 + • • • + + • • • + а

[Ь]и " [а Л—1,т— 1, . . . , аг,т— 1 • . • . • а0 , m-1, . . . , а Л-1 ,0, . . . , аг , 0 • . • . • а0 ,0] |

ч,_ _^ ч_ _^

V--V--

Л-группа Л-группа

¿-слой = [а^,т— 2,..., «¿,0].

Определение 2.5. Определим множества и Пк равенствами

Рл = {Ь е Ъ : 0 ^ ^р(Ь) ^ з} , Пк = {Ь е Ъ : 0 ^ шж(Ь) ^ к} .

Лемма 2.3. Пусть з е 0,1 (р — 1). Пусть

в—1

Ь = ^ т(р — 1)рЛ—1—г + трЛ—1

= ^ т(р —

¿"0

где в и т — частное и остаток от деления з на т(р — 1), т.е. з = вт(р — 1) + т, где 0 < т < т(р — 1). Тогда Ь имеет максимальный п-вес среди элементов Рл-.

Доказательство. Построим число Ь максимального п-веса среди элементов Р^-. Для этого необходимо предварительно найти число максимального п-веса среди чисел фиксированного р-веса. Покажем как должен быть распределён р-вес в р-записи искомого числа. Сначала рассмотрим отдельную А-группу и максимизируем её п-вес. Несложно понять, что следует распределить наибольший р-вес в самые старшие разряды, поскольку при этом получается наибольшее значение соответствующей данной А-группе п-координаты. Теперь максимизируем п-вес всех А-групп в совокупности: сначала распределим максимально допустимый р-вес в самый старший разряд каждой из А-групп, затем распределим максимально допустимый р-вес в следующий самый старший разряд каждой из А-групп и т.д. Ясно, что построение р-записи происходит от старшего ¿-слоя к младшему. Легко видеть, что распределение р-веса в пределах одного ¿-слоя не имеет значения в силу того, что элементы одного слоя дают одинаковый вклад в результирующий п-вес. Для определённости р-вес в пределах одного слоя будем распределять от старшей р-координаты к младшей.

Таким образом, нашли число максимального п-веса среди чисел фиксированного р-веса. В самом деле, рассмотрим два числа а и Ь одинакового р-веса: а — произвольное, а Ь получено по указанной выше процедуре. Если веса соответствующих ¿-слоёв а и Ь совпадают, то у этих чисел одинаковый п-вес. Пусть а и Ь отличаются весом некоторых ¿-слоёв, тогда рассмотрим старший среди таких слоёв. Заметим, что вес данного ¿-слоя а меньше веса того же слоя Ь, поскольку последний по построению Ь имеет максимально допустимый вес. Отсюда вытекает, что в а значение какого-то разряда в этом ¿-слое уменьшилось в пользу какого-то разряда в более младшем слое а, т.е. результирующий п-вес а тоже уменьшился по сравнению с Ь. Следовательно, п-вес Ь больше п-веса а.

Легко видеть, что чем больший р-вес зафиксирован в начале, тем больший п-вес имеет построенное число. Значит, число Ь, которое имеет максимальный п-вес среди элементов Р^-, удовлетворяет следующим условиям: во-первых, получено по указанной выше процедуре с точностью до перераспределения р-веса внутри некоторых ¿-слоёв, во-вторых, имеет р-вес равный ]. Без ограничения общности можно считать, что р-запись Ь имеет распределение р-веса полностью совпадающее с вышеизложенной процедурой.

Заметим, что полностью заполненный слой имеет вес т(р — 1). Несложно понять, что в р-записи Ь будут полностью заполнены все слои от (А — 1)-слоя до (А — в)-слоя, а (А — в — 1)-слой имеет вес т, где в и т — частное и остаток от деления ] на т(р — 1). Таким образом, значение Ь можно вычислить по формуле (2), что завершает доказательство. □

Следствие 2.1. В условиях предыдущей леммы имеем шр(£) = ].

Лемма 2.4. Пусть р Ф 2. Пусть ] е 2,1(р — 1) — 2. Пусть Ь определено согласно (2). Тогда в некоторой А-группе Ь разность между старшей и младшей р-координат,ой не меньше 2.

Доказательство. Пусть [Ь]р = [аА-\т-1,... , а0т-1,... , аА-1,0,... , а0,0]. Поскольку ] ^ 2, по построению Ь имеем а\-1т-1 ^ 2. Если а0т-1 = 0, то старшая А-группа Ь является искомой. Пусть а0т-1 > 0, тогда согласно построению Ь получаем

аХ-1,т-1 = аХ-1,т-2 = ■ ■ ■ = аА-1,0 = (р — 1).

Заметим, что в данном случае а0,0 < (р — 2). В самом деле, если а0 0 ^ (р — 2), тогда по построению Ь имеем Ь ^ (д — 2), т.е. шр(Ь) = з ^ 1 (р — 1) — 1, что противоречит условию. Отсюда заключаем, что при а0,т— 1 > 0 младшая Л-группа Ь является искомой. Лемма доказана. □

Лемма 2.5. Пусть р = 2. Пусть з е 2,1 (р — 1) — 2. Пусть Ь определено согласно (2). Тогда хотя бы в двух Л-группах Ь разность между старшей и младшей р-координатой равна 1.

Доказательство. Пусть [Ь]р = [аЛ—1,т—1,... , а0,т—1,... , аЛ—1,0,... , а0,0]. Поскольку з ^ 2, по построению Ь имеем аЛ—1т—1 = аЛ—1,т—2 = 1. Если а0,т—1 = 0, то а0,т—2 = 0 и две самые старшие Л-группы Ь являются искомыми. Пусть а0,т—1 > 0, тогда согласно построению Ь получаем

аЛ—1,т—1 = аЛ—1,т—2 = • • • = аЛ—1,0 = 1.

Заметим, что в данном случае а1,0 = а0,0 = 0. В самом деле, если это не так, тогда по построению Ь имеем шр(Ь) = з ^ 1 (р — 1) — 1, что противоречит условию. Отсюда заключаем, что при а0,т—1 > 0 две самые младшие Л-группы Ь являются искомыми. Лемма доказана. □

Теорема 2.1. Пусть Л Ф 1. Пусть к е 1,т(п — 1) — 2 и з е 1,1 (р — 1) — 2. Тогда имеет место соотношение

Мп(т, к) Ф Мр(/,з).

Доказательство. Рассуждая от противного, предположим, что существуют к, з такие, что имеет место равенство Мп(т, к) = Мр(/,з). Согласно утверждению 1.2 данное равенство эквивалентно тому, что базисы из элементов « указанных идеалов совпадают, что, в свою очередь, равносильно тому, что Рл- = Пк. Покажем, что в этом случае существует число Ь, принадлежащее Пк, но не принадлежащее Рл-, что приводит к противоречию.

Пусть сначала з = 1. В силу равенств шр(рЛ—1) = 1 и (рЛ— 1) = рЛ—1 имеем к ^ рЛ—1. Положим Ь = рЛ + 1. Легко видеть, что шр(Ь) = 2 и (Ь) = 2 ^ рЛ—1 ^ к. Таким образом, получено число Ь такое, что Ь е Пк и Ь ф Рл-.

Пусть теперь з > 1. Пусть Ь определено согласно (2), тогда имеем шр(Ь) = з и (Ь) = к. По леммам 2.4 и 2.5 без ограничения общности можно считать, что в младшей Л-группе Ь разность между старшей и младшей р-координатой не меньше 2 при р Ф 2 и равна 1 при р = 2. Положим Ь1 = Ь + 1. Тогда в силу лемм 2.4 и 2.5 в некоторой Л-группе Ь1 разность между старшей и младшей р-координатой не меньше 1. Несложно понять, что шр(Ь1) = з + 1 и (Ь1) = к + 1.

Рассмотрим следующее преобразование Ь1: внутри каждой Л-группы поменяем местами р-координаты, стоящие на симметричных относительно середины данной Л-группы местах, т.е. переставим первую и последнюю позиции, вторую и предпоследнюю и т.д. Полученное число обозначим Ь.

Легко видеть, что шр(Ь) = шр(Ь1) = з + 1. Заметим, что (Ь) < (Ь1) = к + 1. В самом деле, по построению Ь1 если две р-координаты одной Л-группы находятся на симметричных относительно середины данной Л-группы местах, то значение старшей из них не меньше значения младшей. Значит, при указанном преобразовании общий вклад этих р-координат в

п-вес не увеличится. Однако, в некоторой А-группе Ь' разность между старшей и младшей р-координатой не меньше 1. Отсюда следует, что при рассмотренном выше преобразовании общий вклад этих р-координат в п-вес уменьшится. Таким образом, получено число £ такое, что £ е Пк и £ ф Р^-. Теорема доказана. □

Замечание 2.3. Аналогичный результат для Мп(т,к) и Мр(1,]) неверен: при р = 2, I = 9, А = 3 имеем М8(3, 2) = М2(9,1) и М8(3,18) = М2(9, 7), при р = 3, I = 6, А = 3 имеем М27(2, 6) = М3(6, 2) и М27(2, 45) = М3(6, 9).

Замечание 2.4. Несложно понять, что шп(Ь')—шп(I) ^ рА-1 — 1, причём равенство достигается только при шп(Ь') = 1(р — 1) — 1.

В работах, посвящённых кодам Рида-Маллера, основное внимание, как правило, уделено совпадению данных кодов со степенями радикала при А = 1, а случай А Ф 1 рассматривается менее детально. Согласно теореме 2.1 при А Ф 1 нет нетривиальных совпадений между базисными кодами Рида-Маллера и степенями радикала Шв. В разделе 6 получен аналог данной теоремы для обычных кодов Рида-Маллера. Далее, если не указано дополнительно, будем считать, что А Ф 1 .

3 Строение графа включений базисных кодов и

степеней радикала

Рассмотрим граф включений базисных кодов Рида-Маллера и степеней радикала Шя, т.е. ориентированный граф, в котором вершины соответствуют указанным идеалам, и между двумя идеалами проходит дуга, когда один из них есть подмножество другого; при этом начало такой дуги — вершина, соответствующая надмножеству, а конец — вершина, соответствующая подмножеству. В данном графе есть два маршрута: маршрут, соответствующий включениям идеалов Мп(т, к) между собой, и маршрут, соответствующий включениям степеней радикала Шя между собой. Согласно утверждениям 2.1 и 2.2 данные маршруты имеют три общие вершины, соответствующие тривиальным совпадениям. Отметим, что первый маршрут значительно длиннее второго. Далее рассматриваются графы после проведения транзитивной редукции, т.е. после удаления всех рёбер, не влияющих на связность между любыми двумя вершинами.

Естественно возникает вопрос: есть ли какие-то включения, кроме включений внутри указанных маршрутов? В данном разделе мы покажем, что такие включения существуют, и дадим их числовое описание.

Список литературы диссертационного исследования кандидат наук Тумайкин, Илья Николаевич, 2017 год

Список литературы

[1] Берман С.Д. К теории групповых кодов // Кибернетика. 1967. Т. 3, № 1. С. 31-39.

[2] Коусело Е., Гонсалес С., Марков В.Т., Мартинес К., Нечаев А.А. Представления кодов Рида-Соломона и Рида-Маллера идеалами // Алгебра и логика. 2012. Т. 51, № 3. С. 297-320.

[3] Лидл Р., Нидеррайтер Г. Конечные поля. М.: Мир, 1988.

[4] Assmus E.F. Jr., Key J.D. Polynomial codes and finite geometries // Handbook of Coding Theory. Amsterdam: Elsevier, 1998. Vol. 2. P. 1269-1343.

[5] Charpin P. Une generalisation de la construction de Berman des codes de Reed et Muller p-aires // Communications in Algebra. 1988. Vol. 16, № 11. P. 2231-2246.

[6] Jennings S.A. The structure of the group ring of a p-group over a modular field // Trans. Amer. Math. Soc. 1941. Vol. 50, № 1. P. 175-185.

[7] Landrock P., Manz O. Classical codes as ideals in group algebras // Designs, Codes and Cryptography. 1992. Vol. 2, № 3. P. 273-285.

[8] MacWilliams F.J., Sloane N.J.A. The Theory of Error-Correcting Codes. Amsterdam: North Holland, 1977.

[9] Moore E.H. A two-fold generalization of Fermat's theorem // Bull. Amer. Math. Soc. 1896. Vol. 2, № 7. P. 189-199.

[10] Roman S. Field Theory. New York: Springer, 2006.

Работы автора по теме диссертации

[11] Тумайкин И.Н. Базисные коды Рида-Маллера и их связь со степенями радикала групповой алгебры над непростым полем // Вестник Московского университета. Серия 1, Математика. Механика. 2013. № 6. С. 46-49.

[12] Тумайкин И.Н. Базисные коды Рида-Маллера как групповые коды // Фундаментальная и прикладная математика. 2013. Т. 18, № 4. С. 137-154.

[13] Тумайкин И.Н. Коды Рида-Маллера как групповые коды // деп. в ВИНИТИ РАН 01.03.2017, № 23-В2017. 29 с.

Приложение: графы включений базисных кодов Рида—Маллера и степеней радикала

Частные случаи основных результатов разделов 2, 3, 4 были сначала смоделированы и получены с помощью системы компьютерной алгебры GAP. Для построения графов включений базисных кодов Рида-Маллера и степеней радикала автором была написана программа на языке C. Исходный код данных программ доступен в Интернете по адресу https: //github.com/Coacher/rmc-inclusion. Приведём здесь некоторые из полученных графов.

(а) р = 2,1 = 4, Л = 4. (Ь) р = 2,1 = 6, Л = 2.

Рис. 1: Графы включений при небольших значениях параметров.

При увеличении значений параметров количество вершин в графе также возрастает. Особенно быстро растёт количество идеалов Мп(т, к). Количество степеней радикала растёт медленнее. Полезны следующие упрощения: будем изображать только те из вершин Мп(т, к), которые связаны хотя бы одним ребром с некоторой степенью радикала, и группировать отдельно вершины, соответствующие степеням радикала и базисным кодам.

Рис. 2: Упрощённый граф включений для р = 2, / = 9, Л = 3.