О теоретико-числовых задачах в теории кодирования тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

На правах рукописи

СЕМЕНОВЫХ Денис Николаевич

О ТЕОРЕТИКО-ЧИСЛОВЫХ ЗАДАЧАХ В ТЕОРИИ КОДИРОВАНИЯ

01.01.06 - математическая логика, алгебра и теория чисел 01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

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

фсГ

Москва 2006

Работа выполнена на кафедре теории чисел Механико-математического факультета МГУ им. М.В. Ломоносова

Научный руководитель: кандидат физико-математических наук,

доцент Черепнев Михаил Алексеевич

Официальные оппоненты: доктор физико-математических наук

профессор

Сидельников Владимир Михайлович, кандидат физико-математических наук Карпунин Григорий Анатольевич

Ведущая организация: Институт проблем передачи информации РАН

Защита диссертации состоится 13 октября 2006 г. в 16 ч. м. на заседании диссертационного совета Д.501.001.84 в Московском государственном университете им. М.В. Ломоносова по адресу: 119992, ГСП-2, Москва, Ленинские горы, МГУ, Механико-математический факультет, ауд. 14-08.

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета (Главное Здание, 14 этаж).

Автореферат разослан 13 сентября 2006 г.

Ученый секретарь диссертационного совета Д.501.001.84 в МГУ, доктор физико-математических наук, профессор

В.Н. Чубариков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Диссертация посвящена некоторым теоретико-числовым вопросам, связанным с теорией кодов, исправляющих ошибки. Затрагиваются коды, представляющие собой линейные подпространства в конечномерном линейном пространстве F" над произвольным конечным полем Fq, и потому называемые линейными.

Актуальность темы. Теория линейных кодов, исправляющих ошибки - это область математики, возникшая и получившая бурное развитие сравнительно недавно - во второй половине XX века. Для получения результатов в этой области активно используются алгебраические, теоретико-числовые и, в последнее время, в связи с возникновением ал-геброгеометрических кодов, алгеброгеометрические методы. В данной диссертации затрагиваются некоторые теоретико-числовые задачи, возникающие в теории кодирования. Одна из таких задач связана с построением линейных кодов, исправяющих ошибки, на основе вычетов степени n, n е N, п > 2 по модулю простого числа р.

В 1963 году и немного позднее Ассмус и Мэттсон опубликовали цикл работ (например 1 2), в которых они дали описание конструкции линейных квадратично-вычетных кодов. А именно, рассмотрим р и I - простые числа, такие, что I является квадратичным вычетом по модулю р. Пространством, в котором будет строиться код, является факторкольцо

Rp = F¡[x]/(a?- 1).

Обозначим через Q множество квадратичных вычетов, а через N - множество квадратичных невычетов по модулю р. Найдя поле, содержащее поле Fi, в котором многочлен хр — 1 раскладывается на линейные множители и обозначив через а какой-либо элемент, порождающий циклическую группу корней из единицы степени р в этом поле, будем рассматривать следующие многочлены:

q(x) = П (ж - а1") и п(х) = Д(ж -а").

reC? n€N

Можно показать, что данные многочлены лежат в F¡ [х]. __ Тогда идеалы £ = (д(х)), £ = ((х — l)g(cc)), а также ОТ = (п(х)), 9Í = ((х — 1)п(х)) в кольце Rp, порожденные, соответственно, многочленами q{x), (х — l)q(x), п(х), (х — 1)п(х), называются квадратично -вычетными кодами.

IE.F. Asamua, Jr., H.F. Matt-son, Jr., Error-correcting codcs: An axiomatic approach, Info, and Cont.ro!. 6 (1963) 315-330

ZE.F. Assmua, Jr., H.F. MetbUon, Jr., On tactical configurations and crior-correcting codes, J. Comb. Theory, 2 (196T) 243-257

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

длина кода п = р -выбранное ранее простое число;

размерность кода к = ^ - для кодов £, УХ;

к = ^ - для кодов £, Ш; кодовое расстояние d > у/р.

Подробное доказательство этого результата можно найти также в книге 3.

Позднее были получены многочисленные интересные свойства описанных выше кодов. В частности, Паттерсон выписал порождающие идем-потенты таких кодов, однако, как утверждают Ф. Мак-Вильямс и Н. Слоэн, этот результат остался неопубликованным. При рассмотрении так называемых расширенных квадратично-вычетных кодов, получаемых из обычных кодов путем добавления проверки на четность, была установлена мощная группа автоморфизмов, относительно действия которой на множестве координатных позиций код является инвариантным. Эта группа обозначается Р5Хг(р) и является множеством всех подстановок вида

у —> a,b,c,d € GF(p), ad—Ьс— 1.

су + а

