О конструкции кривой, соответствующей подкоду наименьшего веса рационального кода Гоппы

DOI:

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

В работе приводятся некоторые результаты, полученные в процессе построения кривых, в конструкции которых участвуют геометрические коды Гоппы C _l( D,G ) над конечным полем F _p с параметрами [п,к].

1.    Весовая иерархия и конструкция подкодов наименьшего веса

Алгебро-геометрический подход к теории кодирования информации начал развиваться в начале 80-х гг. прошлого столетия. Идея построения кодов на точках алгебраических кривых принадлежит Валерию Денисовичу Гоппе. Линейный код Гоппы, связанный с гладкой проективной кривой С над конечным полем, определяется следующим образом. Пусть С — абсолютно неприводимая гладкая проективная кривая над полем F _p . Пусть Р 1 ,...,Р _п есть различные F p -рациональные точки на С и дивизор D = Р 1 + ... + Р „ . Дивизор G Е Div(C ) такой, что носители G и D не пересекаются. Линейное пространство

L(G) = {/ EFP(C)* |(/) + G > 0}U{0} порождает линейное отображение

Ev : L(G) ■ ! ,  / ^ (/(Р 1 ),...,/ (Р^)

Образ этого отображения есть линейный [п, к]-код C _l( D,G ) над конечным полем F _p .

Если С — линейный код длины п и размерности к, то носитель подкода D С С определяют как множество номеров координат, в которых по крайней мере одно кодовое слово имеет ненулевую координату [4]. Обозначим носитель x(D). Тогда

x(D) = { i |3 ж = (^ 1 ,..., х _п ) Е D,X i = 0 } .

Количество элементов в носителе определяет вес подкода D:

^^(D) = M^D)I .

r-й обобщенный вес Хемминга кода равен весу, оказавшемуся наименьшим среди весов подкодов кода С, размерности г, то есть dr(С) = min{w(D) |D С С, dim D = г }, 1 < г < к.

Весовой иерархией кода С называется набор:

{ d _T (С) | 1 <  г <  к } .

