Читать онлайн «Линейные коды и модулярные кривые»

Винит ЮМ УДК 519. 725+512. 624 ЛИНЕЙНЫЕ КОДЫ И МОДУЛЯРНЫЕ КРИВЫЕ С. Г. Влядуц, Ю. И. Мшит ВВЕДЕНИЕ В настоящей работе систематически изложены результаты недавних исследований на стыке теории кодов, теории вычис- вычислимости и алгебраической геометрии иад конечными полями. Эти исследования были инициированы замечательной идеей B. Д. Гоппы [7, 8], который предложил рассматривать линей- линейные системы иа алгебраических кривых как коды и обнаружил, что среди иих есть очень хорошие коды, которые в § 1 ниже названы изолированными. ,Затем М. А. Цфасман [28, 16] пока- показал что и асимптотические параметры кодов Гоппы улучшают долго остававшуюся непревзойденной границу Варша,мова— Гилберта, если существуют кривые, число точек на которых Достаточно велико, по -равнению с родом. ,В действительности, Ихара [24, 23] ранее обнаружил, что модулярные кривые, классические и Шимуры, именно таковы; независимо это поня- поняли С. Г. Влэдуц и Цинк [28]. ,Оценка максимального числа то- точек над полями F, была затем получена В. Г. Дринфельдом и C. Г. Влэдуцем [5] (теорема 3. 8); она точна для q^p2*. ;Алго- q^p2*. ;Алгоритмы, строящие коды вблизи границы Варшамова—Гилберта, являются переборными; поэтому встает естественная задача: генерировать хорошие коды с помощью достаточно быстро ра- работающих алгоритмов. /Оказывается, что коды Гоппы, отвеча- отвечающие модулярным кривым, строятся за полиномиальное время, j \t Для классических модулярных кривых это продемонстрировано в работе С. Г. Влэдуца [4]. ?В этом обзоре изучены модуляр- ;-. ные кривые Дрнифельда [10], в вычислительном отношении f' более удобные. Коды, получающиеся из модулярных кривых, имеют хорошие асимптотические параметры только при доста- /точно большом q. В частности, таким способом нельзя полу- полупить бинарных (д=2) кодов. Г. Л. Кацмаиу принадлежит идея '^использовать каскадные коды с фиксированным внутренним У, бинарным изолированным кодом и виешинми кодами, получаю- получающимися из модулярных кривых. Это приводит к наилучшим известным бинарным кодам с полиномиальной сложностью по- построения (см. пп. 1. 2. 13, 1. 3. 7 и работу [6]). 14-2700 209 Часть упомянутых работ была выполнена в рамках семина- семинаров по диофантовой геометрии н прикладной алгебре, которые- вел Ю. И. Манин на мехмате МГУ в 1981 и 1982 годах. Гла- Глава I этой статьи написана Ю. И. Маииным с использование» записок этих семинаров и курса лекций, В ней изложены ос- основные задачи асимптотической теории кодов и конструкция: Гоппы. Глава II, написанная С. Г. Влэдуцем, содержит про- проведенный им детальный алгоритмический анализ модулярно- кодовых конструкций. Авторы приносят свою искреннюю благодарность В. Г. Дринфельду, беседы с которым об эллиптических моду- модулях были весьма полезны, С. И. Гельфанду н М. А. Цфасману за внимание к работе и ценные замечания и Д. Ю. Григорьеву,, сообщившему алгоритм разложения многочленов на множите- множители, использованный в п. 2. 6. 5. Глава 1 АСИМПТОТИЧЕСКИЕ ЗАДАЧИ ТЕОРИИ КОДОВ § 1. Коды и их асимптотические свойства 1.