- Наличие большой группы автоморфизмов позволяет применять эффективные алгоритмы декодирования (например, перестановочное декодирование, введенное в 1959 году Прэнджем.

Все упомянутые свойства при своем обосновании существенно используют одно важное утверждение, которое было доказано в 1952 году О.Перроном Это свойство позволяет устанавливать распределение квадратичных вычетов и невычетов в множестве чисел, полученных в результате сложения всех квадратичных вычетов (или, соответственно, невычетов) по модулю простого числа р с одним и тем же числом а, взаимно простым с р.

Актуальность задачи обобщения квадратично-вычетных кодов на случай вычетов более высоких степеней, поставленной перед автором, обусловлена тем, что при наличии довольно хорошей нижней оценки на кодовое расстояние (d > у/р), второй важный параметр - относительная

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

Другая теоретико-числовая задача, рассматриваемая в диссертации, связана с гиперэллиптическими кривыми, рассмматриваемыми над конечным полем К характеристики 2. Для фиксированного дивизора И, определенного на данной кривой X, можно рассмотреть пространоство Римана-Роха, задаваемое на множестве ¥Ч(Х) рациональных функций, определенных на кривой, следующим образом:

ЦБ) = {/ е I (Л + о > о} и {о},

В 1981 году в статье 5 В.Д.Гоппа впервые упоминает про алгеброгео-метрические коды. Речь идет о следующей конструкции (которая имеет несколько эквивалентных формулировок).

Пусть Р = {Р\,Р2, • • •, Рп} - произвольное подмножество точек, лежащих на кривой X. Выберем дивизор О — принадлежащий множеству ]Эгу(Рч), так, чтобы выполнялось следующее условие:

Бирр И П Р = 0,

где Бирр И = { | тгц ф 0 }.

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

Еур : ¿(£>) - Г?, /~(/(Р1),...,/(Р„)).

Образ этого отображения Еир(Ь(П) является линейным кодом. Этот код мы будем обозначать С = (X, Р, £>)/,. Можно также рассматривать код С1-, двойственный к коду С и являющийся, по определению, ортогональным дополнением к линейному пространству Еьр(Ь{0)).

Таким образом, для построения данного кода требуется умение явно вычислять базис пространства Римана-Роха. Более того, необходимость явно выписывать такой базис для разных дивизоров возникает также при использовании описанных в литературе алгоритмов кодирования-декодирования е.

Решаемая автором задача выписывания такого базиса для гиперэллиптических кривых, рассматриваемых над полем характеристики 2, основана на результатах опубликованной в 1996 году статьи 7, согласно которой для так называемого приведенного дивизора D = ^ mjPj, где Pi(xi, j/j), можно найти однозначно определенную пару многочленов а{и) и Ь(и), строящуюся следующим образом.

В качестве многочлена o(w) берется многочлен а(и) = Д(и — x;)mi. Тогда, согласно результатам указанной статьи, можно найти единственно определенный многочлен Ь(и), обладающий свойствами:

1) degub(u) < degua(u) < д,

2) b(Xi) = yi,

3) o(u) делит многочлен N(v — b{u)) = b(u)2 + b(u)h(u) — f{u).

Базис пространства Римана-Роха строится на основе задания полуприведенного дивизора D такой парой многочленов.

Цель работы. В процессе написания настоящей диссертационной работы преследовались две основные цели.

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

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

Научная новизна результатов диссертации.

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

и относительную скорость передачи таких кодов. При этом последняя оценка оказывается лучше, чем в известных аналогичных случаях, и с возрастанием числа п она стремится к 1.

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

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

Практическая значимость работы.

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

Для кодов на основе вычетов третьей и четвертой степеней явно выписан порождающий идемпотент и порождающая матрица.

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

Публикации. Оба результата настоящей диссертации опубликованы в двух статьях, одна их которых депонирована в ВИНИТИ РАН.

Структура и объем диссертации. Диссертация состоит из списка обозначений, введения, обсуждения результатов, вычислительного приложения и списка цитируемой литературы. Работа изложена на 80 страницах машинописного текста.

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

СОДЕРЖАНИЕ РАБОТЫ

В первой главе приведен краткий обзор исследований, связанных с содержанием данной диссертации. Даются основные определения и вводятся основные объекты, связанные с теорией кодирования - линейные коды, их порождающие и проверочные матрицы, параметры (блоковая длина, относительная скорость передачи и минимальное кодовое расстояние). Большую роль в теории кодирования играет изучение границ, накладывающих различные ограничения на возможные значения параметров кодов, поэтому в обзоре приводятся некоторые известные на сегодняшний день оценки параметров линейных кодов (границы Синглтона, Хемминга, Плоткина, линейного программирования и достаточное условие существования кода - условие Варшамова-Гилберта). Упоминается основная асимптотическая задача теории кодирования, связанная с существованием так называемых асимптотически хороших семейств кодов, описывается в связи с этим граница Варшамова-Гилберта, обладающая интересными статистическими свойствами.

Одним из основных объектов диссертации являются квадратично-вычетные коды, которые являются циклическими кодами, поэтому в первой главе также даны основные определения и результаты, связанные с циклическими кодами. Более подробно рассмотрен важный частный случай циклических кодов - БЧХ-коды.

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

Во второй главе диссертации исследуются линейные коды, основанные на квадратичных вычетах по модулю простого числа р. Эти коды являются циклическими. Известно, что такие коды имеют довольно хорошую нижнюю оценку одного из важнейших параметров - кодового расстояния, а именно оценку й > у/р. Однако у них есть существенный недостаток, связанный с тем, что другой важный параметр - относительная скорость передачи кода - независимо от блоковой длины всегда равен 1/2, что делает затруднительным применение таких кодов на практике. Исходя из этих соображений, в диссертации строится обобщение таких кодов на случай вычетов более высоких степеней по модулю простого числа р, что позвояет улучшить значение этого параметра.

Пусть тг - натуральное число, п > 2, а простое число р выбрано так, что число 2 является вычетом степени п по модулю р. Будем строить

двоичные коды, определив предварительно следующие h — (п,р — 1) классов:

Qi = {г е Fp*|r = дк, к е Z, 0 < к < р - 2, к = i (mod Л)},

г = 0,... ,Л — 1,

