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

• Семеновых, Денис Николаевич
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Семеновых, Денис Николаевич

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

Введение

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Семеновых, Денис Николаевич, 2006 год

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