close

Вход

Забыли?

вход по аккаунту

?

bd000100074

код для вставкиСкачать
м о с к о в с к и й ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
И М Е Н И М.В.ЛОМОНОСОВА
На правах рукописи
Глухов Михаил Михайлович
ПОСТРОЕНИЕ ЛИНЕЙНЫХ КОДОВ
В ПОЛЯХ АЛГЕБРАИЧЕСКИХ
ФУНКЦИЙ
01.01.09 - дискретная математика и математическая
кибернетика
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
кандидата физико-математических наук
МОСКВА-2005
Работа выполнена на кафедре дискретной математики
Института криптографии связи и информатики Академии Ф С Б
России.
Научный руководитель:
доктор физико-математических наук,
профессор Степанов Сергей Александрович.
Официальные оппоненты:
доктор физико-математических наук,
профессор Гашков Сергей Борисович;
кандидат физико-математических наук,
доцент Применко Эдуард Андреевич.
Ведущая организация:
Институт информационных наук и технологий
безопасности Российского государственного
гуманитарного университета.
Защита диссертации состоится Ч .г.?.
года a l l часов
на заседании диссертационного совета Д501.001.44 Московского
государственного згниверситета им. М.В.Ломоносова по адресу:
119992, г.Москва, ГСП-2, Ленинские горы, МГУ, 2-ой учебный
корпус, факультет ВМиК, аудитория 685.
С диссертацией можно ознакомиться в библиотеке факультета
ВМиКМГУ.
Автореферат разослан т.............!!;... года.
Ученый секретарь
диссертационного совета,
профессор
<7**Т''Т^
Трифонов Н.П.
ми
^9^Ю
1тъ5ч
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность т е м ы . Теория помехоустойчивого кодирования,
или теория корректирующих кодов возникла в середине прошлого
века в связи с практической потребностью повышения достоверно­
сти приема информации, передавс1емой по реальным каналам свя­
зи. Первыми pai6oT£iMH по теории помехоустойчивого кодирования
явились классические работы К. Шеннона "Математическая теория
связи", 1948 г. и "Связь при наличии шума", 1949 г.
Всюду ниже корректирующие коды и теорию помехоустойчивого
кодирования мы будем называть просто кодами и теорией кодиро­
вания. При этом под кодом всегда будем понимать так называемый
блочный код, состоящий из векторов фиксированной длины в задан­
ном конечном алфавите. Указанные векторы называются кодовыми
словами, а их длина - длиной кода. Способность кода обнаруживать
и исправлять ошибки типа замены букв дрзггими буквами алфавита в
передаваемой информации называют корректирующими свойствами
кода. Они во многом определяются кодовым расстоянием рассмат­
риваемого кода, т.е. минимальным расстоянием по Хэммингу между
его различными кодовыми словами.
Одной из главных задач теории кодирования, возникающей непо­
средственно из теории и хфактики связи, является задача построения
кодов с заданньпли корректирующими свойствами и допускающими
сравнительно простую регшизацию процесса кодировгшия и декоди­
рования. В связи с последними требованиями особую роль в теории
кодирования играют так называемые линейные коды. В последние
десятилетия для построения линейных кодов над конечными полями
особенно интенсивно используются методы алгебраической геомет­
рии в теории полей алгебраических функций. Коды, построенные
таким образом, стали называть алгебро-геометрическими кодами.
Первыми работами в этом направлении являются работы
В.Д.Гоппы (см. [3]), в которых он предложил строить коды на точках
алгебраических кривых, определенных над конечным полем. Позд­
нее это направление развивалось многими авторами. В 1984 г. по­
явился обзор [1] С.Г.Влэдуца и Ю.И.Манина работ по кодам на мо­
дулярных кривых. В настоящее время имеется ряд монографий, по­
священных методам построения и исследованию свойств алгеброгеометрических кодов (см. [2], [8], [9]).
В.Д.Гоппа показал, что его конструкция позволяет строить асимп­
тотически длинные коды, информационная мера которых достигает
известной граншцл ВаршамовагГилберта. Затем М.А.Цфасман [7], а
также С.Г.Влэдуц и Т.Цинк заметили, что среди таких кодов суще­
ствуют коды с информационной мерой, превосходящей указанную
границу, которая до этого долгое время оставалась не ул)гчшаемой
(см. [10]). При этом для построения кодов использовались алгебра­
ические кривые с большим числом точек над заданным конечным
полем К, т.е. с большим числом iC-рациональных точек.
РОС НАЦНОНАЛЬНЛИ
БИЫМОТБКА
;
i"iya?l:
Для числа N всех А"-рациональных точек на алгебраической кри­
вой имеется известная оценка Вейля \N—{q+l)\<2g^, где д - род
кривой, K=GF{q). В 1991 году С.А.Степановым (см. [41) были указзг
ны кривые, на которых эта оценка достигается. Идея С.А.Степанова
использована автором для построения широкого класса кривых с
большим, хотя и не достигающим оценки Вейля, числом К- рацио­
нальных точек. Этот класс кривых над полем K=GF{q^) характери­
стики р содержит суперэллиптические кривые, заданые уравнением
,,,
у' = т,
(*)
с многочленом /(х) вида:
I . [t^x + ( M X ) ' ' " - " ' ' ) " {^^x + Ы х ) ' ' " ^ " " ) ' ,
где а, 6, п, я 6 N, 2 / п , п > 1, а -t- 6 = S, (а, я) = 1, ^ 6 А"*, s\q - 1.
I I . (мх -f- {^^xr"-'У
{fxx + ( д х ) ' " ' ' ^ ' ) ' ,
где а,Ь,п,8 е N, п-четно, п > 2, a-f- 6 = s, (а,а) = 1, /^ € К*, 8\q — \.
III.
\цх-\- ifixy
\
, где S,п е N, S,п - четны, /i € К*, s\q — 1,
и кривые Артина-Шрейера, заданные уравнением
с многочленом /(х) вида:
у"'-У
= fix),
IV.(^x)«'"^''''+^-(/ix)''"-'''+S
{**)
где п, а G N, п - нечетно, п> 1, (л е К*, р' - l\q — 1.
V . (/хх)'"''^'+1-(ма:)''"'-'+1,
где п, S € N, п - четно, п> 2, ц е К*, р* - l\q - 1.
Такие кривые мы будем называть, соответственно, кривыми типа
I-V. Некоторые из этих кривых уже использовались для построения
хороших кодов с помощью расслоенных произведений (см. [6]).
Представляется актуальной задача подробного изучения геомет­
рических кодов на указанных кривых, или же в полях алгебраиче­
ских функций определяемых теми же уравнениями. Эти поля мы
также будем называть полями типа I-V.
Ц е л ь диссертационной работы. Подробно исследовать алгеб­
раические кривые и поля алгебраических функций типов I-V, алгеброгеометрические коды на этих кривых и в указгшных полях алгебраг
ическнх функций над полем К = GF{q").
Основные методы исследования. В диссертации используют­
ся методы алгебры, теории чисел и алгебраической геометрии.
Н а у ч н а я новизна результатов. Все основные результаты дис­
сертации являются новыми. Получены следующие результаты.
1. Описаны неприводимые над полями GF{q), GF{q") делители
многочленов I-V, в нетривиальных случаях найдены формулы числа
таких делителей заданной степени.
2.0писавы iir-рациональные точки кривых типов I-V.
3. Д л я простых дивизоров полей алгебраических фушсций типов
I-V найдены их степени, относительные степени, индексы ветвления.
4. Доказаны теоре1|1ы о сужении возможности выбора пар диви­
зоров без нарушения эквивалентности определяемых ими кодов.
5. Д л я кодов, определяемых наиболее естественными паргши ди­
визоров на рассматриваемых кривых и полях алгебраических функ­
ций, найдены основные параметры и порождающие матрицы.
Теоретическая и практическая ценность. Результаты дис­
сертации могут представлять как теоретический, так и практический
интерес. Они расширяют имеющийся запас линейных кодов и поз­
воляют строить новые линейные коды большой длины с достаточно
хорошими корректирующими свойствами.
Апробация результатов. Результаты диссертации докладывав
лись на I I Международной конференции "Теория чисел и ее прило­
жения" (Тула, 1997 г.), на V I I Международном семинаре "Дискрет­
ная математика и ее приложения"(Москва, 2001 г.), на V Междунаг
родной конференции "Алгебра и теория чисел: современные пробле­
мы и приложения"(Тула, 2003 г.), на конференции Академии Ф С Б
и Института криптографии, связи и информатики, посвященой па­
мяти ак. А.Н. Колмогорова (Москва, 2003 г.).
П у б л и к а ц и и . Основные результаты диссертации опубликованы
в семи работах, список которых приведен в конце автореферата.
С т р у к т у р а и объем диссертации. Диссертация состоит из
введения, четырех глав, разбитых на параграфы, и заключения. Об­
щий объем диссертации составляет 115 страниц. Список литературы
включает 49 наименований.
КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ
Введение.
Во введении даны пояснения по актуальности темы, сформули­
рованы задачи и основные результаты диссертации.
Глава 1 . Вспомогательный материал
Эта глава носит вспомогательный характер и содержит три пэг
раграфа. В них вводятся необходимые для дальнейшего изложения
понятия, обозначения и краткие сведения соответственно из теории
полей алгебргшческих функций, теории алгебраических кривых и
теории линейных кодов над конечными полями. Приведем сведения
из | l , необходимые для формулировки основных результатов.
Под полем алгебраических функций F = К{х,у) будем пони­
мать простое алгебраическое расширение поля рациональных дробей
К(х) над фиксированным полем К. Кольцом дискретного нормиро­
вания поля F называется любое подкольцо О поля F, удовлетворя­
ющее условиям: KCOCF
, КфОф¥ , V o e F {а^О или а"^ € О).
Кольцо О есть максимальное подкольцо в F, и является локаль­
ным кольцом главных идеалов. Его максимальный идеал Р состоит
из всех его необратимых элементов. Факторкольцо OjP называется
полем вычетов по идеалу Р и обозначается Fp. Естественный эпи­
морфизм ф-.О-^О/Р индзгцирует изоморфное вложение поля К в Fp.
В связи с этим К отождествляется с ф{К) и считается, что KcFp.
Степень расширения [Fp:K] называется степенью идеала Р и обо­
значается degP. Для элемента оеО образ ф(а)=:а+Р обозначается
а{Р) и называется значением а на Р. Если d e g P = l , то Fp отож­
дествляется с А", и потому а{Р)=а+Р считается элементом из К.
По кольцу дискретного нормирования О и его максимальному
идеалу Р = Ю однозначно определяется отображение v : F -^ ZUoo:
v{a) = к, если а е F* и а = <*•«, гдеfc6 Z и и £ О*, u(0) = оо (и(а) не
зависит от выбора элементов t ли). Следуя [5], мы будем называть
указанное отображение v дискретным нормированием, или просто
- нормированием, поля F по максимальному идеалу Р кольца О.
Кольцо О и его максимгшьный идеал Р однозначно определяются по
нормированию v. А именно: 0={a£F : v(a)>0}, P={a£F : v{a)>0}.
Для описания колец нормирования поля F удобно рассмотреть
сначала простейший случай, когда степень расширения [F:if(a;)]=l.
В этом случае каждый элемент а £ F однозначно представляет­
ся в виде несократимой дроби а = h{x)/g{x), где h{x),g{x) € К[х],
{h{x),g{x)) = 1, и условиям 1), 2) определения кольца нормирования
удовлетворяет множество
Ор{х) = Щх)/д{х) : Цх),д{х) € К[х],{р{х),д{х))
= 1}
при любом фиксированном унитарном неприводимом над К много­
члене р{х) е К[х]. При этом максимальный идеал Рр{х) = р{х)Ор^х)Кроме колец нормирования вида Ор(^х) в К{х) есть еще лишь од­
но кольцо нормирования. Оно обозначается через Ооо и состоит из
несократимых дробей вида h{x)/g{x) в которых degh{x) < degg{x).
Его максимальный идеал PQO порождается элементом 1/х и состоит
из дробей h{x)/g{x), где degh{x) < degg(x).
Функция нормирования, соответствующая Ор(х), определяется для
о = iff} е Р ' : t;p(^)(a) = ехрр(^) h{x) - ехрр(^) д{х) , где
expp(jj) а{х) = max{n G N : р(х)"|о(а;)}, а соответствующая кольцу
Ооо: Voo{a) = degg{a;) - degh{x).
Максимальньшга идеалами степени 1 в поле К(х) являются все
идеалы вида Рр(х), где degp(a;) = 1, и Роо- Значение а ( Р ) дроби
а = ? М е Ор, где а(а;) = anX"+...+aix+ao,b{x) = bmx'"+...+bix+bo,
а„фОу bm^Q, вычисляется следующим образом: если Р = Р^-с, то
а{Р) = Щ^; если Р=Роо, то a ( F ) = f ^ при п=т и а ( Р ) = 0 при п<т.
В случае [F:K{x)]>l любое кольцо нормирования О' поля F яв­
ляется расширением единственного кольца нормирования О поля
К{х), причем 0=0' П К{х). Аналогичное соотношение P=Q П К{х)
выполняется и для мгиссимальных идеалов Р, Q колец О, О'. При
этом имеют место естественные вложения KCK(X)CFQ.
Тот факт,
что Q есть расширение идеала Р обозначается {Q\P)- Степень расширеЕшя [FQ:K{X)P]
называется относительной степенью идеала Q и
обозначается fiQ\P). Нормирование VQ поля F обладает следующим
свойством: 'ia£K{x) ид(о)=еир(а), где e=e(QlP) - независящее от
а нат)гральное число, называемое индексом ветвления идеала Q.
Для каждого кольца нормирования О поля К(х) существует ко­
нечное непустое множество расширений Oi,..., От, являющихся коль­
цами нормирования поля F. При этом для идеалов Р кольца О v Qt
- кольца Oi, г = 1, ...,m, выполняется следующее фз^даментальное
тождество Y,Zi <Qi\P)fiQi\P)
= [F ■ К{х)].
Всюду далее, следуя [9], максимальные идеалы колец нормиро­
вания поля алгебраических функций будем называть хфостыми ди­
визорами этого поля.
Простые дивизоры полей К{х) и F далее будут обозначаться со­
ответственно буквами Р и. Q с индексгили или без. Множ:ество всех
простых дивизоров полей К{х) и F обозначим через Рк(х) и Fp.
Любая целочисленная линейная комбинация конечного множе­
ства элементов из Рр- называется дивизором поля F. Любой дивизор
D можно записать в виде
^ = Е«еР,"««'
(^-^^
где n g e Z и лишь конечное число коэффициентов пц отлично от 0.
Множество S{D)={Q | UQ^O} называют носителем дивизора D. На
множестве Вр всех дивизоров поля F определяется покомпонентное
сложение и, таким образом, Вр превращается в свободную абелеву
грзгппу со свободной системой образующих Pp. В ней выделяется
подполугруппа Ш'р дивизоров вида (1.3) с неотрицательными коэфициевтами TIQ. Такие дивизоры D называют неотрицательными, или
эффективными, и пишут D > 0. Неотрицательный дивизор D, в ко­
тором сзтцествует слагаемое с ненулевым коэффициентом, называют
положительным и пишут D > 0.
На дивизоры распространяются нормирования поля F. Для ди­
визора D вида (1.3) VQ{D) = nQ. Число S o e P p ^Pi^)^^SQ называ­
ется степенью дивизора D и обозначается deg D. Заметим, что при
D = Q степень дивизора D равна степени идеала Q.
С каждым элементом а & F* ассоциируется так называемый
главный дивизор
(«) = EgeP,'''2(a)Q.
(1.4)
При изучении алгебро-геометрических кодов в поле F важную роль
играют множества
L{D) = {х е F : (х) + D >0}и{0}
(для D е © F ) Каждое из них есть линейное пространство над полем К, и если
1>2-^1>0, то L(I)i)cL(£>2) и dim(L(D2)/L(I>i))<degD2-deg£)i.
Размерность пространства L ( U ) называется размерностью дивизо­
ра i? и обозначается также dmi£>. Для любого дивизора D поля F
выполняется неравенство dimD < 1 + degD, а величина
д = max^Jg][J {deg D — dim D + l}^называется родом поля F.
Таким образом, для любого дивизора D: dim£)=deg£)+l—д+с,
где с>0. Известная теорема Римгша-Роха (см., например, [5]) выра­
жает константу с через некоторый канонический дивизор W, зави­
сящий от D: с = dim{W — D). Нами используется следствие из этой
теоремы, по которому dimD = degP + 1 — д, если degZ) >2д — 1.
В §2 вводятся понятия аффинной и проективной алгебраической
кривой над алгебраически замкнутым полем, бирационального изо­
морфизма кривых, регулярной функции на кривой, а также функ­
ции, регулярной в точке кривой, локального кольца точки и его мак­
симального идеала, простой и особой точки кривой, гладкой кривой,
дивизора и группы дивизоров на кривой и др. Устгшавливгиотся свя­
зи между аффинными и проективными кривыми, между основными
кольцами и максимальными идеалами соответствзгющих полей ал­
гебраических функций. Приводится критерий гладкости кривой.
В §3 определяются наиболее известные классы линейньпс кодов
и, в частности, алгебро-геометрические коды Гоппы.
Каждый такой код на гладкой проективной кривой V над GF{q)
задается двумя дивизорами D, G, где D=Pi+P2-\
1-Р„ - сумма
некоторых точек кривой V,G - любой дивизор, носитель которого не
содержит P i , . . . , Р „ . Соответствующий код C(D,G)
состоит из всех
векторов вида (/(Pi),/(P2),. ■ ■ ,/(Pn))i где / пробегает множество
всех таких рациональных функций на V, для которых ( / ) + ( ? > 0.
Аналогичным образом определяется код C{D,G) в любом поле
алгебраических функций F. При этом в качестве дивизора D берется
сумма некоторых простых дивизоров первой степени, а в качестве G
- любой дивизор с условием S{D)r\S(G) = 0. Значение элемента / на
простом дивизоре Р G D вычисляется точно так же как и для идеала
1-ой степени поля К{х), расширением которого является идеал Р.
Такой код C(D, G) изоморфен факторпространству
L{G)/L{G-D)
и при K=GF{q)
является линейным [п,к,с[\д-кодом с параметрэг
ми: \n-{q+l)\<2gy/q , к= dimL{G)-dimL{G-D),
d > degG-2g-\-2,
d>n— deg G, где g - род кривой или поля алгебраических функций.
Если 2д + 1 < degD < п, то отображение CTD ■ L{G) -> U{D,G),
<^DU) = ( / ( A ) . / ( P 2 ) , - , / ( P n ) ) . является изоморфизмом линейных
8
пространств, и тогда dim L{G - D) = 0, к = dim G = deg G + 1 - g,
n + l-g<k
+ d<n + l.
Глава I I . М н о г о ч л е н ы Степанова ж их обобщения.
Для описания неприводимых над полем GF{q) делителей указан­
ных выше многочленов достаточно описать все неприводимые дели­
тели многочлена
,
а±и.
ди{х) = х''^+х,
(П.1)
где U = ±1 при нечетном п и и = ±2 или и = О при четном п.
При четном q его неприводимыми над GF{q) делителями явля­
ются в точности все неприводимые над GF{q) многочлены, степени
которых делят число {п + и)/2.
При решении поставленного вопроса в случае нечетного q исполь­
зованы общепринятые обозначения, включая следующие:
— для а е GF{q)*, ord а - мультипликативный порядок элемента а,
— для keZ, ехр2(А;) = т а х { / б No : 2'|А:},
— Ф(тп) - число неприводимых унитарных многочленов степени m
из кольца GF{q)[x], всех при m > 1 и всех, кроме х, при тп = 1.
Теорема I I . 1 А) Пусть q - нечетно. Неприводимый над GF{q)
многочлен h{x) степени тп > 1 делит ди{х) тогда и только тогда,
когда: 1) т\п+и, т / ^^^^ ; 2) ord(a)|2(g'"/^-l), где а - корень h{x).
Б) При выполнении условий 1),2) число Хт неприводимых над GF{q)
унитарных делителей степени т многочлена ди{х):
^- = Е-=1 ^* ( F ) ' '^' * = ^2^""^-
^"•^^
Решен вопрос о неприводимых над GF{q'^) делителях многочлена
9и{х).
Теорема I I . 2 а) Если п - нечетно, т.е. и = ± 1 , то любой
неприводимый над полем GF{q) делитель многочлена дх,(х) явля­
ется неприводимым «о^ полем GF{q").
б) Если п - четно и и= ± 2, то любой неприводимый над GF(q)
делитель степени т > 1 многочлена ди{х) разлагается над GF{q^)
в произведение двух неприводимых многочленов степени т/2.
в) Если п — четно и и = О, то любой неприводимый над полем
GF{q) делитель степени т > I многочлена ди{х) разлагается над
полем GF{q") в прог13ведение линейных многочленов.
Следствие I I . 1 Если 2 / п , то множество неприводимых над
GF{q^^) делителей многочлена ди(х) совпадает с мноокеством его
неприводимых делителей над GF{q). Если 2\п и и= ± 2, то мно­
гочлен ди{х) имеет неприводимые над G F ( g " ) делители степени
9
m тогда и т,олько тогда, когда он имеет неприводг1Мые над GF{q)
делители степени 2т. При этом число неприводимых над полем
GF{q'*) делителей степени т>1 многочлена 5и(з;) вычисляется по
формуле (П.2), если 2 / п , и равно 2 5Z,=i ^ ^ { f r ) , если 2|п.
Следствие I I . 2 Пусть q - нечетно, и = 1 или 2. Тогда:
а) если п = l(mod 2) или п = 2(mod 4), то (pu(x),g_u(a;)) = х,
б) если п ~ O(mod 4), то (р„(а;),р_„(а;)) = i ' + х.
Для вычисления числа точек на рассматриваемых ниже алгеб­
раических кривых нам необходимы сведения о корнях многочленов
I, I I , I I I в полях GF{q), GF{q^) и результаты о суммах характеров
конечных полей от этих многочленов.
Обозначим через Л ь А2, Аз - множества всех корней многочле­
нов I, I I , I I I в поле GF{q), и Bi, В2, В3 - множества всех корней
многочленов I, I I , I I I в поле GF(q^).
Теорема I I . 3 а) Если q - четно, то Ai = А2 = Аз = GF{q),
( GF(q]
, n = 0( mod 4)
,,
б) Если q - нечетно, mo ^ 1 = ^ 2 = ^ 3 = {0},
1
= roi
в =i
^ S> 2
у GF{q)a, a e GF{q%
Вз = GF{q"^^)a,
{ 0 } , n = 2(mod4)
a"'^ = - 1 , n = 0( mod 4) '
где a 6 GF{q'^),a^^'^'^-'^ = - 1 .
в) Все корни многочленов I, П имеют кратность s, а корни много­
члена Ш - в/2.
Пусть Хп,»{х) = Xs{'"''^^^n{x)) - мультипликативный характер
индекса s поля GF{q^), индуцированный характером Хв поля GF{q).
Д л я / е GF(q'*)[x] обозначим: 5„,,(/) = ExeOFC,-) XnAfi^))Известно (см. [5], стр.41), что число решений уравнения (*) над
GF{q") выражается формулой Nq^^ = Ylxn . ^^Ai)Теорема I I . 4 Пусть f{x) € GF(g")[a;], n > 1, а, Ь, s € N, s\q - I,
а + Ь = 8. Тогда:
а) если 2 / n , f{x) - вида I, тю 5„,,(/ = {
„
^, ;
I
Ч
Q ! если 2\q
q" — q ,если q - любое, 4|n
б) если 2\n, j{x) - вида П, mx> 5„,»(/) = <
g" - 1 ,если 2 ](q, 4 | n ;
q"-q^
,если 2|g, 4 / п
в) если 2\n, 2\s, f[x) - многочлен вида HI, mo Sn,aU) = (g"^^-!)?"^^.
10
Теорема I I . 5 Пусть f{x) - многочлен вида 1-Ш над полем GF{q^),
п>1, а + Ь=8, s\q—l, Mo — множество корней многочлена f{x)
в поле GF^q'^) и М i = GF(g")\Mo. Тогда:
а) для a&GF{q^) уравнение (*) гилеет над GF{q") ровно s решений
вида {а,Р), если a£Mi, и единственное решение (а,0), если а б М о ;
б) если Nqr, - число всех решений над GF(q")
уравнения {*), то
sq"' — (s - \)q ,если f{x) eu(?o I u2\q , или - II и 2 J[q, 4|n
sq" — (a — 1) ,если f{x) вида I u2j(q , или - II и 2 J[ q, 4 / n
^9" - '\
„„" _ ^„_n^2
sq" — (s — l)q^ ,если f(x) вида II при 2\q и 4 / n "
sq" - (s - l)g"''^ ,если f{x) вида III
С использованием сз^мм адгщтивных характеров, доказана
Теорема I I . 7 Пусть GF{q") - поле характеристики р, п>3,
р*—1|5—1. Тогда число решений над GF{q'^) уравнения {**) равно p'q'*.
Глава I I I . О свойствах алгебраических к р и в ы х и полей
алгебраических ф у н к ц и й .
Алгебраические кривые типа I и П имеют особые точки. В связи
с этим перейдем к бирационально изоморфным им гладким кривым.
Теорема I I I . 1 Аффинная кривая V типа I или II бирационально
изоморфна гладкой кривой Vi, заданной уравнением
V' = hiw),
(III.2)
где:
1) fi{w) = (Ц-и;''"''"'-1)»(Ц-г/;9*"'"""-1)», если f{x) вида I, 2)(q;
2) fiH
= ( i ^ T ^ S ^ ) ^ ^ ^ ^ ^ ^ ^ ^ ) * . ^^" / И в"<?а / и 2\q;
3) /i(№)=(!+«;'"'' '-l)'^(l+u^9"''■'^-l)^ если f{x) вида II, 2J(q. 4/n/
4) hH
.n/2-l_,
=('+W-.
„»/2+l_.
)''('0->
)'' ^'^'^ ^(^) «"^'^ "' 2|9' ^Xn;
5) fi(wM'+f^^,.,
)4'+rl.,-^
)\ если f(x) вида II, 4|n.
Теорема I I I . 2 Алгебраическая кривая, заданная уравнением
(III.2), имеет ровно N = sq'* GF{q'*)-рациональных точек в каждом
из случаев 1)-5).
Теорема Ш . З Алгебраическая кривая V, заданная уравнением
(III.2), имеет род д, который в каждом из случаев 1)-5) выража­
ется соответственно формулой:
1)9 = («("+1)/2 + g('*-i)/2 - 4)(s - 1)/2;
2) 9 = (g<'»+i)/2 + g("-i)/2 _ 2{q + l))(s - l ) / 2 ;
11
3)д=. (g"/2+i + g»/2-i _ 4)(s _ l ) / 2 ;
4)9^ (g"/2+i + ^"/2-1 - 2(?2 + i))(s - l ) / 2 ;
5; 5 = (g"/2+i + qn/2-1 _ 2(g + l))(s - l)/2.
Кривая типа I I I разлагается в объединение f кривых, каждая из
которых бирационально изоморфна кривой, заданной уравнением
у=' = а; + х«"''.
(Ш.5)
Теорема I I I . 4 Пусть q - нечетно. Тогда кривая Vi, заданная
уравнением (III. 5), является гладкой неприводимой кривой рода
д = (д"/^ — 1)/2 с N = 2q" - 9"/^ СР{д")-рациональньили точками.
Д л я кривой V типа I V или V доказана
Теорема I I I . 5 Алгебраическая кривая V типа IV или V над по­
лем GF{q^^) является неприводимой гладкой кривой рода
д = [q^^ — l)qr("+»)/2 с JV,n = p'g" ОР{д")-рациональными точками.
Далее рассматриваются поля алгебраических функций над полем
К = G F ( 9 " ) , заданные уравнениями вида (III.2), где fi{x) - любой
из многочленов 1)-5).
В целях обхцности введем для многочлена Д (ж) обозначение
Ф{Х) = фM^^ ■ Фг(х)\
где ф\{х), ^2(а!) - многочлены из первых и вторых скобок записей
многочлена /i(a;) в случаях 1)-5) теоремы I I I . 1 .
Во всех указанных случаях нас интересуют простые дивизоры
поля F, их индексы ветвления и степени относительно поля К(х),
соответствующие функции нормирования. Условимся простые диви­
зоры Рх-а поля К{х) при а & К обозначать через РаТеорема. I I I . 6 Пусть К = GP{g"), F - поле алгебраических
функций, заданное уравнением у' = ф1(х)"ф2{х)^, а + Ь = s, s\ q—l,
(а, s) = 1, n > 1 при нечетном q, п> 2 при четном q. Тогда:
1) Р есть циклическое расширение поля К{х) степени s, К - алгеб­
раически замкнуто вР, и род поля Р д= ^ (deg Ф1 (х) + deg Ф2 (х) - 2) ;
2) для каждого простого дивизора Ра, а £ К, поля К{х) существу­
ет ровно S расширений Qa,p, где 0 пробегает все решения уравнения
у' = ^(а) в К; Qa,0 "^чк идеал порождается многочленом х — а и со­
держит у-Р; e{Qa,fi\Pa) = 1, degQc.,^ = degPa = 1, fiQcfil^c.) = 1 ;
3) для простого дивизора Poo поля К{х) существует s расширений
Qoo >---,Qoo , порождаемых как идеалы элементом х~^ и содержа­
щих соответственно элементы ух~"*^' — ^i,i = l,..., s, где ^i - кор­
ни степени s из 1 в поле К; при этом e{Q^^\Poo) = 1, degC?co = 1,
12
/(0Й|Роо) = 1, i = l,...,5;
4) если р{х) — неприводимый над К многочлен и р{х)\ф{х), то для
простого дивизора Рр(х) поля К(х) существует единственное рас­
ширение (3p(j); deg(9p(j)=degPp(i)=degp(x), e(Qp,^x)\Pp(z))=s,
/(<3p(i)l-Pp(i))=l;
5) если мгюгочлен р{х) неприводим мо^ К и р{х) )[ф{х), то простой
дивизор Рр(х) поля К{х) имеет eft
расширений QpL)> * ~ !>—>*;
где t\s и t зависит от р(х) и для каждого ги них siQpL)\Pp{x)) = 1»
nQpl)\Ppi^)) = h deg^it) = fdegp(^)-
Ниже рассмотрено поле F, заданное уравнением
j/^ = Л(х), где h{x) = X + х'"
= J J . _ {х- at).
Теорема I I I . 7 Пусть К = GF(q"), q - нечетно, п - четно, F поле алгебраических функций над К, заданное уравнением у^ = h{x),
а(х),6(х) 6 К[х], Ь{х) фО,иг = ^ . Тогда:
1) F - гиперэллиптическое поле функций рода д = ^{q^^^ ~ 1);
В) для Р = Ра;_о,, г = 1,...,q"^^, в F существует единственное
расширение Q = д » _ „ , , и e{Q\P) = 2, fiQ\P) = 1, degQ = 1,
VQ(Z) = 2(exp„_„. o(x) - expj_„, b(x));
3) для P = Pj._b, Ь ^ К,Ь-фа{,{ = \,..., q"/^, существуют ровно
2 расширения QW, Qx--b> которые порождаются многочленом х—Ь
и содержат, соответственно, у — с иу + с, где с - фиксированное
значение {h{b))^/\ При
amoMe{Q<'J\\P)=fiQi'lb\P)=degQl^lf,=l,
V > (^) = ехр,_ьа(х) - exp^_j6(x), j = 1,2;
4) для Роо в F существует единственное расширение Q^;
е(0оо|Роо)=2, /{Qoo|Poo)=deg<?«,=!, VQ„(2r)=2(deg6(x)-dega(x));
5) если р(х) - неприводимый над К многочлен степени т> \ и
h{x) не является квадратом в К[х]/р(х), то для Р = Рр(а;) суще­
ствует единственное расширениеQp^x)! ^{Qp{x)\P)=^> fiQp{x)\P)=^,
degQp(i) = 2degp(x), VQ^^^^{z) = exp^^^j o(x) - expp(^) 6(x);
6) если p(x) - неприводимый над К многочлен степени т> 1 и
h{x) - квадрат в К[х]/р{х), то для Р = Рр(а;) существуют ровно 2
расширения Q^'ly j = 1,2; e(Q<f^)|P) = f{Q%^\P)
= 1,
^^sQpix) = degp(x), VQO) (г) = expp(^) a{x) - expp(,) b{x).
13
Рассмотривая поля F типа I V и V, объединим эти случаи записав:
f(x) = h^{x) = x«'""""'+i - х"'--""^' = xix"' - а:)''"-""',
где U = 1 в случае IV, или и = 2 в слзгчае V.
Из теоремы II.6 следует, что уравнение
у"' -У = /1„(а)
(III.8)
имеет р' решений при любом а € GF{q"). С использованием этого
факта доказана
Теорема I I I . 8 Пусть F - поле алгебраических функций, задан­
ное уравнением (**) при f{x) = hu{x), и=1,2. Тогда:
1) F есть расширение поля К{х) степени р', К алгебраически за­
мкнуто в F ирод поля F: д = | ( р ' - 1)д("+")/2;
2) для каждого а £ К простой дивизор Ра = Рх-а поля К{х)
имеет р' различных расширений Qa,p> порождаемых многочленом
X — а и содержащих многочлены у — р, где /? пробегает все реше«ил уравнения (111.8) (при соответствующем и); e{Qa 0\Ра) — 1»
/ ( Q a , ^ | P a ) = p ' , degga.;8 = l ;
3) простой дивизор Роо поля К{х) имеет единственное расширение
Qoo; е(Ооо|Рос) = Р", }{Qoc\Poo) = degQoo = 1 ;
4) еслир{х) - неприводимый над К унитарный многочлен и degp(a:)>l,
то е(др(х)|Рр(х)) = 1, f{.Qp{x)\Pp(x))=J^, degQp(a:) = degp(a;).
Глава r V . Об алгебро-геометрических кодах Г о п п ы
В этой глгше исследуются свойства геометрических кодов Гоппы
на рассмотренных полях гшгебранческих функций.
При определении алгебро-геометрического кода Гоппы С(£>, G) в
поле алгебраических функций F в качестве дивизора D выбирают
сумму Q i + •• ■ + QN различных простых дивизоров степени 1 поля
F, в качестве G - любой дивизор с условием S{G) П S{D) — 0. Ко­
довыми словами являются все векторы {Z{Q\),...,Z{QN)),
Z € L{G).
Такие слова образуют линейное пространство над К, изоморфное
факторпространству L{G)/L{G - D). Если в G в качестве слагае­
мых участвуют лишь простые дивизоры степени 1, то D и G можно
рассматривать как дивизоры на кривой V, и С{Ь, G) естественно
называть кодом на кривой V.
Большая свобода выбора дивизора G, на первый взгляд, делает
трудно обозримым весь класс кодов Гоппы на F. Однако многие ва­
рианты выбора G приводят к эквивалентным кодам. В частности,
C{D,G) ~ C(D,G^), если Gi = G + (г), z £ F, (см., например, [9]).
А так как для любого G существует такое z G F, что G + (г) > О, то
достаточно брать лишь G > 0.
14
Если (7 > О и носитель S{G) дивизора G не содержит бесконеч­
ных простых дивизоров, то неравенство {а(х)/Ь{х)) + G >0 может
выполняться лишь при условии degb(a;) > dego(a;), что существен­
но ограничивает простргшство L{G). Поэтому при построении кодов
C{D,G) обычно в S{G) включают бесконечные простые дивизоры.
В случае I, когда F содержит s бесконечных простых дивизоров
для любого zeF вьшолняется равенство w^^) (^)=UgO) (г).
В связи с этим следует выбирать G так, чтобы QbJ,...,Qx
входили
в дивизор G с одинаковыми коэффициентами.
Всюду ниже в случ£1е I мы выбираем G удовлетворяющий ука­
занным выше условиям. При этом для упрощения записей введем
обозначение
Q _ Q ( I ) Ц_ ^ Q{e)
Для общности в записях в случаях П-П1 единственный бесконеч­
ный простой дивизор Qoo будем обозначать также
Нами получено еще одно существенное ограничение на выбор ди­
визора G при построении кода с точностью до эквивалентности. При
этом рассмотрена более общая ситуахщя, когда F задается уравне­
нием (*) над GF{q"), причем многочлен f{x) имеет каноническое
разлояжние над GF{q'*):
т
= а • П*^^РТ{Х),а € GF{q%
(IV.1)
причем s\q — l, s>l , deg/=Tn>0 , (s,ni) = 1 , г = I,...,к. (IV.2)
Заметим, что все эти условия выполняются в случаях 1-П1.
Теорема F V . l Пусть F - поле алгебраических функций, заданное над GF{q^) уравнением (*) при условиях (IV. 1), {IV.2) и G{D, G i )
- код, заданный в поле F дивизорами
к
I
D = QI + ... + QN ,Gi=
Y,^^^ riQp,^^^ -f- ^
.^^ SjQ,,(^) -I- rQoo,
Piix)\f{x), r, > 0 , i = l,...,k, gj(x)//(x), Sj > 0, j = l,...,l, r > 0.
Тогда код C{D,Gi) эквивалентен коду C{D,G) при
G ■=■ X)t=i iiQp,(x) + cQooi где U - остаток от деления п «о 5,
с = г + degcix), с(х) = П*=1 МФ^'^
■ пи ЧЛФ ■
Таким образом, при построении кодов Гоппы на i^ в случаях 1-П1
можно ограничится рассмотрением кодов C{D, G) лишь при дивизо­
рах G вида, зпказанного в теореме I V . l .
В случаях rV-V, когда F задается зфавнением (**), дивизор G
можно выбирать еще более простого вида.
Пусть F - поле алгебраических функций над полем GF{q^) хзг
рактеристики р, заданное згравнением yf' -у = f{x), где
deg/(a;) = т>о, ( т , р ) = 1, р* - l\q - 1.
15
Теорема I V . 2 В указанном выше поле F любой код C{D,Gi)
эквивалентен коду C{D,G), где G = rQooЗаметим, что в теореме IV. 1 избавиться в G от слагаемых второй
суммы 5^i=i hQp,(x)^ не нарушая эквивалентности кодов не всегда
возможно.
Рассмотрим поле F типа I или I I . Для построения кода выберем в
качестве дивизора D сумму всех N = sq^ простых дивизоров степени
1, кроме Qoo, i = l i ••-,«■•
D=^QI+Q2+-+QN-
(IV.6)
Согласно теореме IV. 1 при построении кодов с точностью до эк­
вивалентности в качестве G можно взять дивизор вида
^ = Е 1 ' , '•i.fc^i.* + Е ? 1 '■2.*^2.* + rQoo,
^~-'к=1
{IV.7)
*—'«=1
где Q . j = <Эр.,,(х). PijixMiix),
О < ri,j < 8, j = l,...,ti, t = 1,2,
г >0, Qoo — Yl'=i Q^ ■ Так как код C{D,G) изоморфен факторпространству L{G)/L{G — D), то для его описания достаточно описать
пространства L{G) и L{G — D).
В общем случае известно что код C{D,G) является линейным
[п, к, dj-кодом над полем К с параметрами к > deg G + 1 — д, где д род поля F, d> N — degG.
Если вьшолняется нергленство
2 5 - 2 < degG,
(IV.9)
то в силу теоремы РиманзгРоха ([9], стр.28-29) dim L(G)= deg G+l-g.
Если, кроме того, degG < iV, то L{G — D) = { 0 } , и в этом случае
A; = degG + l - f f .
Из утверждения 1) теоремы III.6 следует, что любой элемент z€F
однозначно представляется в виде
Z = uo{x) + Ui,{x)y +
h Us-i{x)y'~^, где Ui{x) G K{x).
(IV.10)
Выясним сначала, когда Uj(x)j/* € Lifi).
Л е м м а r V . l Элемент z = ^ X £ F, где i > 0, Q < j < s,
w{x) e GF{q")[x], {w{x),x) = 1, содержится в L{G) тогда и толь­
ко тогда, когда выполняются условия:
1) любой неприводимый над GF{q") делитель многочлена w{x) сов­
падает с одним из многочленовpi^k, I = 1,2, к = I,.. .,ti;
2) ехрр,^(^) w(,x) < ^i^,
k = l,'..,h;
3) expp,,(,) w{x) < 5 i i p i , k = l,...,t2;
4) degu;(a;) -i-jc
+ r>0, гдес= -VQW (J/) = 7 deg ф{х).
16
Выбирая теперь для каждого j унитарный многочлен Wj (х) наи­
большей степени, удовлетворяющий условиям 1)-3), получим
У^Лх) = Ф^^'^'Чх)Ф^'^'Нфф)9ф),
9Ф)=uiupM^f-'^^-^'-^h
где
92Л-)=m!=iP2*(^);'^i-[¥i.
Пусть dj = degwj{x) -jc + r, 0<j<s, Bj = | ^ ^ : 0 < t < djj,
если dj > 0, и Bj = 0, если dj = - 1 .
Теорема I V . 3 Если для определенного равенством (IVЛ) диви­
зора G выполняется условие (IV.9), то множество В = D'JZQBJ
является базисом пространства L{fl).
Следствие I V . l При условии (IV. 9)
L ( G ) = ( ^ + ^ y 4 - - - + ^ ^ y ' - : d e g a . ( x ) < d . , i = 0,...,.-l)
{wo{x)
wi(x)
Ws-iix)
J
Следствие ГУ.2 Если выполнено условие (IV.9), то элемент
Z вида (IV. 10) содерж:ится в L{G) тогда и только тогда, когда
Ui(x)y'eL{G),i
= 0,...,s-l.
Теперь при условии (IV.9) найдем базис пространства L{G — D).
Л е м м а rV.4 При условии (IV. 9):
a)L{G-D)
= {(хя"-х)
■ Е,б{о
.-i} ^У'
б) базисом пространства L{G — D) является
= dj>q-,degbj<dj-q'^},
множество
{^'^l^^■■dJ>Я'^,0<i<dj-q"}.
Для описания пространства L{G)/L{G—D) выделим в каждом из
смежных классов пространства L{G) по подпространству L{G—D)
по одному хфедставителю, которого и условимся принимать за эле­
мент пространства L{G)/L{G — D). Тогда имеет место
Теорема 1У.4 Если для дивизора G вида (IV. 7) выполнено усло­
вие (IV. 9), то
а) L{G)/L{G-D)
= { E J I Q ^У'
= dega,- < tj,tj = min{d„g" - 1 } } ,
б) базисом пространства L{G)/L{G
— D) является
множество
l-^^-7-т : 0 < j < s - l , d , > 0 , 0 < г < « Л .
\wj{x)
- ' - - ')
Для построения порождающей матрицы кода C(Z?,(?) упорядо­
чим простые дивизоры 1-ой степени поля F следующим образом:
QoL\3\i—i
Qa,n ,0,n , Voi,/3iC, •••) Qa,n ,/3,nO •••' Qai,0ii—^
17
i •••, Qa,r, , / 3 , " ^ ' ~ ' '
где ^ - любой элемент порядка s в поле F,n, a i , . . . , а,» - произ­
вольная перестановка элементов поля GF{q^^). Тогда при N = q^s,
порождающая матрица кода C{D, О) будет иметь вид
/ AQ
АО
...
Ао
\
Л1
A^i
...
Лle-^
А^
Аг
Аг^
... A^i'-^
\ Л _ 1 A . l i e ... А._1>-1 /
где Aj - матрица размеров (tj+l)x5", полученная из первых ij-V\
строк матрицы
/ 1
1
...
1
\
«1
В =
а?
V "Г"'
"2
о»-2
а.
1^
...
-,«"-2
а;;»
/
а,п
"j.e'
их покомпонентным умножением на вектор (uj_i,...,т;^
').
Следствие I V . 3 £/сли G имеет вид (IV.7), а D - (IV.6), выпол­
нено условие (IV. 9) и deg G < N,moC{D,G)
есть \N,fe,d],» -код, где
N=q'^s, k-degG+1-g, N- degG<d<N-8 ■ max{dj : j = 0,...,s-l}.
Следствие r V . 4 Если G = rQoo, D - дивизор из (IV.6), выпол­
нено условие (IV.9) и degG < N, то C{D,G) есть {М,к,(1\дп-код,
где N = q'^s, к = degG -g-^l,d = N- deg б?.
Замечание. Из этих двзгх следствий видно, что использовгшие в
качестве G дивизоров, отличных от rQoo возможно позволит строить
коды такой же размерности, что и при G = rQoo, но с большим кодо­
вым расстоянием. Однако подтверждающих эту гипотезу примеров
у автора пока нет.
Построим код Гоппы C{D,G) на простых дивизорах поля F, за­
данного над К = G F ( g " ) уравнением y^=f(x), где /(ж) = ж'" -(-а:,
q - нечетное, п > 2 - четное
Обозначим через А
{ui,..., Oe}, s = g"^^, множество всех корней
многочлена f{x), и через В = К\А = {bi,...,bt}. К а к показано в
теореме III.7 поле F в этом случае имеет следующие N = 2д" — д"/^
простых дивизоров степени 1:
Q.-a,, j = 1,..., g"/=', gi^lfc., g i ' l j . , J = 1...., t, Qoo.
l(m)
(m)
Обозначив: Qa:_o,=Ot, Qxlb =Qi
18
> возьмем в качестве D дивизор
Тогда, в силу теоремы I V . l , при построении кода C{D,G) с точно­
стью до эквивалентности в качестве G достаточно рассмотреть ди­
визор G = rQoo, г € N.
Заметим, что здесь в определении кода участвуют лишь простые
дивизоры первой степени. Поэтому его можно рассматривать как
код на кривой. При доказательстве вспомогательных утверждений
оказывается, что следует различать случаи:
!"• О < [|] < |(д"/' + Ю ;
20. |(<7"/2 + е)< [§] < д" - ^ ^
3". 9" - ^
4». [§] > д»,
< [§] < 9" ;
;
где 6 = 1 при четном г и е = - 1 при нечетном г.
Л е м м а r V . l O Код C{D,G)
состоит из векторов вида
[ziQi),...,z{Q,),z{Q\^\...,Z{QI\ziQ^^^...,z(gp)))
, где, в зависимости от случаев 1°-4°, элемент z пробегает множества:
l'>.Ci = {a{x): dega(a:) < [ § ] } ;
2". С2 = {а(х) + Ь{х)у : йе$а{х) < [§] ,deg6(x) < [§] -
2!^};
3°. Сз = {а{х) + Ъ{х)у : dega(a;) < [§] ,deg6(x) < g" - ?"/=' - l } ;
4". d = {а{х) + Ь(х)у : dega{x) <q"- l,deg6(a;) < g" - g"/^ - l } .
Теорема I V . 5 При указанном выборе дивизоров D, G код C{D, (?)
является линейным [N, к, cf]," -кодом, где N = 2д" — д"'^, а парамет­
ры к, d принимают в случаях 1° — 4" следующие значения:
l » . f c = [ f ] + l , d = 7V-2[§];
2o.k = 2m+l)-<^,N-r<d<N-{2[r].-il!;±^
+ l);
3°. fc = [§] - И -1- g" - g"/2, N-r<d<N([§] -I- g" - g"/^);
4°. k = N,d=l.
Заметим, что в случаях 2°, 3" при совпадении найденной верхней
оценки для d с истинным значением d код C{D, G) является МДРкодом, т.е. кодом с максимально достижимым кодовым расстоянием.
Из леммы IV. 10, содержащей описание кодов C{D,G) во всех че­
тырех случаях, легко находятся базисы соответствуюнщх пространств,
а значит и порождающие матрицы кодов, соответствующие выбран­
ным базисам.
Зафиксируем поле F типа IV-V. Из теоремы П1.8 следует, что
оно содержит N = p'q" простых дивизоров Qa,0 первой степени,
где а пробегает G F ( g " ) , а Р при фиксированном а - все решения
уравнения уР' —у = hu(a).
19
Рассмотрим код C{D,G),
определяемый дивизорами D, G на F:
^ = Y. «««,/?. G = rQ«,, г >0.
'
'QtP
Заметим, что из теоремы IV.2 следует, что при построении кодов,
с точностью до эквивалентности, достаточно рассматривать именно
такой дивизор G.
Л е м м а ГУ. 14 Полной системой представителей смежных клас­
сов пространства L{G) по подпространству L{D — G) может слу­
жить система многочленов z{x, 7/)=oo(a;)+ai(a;)y+...+Op._i(a;)y'''~^
при следующих ограничениях на а,{х):
1) если (/ - \)т <г < 1т,, I = 1, ...,р' - 1 , то degai(a;) < (г - тг)/р',
г = 0,1,...,/ - 1, aj{x) = 0,j=l,l
+ 1,...,р» - 1 ;
2) если (p*-l)m<r<p'g", то dtgа,{х)<{г-mi)/р',
г = О, . . . , р * - 1 ;
3) если p'q" + [1 - 1)т < г < p'{q" - q") + Im, I = 1, ...,p' - 1, mo
degoo(a;) <q", dego,(a;) < g" - g", i = 1 , . . . , / - 1 ,
degoj(i) > (r - mj)/p', j = 1,1 + 1, ...,p' - 1 ;
4) если r > p*(g" — g") + (p* - l ) m , mo degoo(a;) < g",
dego,(x) < g" - g » , i = l,...,p' - 1.
Используя лемму IV. 14, нетрудно построить базис пространства
L{G)IL{D - G).
Теорема I V . 6 Рассматриваемый код C{D, G) является линей­
ным [N,k,d\-KodoM, в котором параметры k,d удовлетворяют сле­
дующим условг1Ям:
1) если (/ - 1)т < г < 1т, 1 = 1,2,...,р' -\,ток
= ^'г^ [ ™ ] + /,
(p'-i+i) (?"- [^^^^]) <d<p'9'- [^^^^^] (p'-O-EtS [ ^ ] -i+1;
2а) если (р*-1)ш<г<р'д"-т-€, где е = Q при р*|г+тп, и е=1 при
р' Хг+т, то fc=r+l-iE^^^i^=!^ , p»g»-r<<i<p''g"-r + i £ - : : i ^ 2 ^ ;
26) если p'q'^ - m - е < г < p'g", mofc= г + 1 - (р* - l ) ( m - l ) / 2 ,
9" - ['•-"'у-^)] < d < p'g" - r + (p' - l)(m - l)/2;
3) если p^q" + {l-l)m<r
< p'{q" - g") -\-lm,l= 1,2, ...,p' -I, mo
fc = g" + (g" - g«)(Z - 1) + J^fj^ [ l ^ ] + p* - /,
9"- ['•""•У"^^] <d<(p'-i)g"+g«(/-l)-r+ [lEl^l^znzil] + ^ | : J [ r ^ p ] +;.
^; еслиг>р''(д"-д")+{р''-1)т, mo A;=p»g"-{p»-l)g", d=g"+p*-l.
Заметим, что в случаях 3)-4) при р' = 2 полученные коды явля­
ются МДР-кодами. Это повышает интерес к рассмотрению случаев
г > N, которые обычно опускаются.
20
ЛИТЕРАТУРА
1. Влэдуц С.Г., Мании Ю.И. Линейные коды и модулярные кри­
вые. Итоги науки и техники, т.25, 1984, 209-257.
2. Влэдуц С.Г., Ногин Д.Ю., Цфасман М.А. Алгеброгеометрические коды. Основные понятия. М.: МЦНМО, 2003.
3. Гоппа В.Д. Коды на алгебраических кривых. Д А Н СССР, т.24,
П.1, 1981, 170-172.
4. Степанов С.А. О нижних оценках сумм харгистеров над конеч­
ными полями. Дискретная математика, т.З, вып.2, 1991, 77-86.
5. Степанов С.А. Арифметика алгебраических кривых. Москва,
"Наука", 1991.
6. Степанов С.А., Озбудак Ф. Расслоенные произведения гипер­
эллиптических кривых и геометрические коды Гоппы. Дискретная
мат., T.9. вып.З, 1997, 36-42.
7. Цфасман М.А. Коды Гоппы, лежащие выше границы
ВаршамовагГильберта. Проблемы передачи инф., т. 18, п.З, стр.3-6.
8. Stepanov S.A. Codes on Algebraic Curves.
Kluwer Academic/Plenum Publishers, 1999.
9. Stichtenoth H. Algebraic functionfieldsand codes. Springer-Verlag,
1993.
10. Tsfasman M.A., Vladut S.G., Zink T. Modular curves, Shimura
curves, and Goppa codes, better then Varshamov-Gilbert bound.
Math.Nachr., v.l09, 1982, 21-28.
Публикации автора по теме диссертации
11. Глухов М.М.-мл. Нижние оценки сумм харгистеров от много­
членов. Тезисы докладов Международной конференции "Современ­
ные проблемы теории чисел", Тула, 1993, 36.
12. Глухов М.М.-мл. Нижние оценки сумм характеров от много­
членов над конечными полями. Дискретная мат., т.б, вып.З, 1994,
136-142.
13. Глухов М.М.-мл. О Ксшонических разложениях некоторых дву­
членов над GF{q"^). Тезисы докладов I I международной конферен­
ции "Алгебраические, вероятностные, геометрические, комбинатор­
ные и функциональные методы в теории чисел", Воронеж, 1995, 41.
14. Глухов М.М.-мл. О кодах Гоппы на кривой у^ = х + ж'" .
Материалы V I I Международного семинара "Дискретная математика
и ее приложения", Москва, 2001, 303-304.
15. Глухов М.М.-мл. О кодах Гоппы на одном семействе полей
алгебраических функций. Дискретная математика, т.13, вып.2, 2001,
14-34.
16. Глухов М.М.-мл. О кодах Гоппы на суперэллиптических кри­
вых и полях алгебраических функций. Вестник И К С И , серия " К " ,
спец. вьгауск, М.:2003, 118-127.
17. Ozbudak F., Glukhov M.-jr. Codes on superelliptic curves. Turkish
j . of Math., V.22, n.2, 1998, pp.223-234.
21
Всего пронумеровано 22 стр.
Подписано к печати 24.10.2005 г.
Авт. л. 0,91 Усл. печ. л. 1,37
Заказ № 241ф/05
Тираж 70 экз.
Типография в/ч 33965
22
1120835
РНБ Русский фонд
2006-4
19430
Документ
Категория
Без категории
Просмотров
0
Размер файла
949 Кб
Теги
bd000100074
1/--страниц
Пожаловаться на содержимое документа