где g - произвольный порождающий элемент группы F*. Далее зафиксируем кольцо Rp = F2\x]/{xp — 1), произвольный идеал которого является циклическим кодом 8. Обозначив через а произвольный примитивный корень степени р из единицы, лежащий в некотором расширении поля F2, введем в рассмотрение следующие h многочленов:

П>-аГ)> г = 0,..., Л — 1.

r€Qi

В диссертации показывается, что данные многочлены принадлежат кольцу -РгМ- Поэтому для каждого числа i — 0,... ,Л — 1 можно рассмотреть идеалы £j в кольце Rp, порождающим многочленом которых служат, соответственно, многочлены <?<(х). Заметим, что данные порождающие многочлены задаются лишь своими корнями; для эффективного же задания таких многочленов требуется проводить вычисления их коэффициентов в конечном поле i*2. Для того, чтобы избежать этих вычислений, далее для каждого кода будет найден другой многочлен, порождающий этот код, с помощью которого задача эффективного описания кода становится более простой.

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

Теорема 1

1) Длина кода (длина каждого кодового слова) равна р.

2) Размерность кода равна р — deg qi(x) = р — а относительная скорость передачи 1 — ^ +

3) Все коды £,■ эквивалентны друг другу и получаются друг из

друга некоторой перестановкой координатных позиций.

4) Кодовое расстояние d удовлетворяет неравенству d > typ.

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

Если сравнивать параметры полученных кодов с параметрами другого широко известного класса циклических кодов - БЧХ-кодами, то нижние границы параметров примитивных БЧХ-кодов имеют несколько лучшую асимптотику (имеются в виду случаи, в которых сравниваются коды над полем построенные с помощью вычетов степени п блоковой длины р, где р - простое число, и примитивные БЧХ-коды такой же блоковой длины, то есть случаи, когда число р имеет вид р = 2т — 1). Однако у БЧХ-кодов имеется один существенный недостаток, связанный со сложностью построения в явном виде порождающего многочлена, который, по определению, является многочленом наименьшей степени, имеющий своими корнями а, а2,... , а*-1 для некоторого натурального числа 6, где а - примитивный элемент поля В рассматриваемых нами кодах, обобщающих квадратично-вычетные коды, в случае вычетов третьей и четвертой степеней в явном виде построен многочлен, порождающий код, для выписывания коэффициентов которого достаточно указать все вычеты третьей и четвертой степени соответственно по модулю простого числа р.

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

Определение 1 Многочлен Е(х) € Яр - идемпотент, если в Яр выполнено равенство Е2(х) = Е(х).

Рассмотрим также следующие многочлены: Т;(х) = хТ, г = О, Л — 1.

гее*

Определение 2 Скажем, что семейство кодов £{ имеет распределение (ао, а1,..., аь-х), а,{ € {0,1}, если для некоторого а - примитивного корня из 1 степени р - справедливы равенства:

Т0(а) = а0, 71 (а) = аь ..., ТЛ_ 1(а) = аЛ_ 1.

Для случаев Л = 3 и Л = 4 доказаны следующие теоремы.

Теорема 2 (Случай кубических вычетов) При /г = 3 элемент а -примитивный корень степени р из единицы - можно выбрать таким образом, что порождающими идемпотентами Е,(х) кодов и порождающими идемпотентами Е^(х) кодов будут являться, соответственно, многочлены:

Е,(:г) = Г3_<(х) + 1, ~Щх) = ад.

лУЗ-г

Теорема 3 (Случай биквадратичных вычетов) При h = 4 элемент а - примитивный корень степени р из единицы - можно выбрать таким образом, что

1) В случае р ее 1 (mod 16) код £< имеет распределение (1,0,0,0)

и идемпотенты Ei(х) — Т4-,(х) + 1, Е<(х) = £ Tj(x).

¡фА-i

2) В случае р = 9 (mod 16) код £j имеет распределение (0,1,1,1)

и идемпотенты Ei{x) — 7}(ж) + 1, Ei{x)— Т^{х).

j/4-t

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

Построение в явном виде порождающего многочлена позволяет эффективно строить порождающую матрицу, то есть позволяет полностью описать код.

Третья глава диссертации посвящена рассмотрению гладких гиперэллиптических кривых над конечным полем К характеристики 2 и ал-геброгеометрических кодов, построенных по таким кривым.

Пусть К - конечное поле характеристики 2, К - его алгебраическое замыкание. Рассмотрим гиперэллиптическую кривую X над полем К рода д, заданную уравнением

V2 + h(u)v = /(it), (1)

где h(u) 6 К [и] - многочлен степени не выше д, f(u) Е K[v] - многочлен степени 2д + 1. Дополнительно будем предполагать выполненным условие гладкости рассматриваемой гиперэллиптической кривой, которое заключается в отсутствии решений (и, v) € К х К следующей системы уравнений 9:

{V2 + h(u)v = f(u), 2v + h{u) = 0, h'(u)v - /'(и) = 0.

Для каждой точки Р = Р(х, у) будем рассматривать сопряженную к ней точку Р ~ Р{х, —у — h(x)).

Зафиксируем произвольный дивизор D, определенный на кривой: D = трР + sоо. Одним из основных объектов, тесно связанных с алгеброгеометрическими кодами, построенными по таким кривым, является пространство Римана-Роха, имеющее в литературе стандартное обозначение L(D):

L(D) = {fe F?(xr I (/) + D > 0 } U { 0 }.

Известно, что пространство Римана-Роха является конечномерным линейным подпространством в пространстве рациональных функций на кривой. В диссертации предлагается построение базиса данного линейного пространства над полем К для приведенного дивизора D.

Метод, с помощью которого строится такой базис, основан на задании приведенных (и полуприведенных) дивизоров, определенных на рассматриваемой гиперэллиптической кривой, парой многочленов. В настоящее время в литературе имеются работы, использующие такой способ задания дивизоров для построения эффективных вычислительных алгоритмов в группе классов идеалов кольца К[х,у], целозамкнутого в своем поле частных К(х, у), где К{х, у) - поле рациональных функций на гиперэллиптической кривой. В данной диссертации продемонстрировано, каким образом можно применять такое задание приведенного дивизора для определения порядка произвольной функции, принадлежащей пространству L(D), соответствующему данному дивизору D, и, тем самым, для построения базиса этого пространства. Линейно независимые функции, принадлежащие множеству L[D), строятся с помощью удобного критерия, основанного на разложении функций в ряд по степеням локального параметра. С помощью этого же критерия исследуется полнота полученной системы функций.

Итак, найдем для приведенного дивизора D = тпрР + soo однозначно определенную связанную с ним пару многочленов а{и) и Ь{и), лежащих в пространстве К [и]. Метод нахождения такой пары многочленов указан, например, в работе 10.

Рассмотрим далее вспомогательное пространство

(L(D))U = {/ е K(u,vY | uP(f) > -uP{D) для всех

конечных точек Р} U {0}.

Пусть теперь D = Найдем для данного дивизора соответ-

ствующую ему пару многочленов точно также, как это делалось для дивизора D. Для дивизора D многочлен а(и) будет в точности совпадать

с соответствующим многочленом для дивизора D. Второй же многочлен будет отличаться от многочлена Ь(и), найденного для дивизора D. Обозначим этот многочлен через Ь(и).

В диссертации доказывается следующая теорема.

Теорема 4 Функции

V — Ь(и) u>i =-г-г- li Ш2 = 1

образуют базис пространства (L{D))U над кольцом К[и\.

Доказательство данной теоремы существенным образом опирается на результаты статьи 11, в частности, использован критерий принадлежности рассматриваемому линейному пространству, а также критерий линейной независимости произвольного набора рациональных функций, определенных на кривой.

Пусть А — i^ooC^i) = 2£)mp — 2g — 1 - порядок функции шу в бесконечно удаленной точке. Далее доказывается теорема о структуре базиса пространства L(D).

Теорема 5 Пусть D = Y2 mpP+soo - приведенный дивизор, для которого А + s > 0. Тогда базис пространства L(D) над полем К задается следующими функциями:

ГА + з'

{Лл}, {U3üji = 0 < г < —-—

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

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

1. Семеновых Д.Н. Обобщение квадратично-вычетных кодов на случаи вычетов третьей и четвертой степени Дискретная математика, т. 17, 2005, №4, с. 143-149

2. Семеновых Д.Н. Построение базиса пространства Римана-Роха на гиперэллиптических кривых. Рукопись деп. в ВИНИТИ 13.12.2005 JV« 1653-В2005

11J. Coates "Construction of rational functions on a curve", Proc. Camb. Soc., 1970, 68, 105

Издательство ЦПИ при механико-математическом факультете МГУ им. М.В, Ломоносова. Подписано в печать /(. 03, Об

Формат 60 х 90 1/16. Усл. псч. л. I, С

Тираж 100 экз. Заказ £(!>

г - ív-fi,

Список обозначений

Введение

Описание результатов диссертации.

1 Обзор исследований, связанных с содержанием работы

1 1 Краткий обзор основных понятий теории кодирования.

1 2 Некоторые классические оценки параметров кодов

1 3 Циклические коды как пример линейных кодов. . . 21 1 4 Алгеброгеометрические коды Основные определения

2 Квадратично-вычетные коды и их обобщение на случай вычетов более высоких степеней.

2 1 Квадратично-вычетные коды Основные определения и историко-библиографические замечания 32 2 2 Обобщение квадратично-вычетных кодов на случай вычетов высших степеней.

2.3 Построение порождающих идемпотентов для квадратично-вычетных кодов третьей и четвертой степени

3 Построение базиса пространства Римана-Роха на гиперэллиптических кривых.

3 1 Основные определения и постановка задачи. . . . 51 3 2 Разложение рациональных функций по степеням локального параметра в точке.

3.3 Представление приведенного дивизора парой многочленов и доказательство основной теоремы.

Вычислительное приложение.

Список обозначений

С — линейный код

Сх — код, двойственный коду С

1гтС — размерность линейного пространства, размерность кода

Ап — п-кратное декартово произведение множества А

О^д) — конечное поле из q элементов К — конечное поле а(ж)) — главный идеал, порожденный многочленом а(х) с1 — транспонированная вектор-строка п, к, — линейный код с блоковой длиной п, размерностью к и кодовым расстоянием й, рассматриваемый над конечным полем из элементов биномиальный коэффициент

Рч[х\ — кольцо многочленов одной переменной х с коэффициентами из ПОЛЯ.Рд

Рц(х) — поле рациональных функций одной переменной х с коэффициентами из поля Рч РЧ{Х), К(и,у) — поле рациональных функций на кривой X, определенной над полем Рч, К а | Ь — число а делит число Ь а(х) | Ь(х) — многочлен а(х) делит многочлен Ь(х) Gíа^(F9/F(/) — группа Галуа расширения^/^ группаР9-дивизоров

Р* — мультипликативная группа поля Р виррИ — носитель дивизора И, множество точек, входящих в дивизор О с ненулевым коэффициентом (1едБ — степень дивизора В

Кр — факторкольцо^ [ж] / (хр — 1), ^ [ж] / (хр — 1)

X, — код, построенный по кривой X, множеству Р и дивизору И с помощью ¿-конструкции граница Варшамова-Гилберта Н>туг{$) — граница Цфасмана-Влэдуца-Цинка

5 — множество квадратичных вычетов по модулю простого числа р

N — множество квадратичных невычетов по модулю простого числа р £, 91 — квадратично-вычетные коды расширенные квадратично-вычетные коды

РбХгОэ) — дробно-линейная группа ги£(а) — вес Хемминга вектора а

Р — точка на гиперэллиптической кривой, сопряженная к точке Р иРх(Л ~~ порядок рациональной функции / на гиперэллиптической кривой в точке Рх у)\(х,у) ~ значение функции /(и, у) в точке с координатами я, у)

Описание результатов диссертации.

Диссертация посвящена некоторым теоретико-числовым вопросам, связанным с теорией кодов, исправляющих ошибки Затрагиваются коды, представляющие собой линейные подпространства в конечномерном линейном пространстве над конечным полем и потому называемые линейными.

В первой главе приведен краткий обзор исследований, связанных с содержанием данной диссертации. Даются основные определения и вводятся основные объекты, связанные с теорией кодирования - линейные коды, их порождающие и проверочные матрицы, параметры (блоковая длина, относительная скорость передачи и минимальное кодовое расстояние). Большую роль в теории кодирования играет изучение границ, накладывающих различные ограничения на возможные значения параметров кодов, поэтому в обзоре приводятся некоторые известные на сегодняшний день оценки параметров линейных кодов (границы Синглтона, Хемминга, Плоткина, линейного программирования и достаточное условие существования кода -условие Варшамова-Гилберта) Упоминается основная асимптотическая задача теории кодирования, связанная с существованием так называемых асимптотически хороших семейств кодов, описывается в связи с чтим граница Варшамова-Гилберта, обладающая интересными статистическими свойствами.

Одним из основных объектов диссертации являются квадратично-вычетные коды, которые являются циклическими кодами, поэтому в обзоре также даны основные определения и результаты, связанные с циклическими кодами. Более подробно рассмотрен важный частный случай циклических кодов - БЧХ-коды.

Другой основной объект диссертации - пространство Римана-Роха £(£)), являющееся линейным подпространством в пространстве рациональных функций, рассматриваемых на алгебраических кривых. С пространс твом Римана-Роха тесно связаны алгеброгеометрические коды, определение которых, оценки параметров, а также основной метод декодирования также приведены в первой главе

Во второй главе диссертации исследуются линейные квадратично-вычетные коды, основанные на квадратичных вычетах по модулю простого числа р Эти коды являются циклическими. Известно, что такие коды имеют довольно хорошую нижнюю оценку одного из важнейших параметров - кодового расстояния, а именно оценку d > у/р. Однако у них есть существенный недостаток, связанный с тем, что другой важный параметр - относительная скорость передачи кода -независимо от блоковой длины всегда равен 1/2, что делает затруднительным применение таких кодов на практике. Исходя из этих соображений, в диссертации строится обобщение таких кодов на случай вычетов более высоких степеней по модулю простого числа р.

Пусть п - натуральное число, п > 2, а простое число р выбрано так, что число 2 является вычетом степени п по модулю р Будем строить двоичные коды, определив предварительно следующие h классов:

Qi = {г € F*\r = дк, к е Z, 0 < к < р - 2, к = г (mod h)}, г = 0,., h — 1, где д - произвольный порождающий элемент группы F*,h = (п,р— 1) Далее зафиксируем кольцо Ftp = F2[x]/{xp — 1), произвольный идеал которого является, как известно, циклическим кодом (подробнее см стр. 21). Обозначив через а произвольный первообразный корень степени р из единицы, лежащий в некотором расширении поля F2, введем в рас смотрение следующие h многочленов:

Я*(х)= ДОе-оТ), г = 0,., /г — 1. reQ,

Можно доказать (см стр. 39), что данные многочлены принадлежат кольцу F2[x\. Поэтому для каждого числа г = 0,., h — 1 можно рассмотреть идеалы £г в кольце Др, порождающим многочленом которых служат, соответственно, многочлены дг(х).

Для полученных таким образом кодов доказывается следующая теорема (см. подробнее стр. 40).

Теорема 1

1) Длина кода (длина каждого кодового слова) равна р.

2) Размерность кода равна р — ¿ед дДж) = р — а относительная скорость передачи 1 — ^ +

