Модулярные кривые и коды с полуноминальной сложностью построения

• Автор: Влэдуц, Сергей Георгиевич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 1983
• Место защиты: Москва
• Количество страниц: 126 c. : ил

ГЛАВА I. Рациональные точки на кривых и корректирующие

коды

§1. Рациональные точки на кривых над конечными

полями

§2. Корректирующие коды и их асимптотические

границы

§3."Модулярный коды и их параметры

§4. Применение к бинарным кодам

ГЛАВА 2. "Модулярные" коды для классических модулярных

кривых

§1. Основная теорема

§2. Реализация "модулярных" кодов
§3. Формулы
§4. Вычислительный процесс
§5. Стандартные процедуры
ГЛАВА 3. "Модулярные" коды: эллиптические модули
В.Г.Дринфельда
§1. Основная теорема
§2. Многообразия модулей эллиптических модулей
§3. Реализация "модулярных" кодов
§4. Формулы
§5. Вычислительный процесс
ЛИТЕРАТУРА

Общая характеристика работы. Актуальность темы. Работа посвящена изучению связи между алгебраическими кривыми над конечными полями и корректирующими кодами. Изучаются рациональные точки на алгебраических кривых над конечными полями и корректирующие коды, возникающие на таких кривых.
Линейным с» -ичным кодом С называется -мерное под-СГ’ Iх
пространство в , минимальное число ненулевых координат в ненулевом векторе из С обозначается <£ = (£. (С) . Одной из основных задач теории кодирования является изучение соотношений между величинами К = и <Г = ^(п при длине кода
Ь., стремящейся к бесконечности. Здесь ставится задача существования сколь угодно длинных кодов с заданными параметрами ( , <Г ), а также задача эффективного построения такой последовательности кодов, коль скоро известно, что она существует. Частичное решение этих задач дают нижние границы Варшамова-Гильберта (для произвольных линейных кодов) и Блоха-Зяблова (для эффективно конструируемых последовательностей кодов).
Цель работы. Целью работы является построение семейств кривых с асимптотически максимальным числом рациональных точек, доказательство того, что получаемая оценка неулучшаема, и получение на основе детального алгоритмического анализа конструкции кодов по кривым утверждения о возможности эффективного построения таких кодов. Оцениваются их асимптотические параметры, оказывающими весьма хорошими.
Научная новизна. Все основные результаты работы являются новыми и могут быть использованы в алгебраической геометрии,

теории кодирования и теории сложности вычислений.
Методика исследования. Применяется конструкция В.Д.Гоппы кодов по кривым над конечным полем, вычисление числа рациональных точек на модулярных кривых. Для алгоритмического анализа конструкции кодов применяется детальный анализ плоских моделей модулярных кривых.
Апробация работы. Результаты диссертации докладывались на ХУ1 Всесоюзной алгебраической конференции (Ленинград, 1981 г.), на Школе-семинаре по алгебраической геометрии (Ярославль,
1982 г.), на семинаре по теории кодирования в Институте проблем передачи информации АН СССР (1983 г.), на семинаре Отдела прикладной математики Центрального экономико-математического института АН СССР (1983 г.), на УШ Всесоюзном симпозиуме по проблеме избыточности в информационных системах (Ленинград,
1983 г.).
Объем и структура диссертации. Диссертация содержит 125 страниц и состоит из введения и трех глав, разбитых на 14 параграфов; библиография - 39 названий.
Публикации. Все основные результаты диссертации опубликованы в работах [4 - 8] , [38]
Содержание диссертации.
В главе I, Рациональные точки на кривых и корректирующие коды, изучается связь между рациональными точками на кривых над конечным полем и асимптотически хорошими корректирующими кодами.
В §1 изучается вопрос о возможной асимптотике отношения числа -точек на гладкой абсолютно неприводимой кривой

^ (С ^ (Съ)= ра. (с) - ^ 2 (Ч-р -1) С3),
где суммирование ведется по всем точкам кривой С , включая бесконечно близкие (.сумма имеет СМЫСЛ, Т.К. Хр (^р -1) фо только для конечного числа особых точек Р ).
Мы будем обозначать через £{, С множество особых точек кривой С . Пусть Р 6 $С . Назовем бесконечно близкими точками первого порядка бесконечно близкие точки точки Р , лежащие на поверхности , полученной из Р раздутием точки Р . Бесконечно близкие точки Лг -того порядка (^^1) определяются как бесконечно близкие точки, лежащие на поверхности, получаемой раздутием одной из особых бесконечно близких точек (У- - 0 -ого порядка.
Дерево Гр бесконечно близких точек точки Р определяется следующим образом: его корень 'иг=• игр соответствует точке Р , потомки первого порядка находятся в биекции с бесконечно близкими точками первого порядка, ..., потомки Ъ -того порядка - с бесконечно близкими точками % -того порядка. Висячие вершины дерева Г^> находятся в биекции с точками на нормализации СУ кривой С , лежащими над Р . Множество вершин (.висячих вершин) дерева Г^> будет обозначаться через /р (соответственно /р ), его мощность - через Кр (соответственно У'р ). Через Г мы обозначаем граф и Гр и называем
Р £ С
его графом разрешения особенностей С . «
Мы будем рассматривать далее интересующий нас случай
к= Ц, г= Р С=х , су=А
25. Л е м м а. Имеет место неравенство