Известно, что г-й обобщенный вес Хемминга кода СL(D,аРю) может быть вычислен по формуле dr(Cl(D, аР^У) = п — к + г, 1 < г < к.

Но, кроме иерархии весов кода, требуется явная конструкция подкода, на котором достигается обобщенный вес Хемминга. В частности, для геометрических кодов Гоппы вида С _L (D,аР _ю ) подкоды минимального веса можно построить следующим образом.

Пусть Dr — г-мерный подкод Fp-кода С, носитель которого удовлетворяет условию lx(Dr )| = dr (С).

Предположим, что этот подкод порождается элементами Ev(/ 1 ),..., Ev(/ _r ). Выполнение условия для носителя говорит о том, что в базисе кода D _r все кодовые слова имеют точно п — d _r различных координат, значения которых равны нулю для всех элементов базиса. Или, формулируя вышесказанное в терминах дивизоров, получим

(/г) = А + Вг — аР^, 1 < г < г, где дивизоры А и Вг такие, что:

0 <  А <  D, deg А = п — d _r ,В _г >  0,1 <  г <  г.

Причем, носитель дивизора В _г может состоять из рациональных точек. Построенные таким образом элементы / _г , 1 <  г <  г представимы в виде:

а

/ г (х) = П (ж — ац ), O ij Е Е р , 1 <  г <  г.

3 = 1

Дальнейшая конструкция требует представления полученного кода в виде след-кода.

2.    Представление подкода в виде след-кода

Для того чтобы представить подкод наименьшего веса в виде следа некоторого кода, определенного над полем Е _р т , потребуется расширить поле констант. Напомним, что алгебраическое расширение Е ‘ /К ‘ поля Е/К называется расширением поля констант, если Е ‘ = ЕК ‘ .

Рассмотрим поле рациональных функций Е _р (х)/Е _р . Тогда расширение Е _р т (х^/Е р т является расширением поля констант. В поле рациональных функций Е _р (х)/Е _р существует точно р +1 точка степени один. Выясним поведение рациональных точек при подъеме поля констант.

Лемма. Если Р — рациональная точка поля Е _р (х^/Е _р , то в расширении Е _р т (х)/Е _р т существует единственная точка степени один, лежащая над точкой Р.

Доказательство. Пусть Q точка поля Е _р т (х)/Е _р т , лежащая над точкой Р . Тогда из условия

/(Q |Р) • degP = degQ • т следует, что относительная степень

/(Q | Р) = degQ • т.

Так как / (Q | Р) <  т, следовательно degQ = 1. Таким образом, над точкой Р будут лежать только рациональные точки поля Е _р т (х)/Е _р т . Известно, что расширение поля констант не разветвлено, то есть индекс ветвления e(Q | Р) = 1, для всех точек Р Е Е Р р р (ж) и всех точек Q Е P ^ ^m ( _ж ) таких, что Q | Р. Если Q 1 ,. .. ,Q _r — все точки поля Е _р т (х)/Е _р т , лежащие над Р , тогда из условия

r

• У. e(Q . | Р) • / (Q , | Р ) = т г=1

заключаем, что г = 1. Следовательно, над точкой Р будет лежать одна точка поля F _p m (x')/F _p m . Лемма доказана.

Пусть F ‘ /К ‘ — алгебраическое расширение поля F/K . Для точки Р Е Г р конорма определяется следующим образом:

Сопр‘/р(Р) = ^e(Q |Р) •Q, QIP где сумма берется по всем точкам Q, лежащим над точкой Р, а целое число e(Q |Р) — индекс ветвления точки Q над Р.

Для элемента х — а Е F _p (x) обозначим (х — а _р ) р — дивизор нулей этого элемента.

Имеем

^(х - « Р ^{) р}

= р

—  а .

Рассмотрим дивизор нулей этого же элемента в поле F _p m (х) = F ‘ :

^(х - ^{а ) р} ‘ = Con p ‘ /р ^((х - ^{а ) р} ) = ^Con _p‘ _/р ^(Р а ) = ^^{e(Q | Р}) • ^Q = ^Q.

QIP

Таким образом, точка Q, лежащая над точкой Р _а , является единственным нулем элемента х — а.

Пусть / _г — элементы поля F _p (x), причем

а

Цх) = П (х — а гз ), « г, Е F p , 1 <  г <  г.

3 = 1

Каждому элементу / _г поставим в соответствие элемент Д / ^ ( _ж ) , определяемый следующим образом:

т—1                ат—

RllW = (£ • ■ у-—1Ъх — £ «,( £ ■■

5=0                  3=1

а        т—1                                   ат—

+ £ Оу « гк ( £ (Ьх) ^? ) ^а - ³ Ьх -----+ ( — 1) ^а- 2    £    O jj i • ... • O ij _a- 2 £ (Ьх) ^Р ” Ьх +

3=к          S=0                                       31<...<3а-25

а

+ ^{( — 1) а 1}     ^^     ^а г, ₁ • . . . • ^a ij _a-1 ^Ьх + ^{( — 1) а а} г ^,

3 1 <...<3 а - 1

а где Tr(aj) = П «у. Здесь Tr — отображение следа: 3 = 1

Tr : F _p m ^ F _p , т E Z, т> 1.

Элемент b Е F _p m такой, что Tr(b) = 1.

Теорема. Пусть D _r — г-мерный подкод F _p -кода С = С ь (В,аР_Ж1'), носитель которого удовлетворяет условию | x(D _r ) | = d _T (С ) . Для любого кодового слова с Е D _r существует элемент R Е F _p m [х] такой, что

Tr con _D (R) = с.

Доказательство. Пусть D _r — г-мерный подкод Е _р -кода Гоппы С = C l ( D, aP ^ ). Предположим, что код D _r порождается кодовыми словами с ₁ ,...,с _г , где c _i = Ev(f _i ), 1 <  <   г <  г. Элементы Д,... ,f _r Е L(aP ^ ) являются линейно независимыми над Е _р . Осуществим выбор базиса кода D _r таким образом, чтобы элементы f _i , 1 <  г <  г допускали представление в виде а

&(^ж) = П^{(ж - a} ij ),

• 3 = 1

где O ij Е Е _р , 1 <  г <  г. Каждому элементу f _i (x) поставим в соответствие R _i Е Е _р т [ж]. Пусть точка P _s Е supp(Con(D)), 1 <  s <  п, тогда

P s = P _X —Y _S , Y s Е Е р .

Для точек P _s Е supp(Con(D)), 1 <  s <  п выполняется

Tr(R i (P s )) = f i (Y s ).

Тогда для 1 <  г <  г получим

Tr con( _O ) (R i ) = Tr(R i (P i ),..., R i (P _n )) = (f i (Y i ),..., f i (Y n )) = C i .

r

Пусть с — кодовое слово, тогда с = ^2 в _i c _i , в г Е Е _р , следовательно, получим i=1

r              r                                             r с = 52 вiCi = 52 ei Trcon(O)(Ri) = Trcon(O)(52 eiRi).

i=1         i=1                                  i=1

Теорема доказана.

Таким образом, если Dr — г-мерный подкод Ер-кода С = C^(D,aP^), носитель которого удовлетворяет условию lX(Dr )| = dr (С), элементы R1,...Rr Е Ерт(ж) такие, что Trcon(p)(Ri) = ci, 1 < г < г, где с1,...,сг — базис кода Dr, то, обозначив U = (R1,... ,Rr) — г-мерное векторное пространство над полем Ер, получим

Tr con(D) (U) = D r .

3.    Анализ явного вида кривой, соответствующей подкоду наименьшего веса рационального кода Гоппы

Пусть Dr — г-мерный подкод рационального кода Гоппы C^(D,aP^), носитель которого удовлетворяет условию lX(Dr )| = dr (CL(D,aP_)).

Элементам базиса сд^ этого подкода поставим в соответствие кривые Артина — Шрайера Сд^ с аффинным уравнением у5 - Уг = R^x) 1 < г < г, здесь элемент R5(x) Е U соответствует слову с д.. Fp-векторное пространство U С С Fpm (х) и подкод DГ связывает следующее соотношение:

Trcon(D)(U) = {Tcon(D)(R) IR EU } = DT, где Tr — отображение следа

Tr : F p m ^ F _p .

Для элемента R Е U обозначим ф д (Т ) = Т ^p — Т — R Е F[Т ]. Пусть Е у — поле разложения всех многочленов ф _Д (Т ) над полем F = F _p m (х). Многочлен ф _Д (Т), соответствующий элементу 0 = R Е U , либо неприводим над полем F , либо разлагается в произведение линейных сомножителей. Предположим последнее, то есть существует элемент z Е F , являющийся корнем ф д (Т). Тогда z^p — z = R и, кроме того, v _{P i} (z ) >  0 для всех точек Р _г Е Г р . Вычислим

Tr conP (R) = (Tr(z ^p — z)(P i ),..., Tr(z ^p — z )(P „ )).

Полагая в ₅ = z (P ₅ ) Е F _p m , 1 <  г <  n, получим:

Tr conP (R) = (Tr(e p — в 1 ),..., Tr(e £ — в п )).

Тогда Trconp (R) = 0. С другой стороны, 0 = R Е U, следовательно, существуют Г элементы а Е Fp такие, что R = ^2 o5R5. Вычислим

5=1 Г                 Г                               Г

TrCon(P)(R) = Tr(52 а R = 52 а Trcon(D)(R5) = 52 агСг, где с5 — кодовое слово, ассоциированное с элементом R5 Е U. Таким образом, имеем Г

^2 a ^ c ₅ = 0, что возможно только в случае равенства нулю всех коэффициентов а _г Е F _p . 5=1

Но это противоречит выбору элемента 0 = R Е U , следовательно, многочлен ф д (Т ) неприводим. Поле Е у является полем разложения сепарабельных многочленов ф д (Т) над F и, следовательно, расширение Е у /F является расширением Галуа.

Рассмотрим элементы у1, ...,уГ Е Еу такие, что yp — Уг = R5, тогда Еу = F(у1, ...,уп). Обозначим Gal(Ey/F) — группа Галуа расширения Еу/F. Отображение ст : F ^ F определим следующим образом:

^(Уг) = Уг + аг, аг Е Fp, 1 < г < г, тогда т Е Gal(Ey/F). Имеем рг <|Gal(Ey(F)| = [Еу :F] < рГ.

Таким образом, [Е _у : F ] = р ^Г . Кроме того, для всех т Е Gal(E _y /F ) выполняется c ^p = id. Тогда расширение Е _у /F является элементарным абелевым р-расширением [2].

Существует точно ^ —¹ промежуточных полей F С Е С Е _у степени [Е : F ] = р, каждое из которых определяется следующим образом:

Е = E _r = F(у), у^р - у = R G и \{ 0 } .

Таким образом, имеем Еу/F — элементарное абелево расширение степени рт. Основные параметры этого расширения исследуются в работе [1]. Тогда существует элемент у G Еу такой, что Еу = F(у), при этом минимальный многочлен элемента у над полем F имеет вид г Г —1 ф(Т) = трГ - Т - г, . = ЕЕ а-^. з=1 i=o

Поле Еу — поле рациональных функций кривой Суг, которая соответствует подкоду Dr. Таким образом, подкоду наименьшего веса соответствует кривая над полем Fpm, задаваемая уравнением г г—1 у^ - у = ЕЕ а—Х. 3=1 i=0