3) Все коды £г друг другу эквивалентны и получаются друг из друга некоторой перестановкой координатных позиций.

4) Кодовое расстояние в, удовлетворяет неравенству й > ^р.

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

Если сравнивать параметры полученных кодов с параметрами другого широко известного класса циклических кодов - БЧХ-кодами, то нижние границы параметров примитивных БЧХ-кодов имеют несколько лучшую асимптотику (имеются в виду случаи, в которых сравниваются коды над полем ^2, построенные с помощью вычетов стенени п блоковой длины р, где р - простое число, и примитивные БЧХ-коды такой же блоковой длины, то есть случаи, когда число р имеет вид р = 2т — 1). Однако у БЧХ-кодов имеется один существенный недостаток, связанный со сложностью построения в явном виде порождающего многочлена, который, по определению, является многочленом наименьшей степени, имеющий своими корнями а, а2,., а*5-1 для некоторого натурального числа 6, где а - примитивный элемент поля ^т. В рассматриваемых нами кодах, обобщающих квадратично-вычетные коды, в случае вычетов третьей и четвертой степеней в явном виде построен многочлен, порождающий код (порождающий идемпотент), для выписывания которого достаточно указать все вычеты третьей и четвертой степени по модулю простого числа р.

Определим следующие многочлены: Тг(х) = ]Г) хг, г = 0, h — 1 reQ,

Для случаев h = 3 и h = 4 доказаны следующие теоремы (см подробнее стр. 47, 48)

Теорема 2 (Случай кубических вычетов) При h = 3 примитивный корень а можно выбрать таким образом, что порождающими идемпотентами Ег(х) кодов £г и порождающими идемпо-тентами Ег(х) кодов £г будут являться, соответственно, многочлены

Ег{х) = Т3г(х) + 1, Щх) = ^ Tj(x).

Теорема 3 (Случай биквадратичных вычетов) При h = 4 примитивный корень а можно выбрать таким образом, что

1) В случае р = 1 (mod 16) код £г имеет распределение (1,0,0, 0) и идемпотенты Ег(х) = Т^-г{х) + 1, Ег{х) = Т3{х).

4-г

2) В случае р = 9 (mod 16) код £г имеет распределение (0,1,1,1) и идемпотенты Ег(х) = Т3(х) + 1, Ег{х) = Т4г(х).

4-г

В данных теоремах под термином "распределение"понимается набор чисел (ао, ai,., a^-i), аг € {0,1}, в котором для некоторого а - примитивного корня из 1 степени р - выполнены равенства

Т0(а) = ао, Т\(а) = а\, ., Th-i(a) = ahь

Теоремы 3 и 4 позволяют эффективно выписывать многочлены, порождающие соответствующие коды (правда, они уже не являются многочленами наименьшей степени, порождающими код) Действительно, для выписывания таких многочленов достаточно лишь, зная число р, воспользоваться таблицами вычетов третьей и четвертой стенени по модулю что го числа р

Построение в явном виде порождающего многочлена позволяет эффективно строить порождающую матрицу, то есть позволяет полностью описать код

Материал второй главы диссертации отражен в статье автора [42].

Третья глава диссертации посвящена рассмотрению гладких гиперэллиптических кривых над конечным полем К характеристики 2 и алгеброгеометрических кодов, построенных по таким кривым. Одним из основных объектов, связанных с такими кодами, является пространство Римана-Роха, имеющее в литературе стандартное обозначение Ь(О), где И - некоторый дивизор, определенный на кривой Известно, что пространство Римана-Роха является конечномерным линейным подпространством в пространстве рациональных функций, определенных на кривой. В диссертации предлагается построение базиса данного линейного пространства для приведенного дивизора В (см. подробнее стр 52)

Метод, с помощью которого строится такой базис, основан на задании приведенных (и полу приведенных) дивизоров, определенных на рассматриваемой гиперэллиптической кривой, парой многочленов В настоящее время в литературе имеются работы, использующие такой способ задания дивизоров для построения эффективных алгоритмов, позволяющих проводить вычисления в группе классов идеалов кольца К[х,у], целозамкнутого в своем поле частных К(х,у), где К(х,у) - поле рациональных функций на гиперэллиптической кривой, определенной над некоторым конечным полем К. В данной диссертации продемонстрировано, каким образом можно применять такое задание приведенного дивизора для определения порядка произвольной функции, принадлежащей пространству Ь(О), соответствующему данному дивизору £), и, тем самым, для построения базиса этого пространства Линейно независимые функции, принадлежащие множеству L(D), строятся с помощью удобного критерия, основанного на разложении функций в ряд по степеням локального параметра. С помощью этого же критерия исследуется полнота полученной системы функций

Итак, найдем для приведенного дивизора D единственно определенную связанную с ним пару многочленов a(w) и Ь(и), лежащих в пространстве К [и].

Рассмотрим далее вспомогательное пространство

L(D))U = {fe К{и, v)* | Mf) > ~MD) для всех конечных точек Р} U {0}.

Доказывается следующая теорема Теорема 4 Функции v — Ь(и) ui =-7 \ и и>2 = 1 а{и) образуют базис пространства (L(D))U над кольцом К [и].

Используя найденные в теореме 4 функции и cj2, далее доказывается теорема структуре базиса пространства L(D)

Теорема 5 Пусть D = + so° " приведенный дивизор, для которого А + s > 0. Тогда базис пространства L(D) задается следующими функциями:

А + s' u1uji}, {и]ш2 = uJ}, 0 < г < 0<j< 2

В данной теореме под числом А обозначен порядок l>oo ) = 2 У^тр — 2g — 1 s" 2. функции и}\ в бесконечности.

Построение в явном виде такого базиса решает задачу явного описания алгеброгеометрического кода на гиперэллиптических кривых, так как позволяет строить порождающую и проверочную матрицы таких кодов, а также может применяться в основном алгоритме декодирования, в котором требуется неоднократный поиск базиса пространства Ь(И) для разных дивизоров Б.

Материал третьей главы диссертации отражен в статье автора

43]

Результаты работы программы (приведены файлы, созданные в результате работы программы, интерпретацию этих результатов см. выше).

При р = 31

Enter the prime number p: 31

Enter the degree of residue (3 or 4): 3

Prime element=3

Idempotent is: 1110100010000001100000010001011 The new minimum of weight is:11 The word of this weight is: 1000000000000000000000000000000*Idempotent(x) The word is: 1110100010000001100000010001011 The new minimum of weight is:10 The word of this weight is: 1111111100000000000000000000000*Idempotent(x) The word is: 0100001001001110000000001110010 The new minimum of weight is:8 The word of this weight is: 1010000101000000000000000000000*Idempotent(x)

The word is: 0100000010000100101000101001000 The new minimum of weight is:7 The word of this weight is: 1100111101000000000000000000000*Idempotent(x) The word is: 1000000010001010000100000100001 The new minimum of weight is:6 The word of this weight is: 1101101101100000000000000000000*Idempotent(x) The word is: 1000000000100100000011000000100 The new minimum of weight is:5 The word of this weight is: 1000011100001000000000000000000*Idempotent(x) The word is: 1000011100001000000000000000000

При p = 43

Enter the prime number p: 43

Enter the degree of residue (3 or 4): 3

Prime element=3

Idempotent is: 1110100010010000100001100001000010010001011 The new minimum of weight is:15

The word of this weight is:

1000000000000000000000000000000000000000000*Idempotent(x) The word is: 1110100010010000100001100001000010010001011 The new minimum of weight is:12 The word of this weight is:

1010010100000000000000000000000000000000000+Idempotent(x) The word is: 0101101000100001000000101010100000010000100 The new minimum of weight is:11 The word of this weight is:

1111110110101100000000000000000000000000000+Idempotent(x) The word is: 1010100000000001001000000010100010000110001 The new minimum of weight is:7 The word of this weight is:

1101000100010110000000000000000000000000000*Idempotent(x) The word is: 1101000100010110000000000000000000000000000 The new minimum of weight is:6 The word of this weight is:

1000010100000101000010000000000000000000000+Idempotent(x) The word is:

1000010100000101000010000000000000000000000 При р = 73

Enter the prime number p: 73

Enter the degree of residue (3 or 4): 4

Prime element=5

Idempotent is: 10010111001111110101111111111111011100111011

11111111111010111111001110100

The new minimum of weight is:55 The word of this weight is: 100000000000000000000000000000000000000000000000000000000000

0000000000000+Idempotent(x)

The word is:

100101110011111101011111111111110111001110111111111111101011

1111001110100

The new minimum of weight is:26 The word of this weight is: 110000000000000000000000000000000000000000000000000000000000

0000000000000*ldempotent(x)

The word is:

110111001010000011110000000000001100101001100000000000011110

0000101001110

The new minimum of weight is:24 The word of this weight is:

100001000000000000000000000000000000000000000000000000000000

0000000000000*ldempotent(x)

The word is:

001100111000011010100101000000001000100000100010000000010100

1010110000111

The new minimum of weight is:23 The word of this weight is: 111101101001100000000000000000000000000000000000000000000000

0000000000000*ldempotent(x)

The word is:

010000000010000101100000110000010000000111000001111100100110

1001000010001

The new minimum of weight is:21 The word of this weight is: 110011001000110000000000000000000000000000000000000000000000

0000000000000*Idempotent(x)

The word is:

010100010001000000001010010100000011100110111001000110000000

0000000011000

The new minimum of weight is:20 The word of this weight is: 101011101110101000000000000000000000000000000000000000000000

0000000000000*ldempotent(x)

The word is:

010000000000010000111010010100000010000100100100100001000000

1010010111000

The new minimum of weight is:19 The word of this weight is: 110110011101000010000000000000000000000000000000000000000000

0000000000000*ldempotent(x)

The word is:

000100000010000001000000100110111000110100010000000110100110

0000000001000

The new minimum of weight is:13 The word of this weight is: 101110011111001110100000000000000000000000000000000000000000

0000000000000*ldempotent(x)

The word is:

101110011111001110100000000000000000000000000000000000000000

0000000000000

The new minimum of weight is:10 The word of this weight is: 111001010000101001110000000000000000000000000000000000000000

0000000000000*ldempotent(x)

The word is:

111001010000101001110000000000000000000000000000000000000000

The new minimum of weight is:8 The word of this weight is: 101001000010000100001001010000000000000000000000000000000000

0000000000000*ldempotent(x)

The word is:

101001000010000100001001010000000000000000000000000000000000

0000000000000

1. E F. Assmus, Jr , H.F. Mattson, Jr , Error-correcting codes- An axiomatic approach, Info, and Control, 6 (1963) 315-330

2. E F. Assmus, Jr., H.F. Mattson, Jr., On tactical configurations and error-correcting codes, J. Comb Theory, 2 (1967) 243-257

3. E F. Assmus, Jr , H F. Mattson, Jr., Research to Develop the Algebraic theory of codes, Report AFCRL-68-0478, Air Force Cambridge Res. Labs., Bedford, Mass., September, 1968

4. E.F. Assmus, Jr., H.F. Mattson, Jr., New 5-designs, J. Comb. Theory, 6 (1969) 122-151

5. E.F. Assmus, Jr., H.F. Mattson, Jr., Algebraic Theory of Codes II, Report AFCRL-69-0461, Air Force Cambridge Res. Labs., Bedford, Ma&s., 15 October, 1970

6. E F. Assmus, Jr , H.F. Mattson, Jr., Algebraic Theory of Codes II, Report AFCRL-71-0013, Air Force Cambridge Res. Labs , Bedford, Ma&s , 15 October, 1970

7. E F. Assmus, Jr., H.F. Mattson, Jr., On weights in quadratic-residue codes, Discrete Math., 3 (1972) 1-20

8. E.F. Assmus, Jr., H.F. Mattson, Jr., Contractions of self-ortogonal codes, Discrete Math., 3 (1972) 21-32

9. E F. Assmus, Jr., H.F. Mattson, Jr., Error-Correcting Codes, Report AFCRL-72-0504, Air Force Cambridge Res Labs., Bedford, Mass , 31 August, 1972

10. E.F. Assmus, Jr., H.F. Mattson, Jr., Coding and combinatorics, SIAM Review, 16 (1974)

11. E.F. Assmus, Jr., H.F. Mattson, Jr., H.E. Sachar, A new form of the square-root bound, SIAM J Appl. Math., 30 (1976) 352-354

12. E.F. Assmus, Jr., H.F. Mattson, Jr., R.J. Turyn, Cyclic codes, Report AFCRL-65-332, Air Force Cambridge Res. Labs., Bedford, Mass., 28 April, 1965

13. EF Assmus, Jr., H.F. Mattson, Jr., R.J. Turyn, Cyclic codes, Report AFCRL-66-348, Air Force Cambridge Res Labs., Bedford, Mass., 28 April, 1966

14. E F Assmus, Jr., H F. Mattson, Jr , R J. Turyn, Low weights in Quadratic Residue Codes, Inst, of Stat. Mimeo Series 484.3, Dept. of Stat., univ. of N. Carolina, Chapel Hill, N.C., 1966

15. E.F. Assmus, Jr., H F. Mattson, Jr., R J. Turyn, Research to develop the algebraic Theory of Codes, Report AFCRL-67-0365, Air Force Cambridge Res. Labs , Bedford, Mass., June, 1967

16. R C. Bose, D.K. Ray-Chaudhuri On a class of error correcting binary group codes,Info, and Control, 3 (1960) 68-79

17. R C. Bose, D.K. Ray-Chaudhuri Futher results on error correcting binary group codes, mfo. and Control, 3 (1960) 279-290

18. J Coates "Construction of rational functions on a curve", Proc Camb. Soc., 1970, 68, 105

19. RW. Hamming Error detecting and error correcting codes Bell. Syst. Tech. J., 29 (1950) 147 160

20. A. Hocquenghem Codes correcteurs d'erreurs, Chiffres (Paris), 2 (1959) 147-156

21. K. Ireland, M. Rosen A Classical Introduction to Modern Number Theory, Springer, Berlin, 1982.

22. Manin Yu.A., What is the maximum number of points on a curve over J. Fac Sci. Univ Tokyo, Sect. IA Math., vol.28, no 3, 715-720, 1981

23. M. Plotkin Binary codes with specified minimum distances IEEE Trans. Info. Theory, 6 (1960) 445 450

24. E. Prange The following technical notes issued by Air Force Cambridge Research Labs, Bedford, Mass: Cyclic Error Codes in Two Symbols, TN-57-103 (September, 1957)

25. E. Prange The following technical notes issued by Air Force Cambridge Research Labs, Bedford, Mass- The use of coset equivalence m the analysis and decoding of group codes, TN-59-164 (1959)

26. E Prange The following technical notes issued by Air Force Cambridge Research Labs, Bedford, Mass: An algorithm for factoring xn 1 over a finite field, TN-59-175 (October, 1959)

27. R.C. Singleton Maximum distance q-nary codes. IEEE Trans. Info. Theory. 10 (1964) 116-118

28. A N. Skorobogatov, S.G. Vladut On the Decoding of Algebraic-Goemetric Codes, IEEE Transactions on Information Theory, vol 36 No. 5, September 1990

29. H Stichtenoth Algebraic Function Fields and Codes, Springer Verlag, Berlin

30. M A. Tsfasman, S.G. Vladut, T. Zink, Modular curves, Shimura curves, and Goppa codes, better than Varshamov-Gilbert bound, Math. Nachr., vol. 109, pp. 21-28, 1982

31. P.P. Варшамов Оценка числа сигналов в кодах с коррекцией ошибок, Доклады Академии наук СССР, 1957, Т. 117 №5, С.739-741

32. С.Г. Влэдуц, Д.Ю. Ногин, М.А. Цфасман "Алгеброгеметриче-ские коды. Основные понятия 11, МЦНМО 2003.

33. Влэдуц С.Г., Манин Ю.И. Линейные коды и модулярные кривые, Современные проблемы математики, Итоги науки и техники, 1991, Т. 25, №1, С.24-36

34. В.Д. Гоппа, Коды на алгебраических кривых, ДАН СССР, Т. 259, №6, с. 1289-1290, 1981

35. В.Д Гоппа, Алгебраико-геометрические коды, Изв. АН СССР, Сер. Мат., Т46, №4, с. 762-781, 1982

36. В.Д. Гоппа, Коды и информация, УМН, т. 39, №1, с. 77-120, 1984

37. Ф. Мак-Вильямс, Н. Слоэн Теория кодов, исправляющих ошибки, "Связь", Москва, 1979.

38. И.Р. Шафаревич Основы алгебраической геометрии М Наука, 1972

39. К. Шевалле Введение в теорию алгебраических функций от одной переменной

40. Семеновых Д Н. Обобщение квадратично-вычетных кодов на случаи вычетов третьей и четвертой степени Дискретная математика, т. 17, 2005, №4, с. 143-149

41. Семеновых Д.Н. Построение базиса пространства Римана-Роха на гиперэллиптических кривых. Рукопись деп. в ВИНИТИ 13.12.2005 № 1653-В2005