close

Вход

Забыли?

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

?

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

код для вставкиСкачать
МАТЕМАТИКА
www.volsu.ru
DOI: https://doi.org/10.15688/jvolsu1.2016.4.5
УДК 512.77
ББК 22.147
О КОНСТРУКЦИИ КРИВОЙ,
СООТВЕТСТВУЮЩЕЙ ПОДКОДУ НАИМЕНЬШЕГО ВЕСА
РАЦИОНАЛЬНОГО КОДА ГОППЫ
Юлия Сергеевна Касаткина
Старший преподаватель кафедры компьютерной безопасности,
Балтийский федеральный университет им. И. Канта
yuliya_kasatkina@list.ru
ул. А. Невского, 14, 236041 г. Калининград, Российская Федерация
Анна Сергеевна Касаткина
Преподаватель кафедры экономики и информационных технологий,
Западный филиал Российской академии народного хозяйства
и государственной службы
kasatkina_ana@mail.ru
ул. Артиллерийская, 18, 236016 г. Калининград, Российская Федерация
© Касаткина Ю.С., Касаткина А.С., 2016
Аннотация. Исследуется конструкция кривых, ассоциированных с геометрическими кодами Гоппы. Для построения этих кривых используются подкоды малого веса. В работе изложен способ построения кривых, ассоциированных с рациональными кодами Гоппы.
Ключевые слова: геометрический код Гоппы, обобщенный вес кода,
подкод наименьшего веса, алгебраическая кривая, способ построения кривой.
Введение
При построении эффективной системы связи, для защиты сообщения от ошибок
используют помехоустойчивое кодирование, поэтому проблема получения новых кодов с
хорошими характеристиками представляется актуальной. Конструкция некоторых классов кодов требует кривые, обладающие достаточным числом рациональных точек. Для
построения таких кривых возможно использовать кодовые слова малого веса. Этим кодовым словам можно поставить в соответствие кривые Артина — Шрайера. Соответствие, в свою очередь, может быть продолжено до подкодов, на которых достигается
обобщенный вес Хемминга, и расслоенного произведения кривых Артина — Шрайера.
ISSN 2222-8896. Вестн. Волгогр. гос. ун-та. Сер. 1, Мат. Физ. 2016. № 4 (35)
75
МАТЕМАТИКА
В работе приводятся некоторые результаты, полученные в процессе построения кривых,
в конструкции которых участвуют геометрические коды Гоппы  (, ) над конечным
полем  с параметрами [, ].
1. Весовая иерархия и конструкция подкодов наименьшего веса
Алгебро-геометрический подход к теории кодирования информации начал развиваться в начале 80-х гг. прошлого столетия. Идея построения кодов на точках алгебраических кривых принадлежит Валерию Денисовичу Гоппе. Линейный код Гоппы,
связанный с гладкой проективной кривой  над конечным полем, определяется следующим образом. Пусть  − абсолютно неприводимая гладкая проективная кривая над
полем  . Пусть 1 , . . . ,  есть различные  -рациональные точки на  и дивизор
 = 1 + . . . +  . Дивизор  ∈ () такой, что носители  и  не пересекаются.
Линейное пространство
() = { ∈  ()* |( ) +  ≥ 0} ∪ {0}
порождает линейное отображение
 : () →  ,
 ↦→ ( (1 ), . . . ,  ( )).
Образ этого отображения есть линейный [, ]-код  (, ) над конечным полем  .
Если  — линейный код длины  и размерности  , то носитель подкода  ⊂ 
определяют как множество номеров координат, в которых по крайней мере одно кодовое
слово имеет ненулевую координату [4]. Обозначим носитель (). Тогда
() = { |∃ = (1 , . . . ,  ) ∈ ,  ̸= 0}.
Количество элементов в носителе определяет вес подкода :
() = |()| .
r-й обобщенный вес Хемминга кода равен весу, оказавшемуся наименьшим среди весов
подкодов кода  , размерности , то есть
 () = min{() | ⊆ , dim  =  }, 1 ≤  ≤ .
Весовой иерархией кода  называется набор:
{ () |1 ≤  ≤  }.
Известно, что -й обобщенный вес Хемминга кода  (, ∞ ) может быть вычислен по
формуле
 ( (, ∞ )) =  −  + , 1 ≤  ≤ .
Но, кроме иерархии весов кода, требуется явная конструкция подкода, на котором
достигается обобщенный вес Хемминга. В частности, для геометрических кодов Гоппы
вида  (, ∞ ) подкоды минимального веса можно построить следующим образом.
Пусть  — -мерный подкод  -кода  , носитель которого удовлетворяет условию
|( )| =  ().
76
Ю.С. Касаткина, А.С. Касаткина. О конструкции кривой, соответствующей подкоду
МАТЕМАТИКА
Предположим, что этот подкод порождается элементами (1 ), . . . , ( ). Выполнение условия для носителя говорит о том, что в базисе кода  все кодовые слова имеют
точно  −  различных координат, значения которых равны нулю для всех элементов
базиса. Или, формулируя вышесказанное в терминах дивизоров, получим
( ) =  +  − ∞ , 1 ≤  ≤ ,
где дивизоры  и  такие, что:
0 ≤  ≤ , deg  =  −  ,  ≥ 0, 1 ≤  ≤ .
Причем, носитель дивизора  может состоять из рациональных точек. Построенные
таким образом элементы  , 1 ≤  ≤  представимы в виде:
 () =

∏︁
( − α ), α ∈  , 1 ≤  ≤ .
=1
Дальнейшая конструкция требует представления полученного кода в виде следкода.
2. Представление подкода в виде след-кода
Для того чтобы представить подкод наименьшего веса в виде следа некоторого кода, определенного над полем  , потребуется расширить поле констант. Напомним, что
алгебраическое расширение  ′ / ′ поля / называется расширением поля констант,
если  ′ =   ′ .
Рассмотрим поле рациональных функций  ()/ . Тогда расширение
 ()/ является расширением поля констант. В поле рациональных функций
 ()/ существует точно  + 1 точка степени один. Выясним поведение рациональных
точек при подъеме поля констант.
Лемма. Если  — рациональная точка поля  ()/ , то в расширении  ()/
существует единственная точка степени один, лежащая над точкой  .
Доказательство. Пусть  точка поля  ()/ , лежащая над точкой  . Тогда из
условия
 ( | ) · deg  = deg  · 
следует, что относительная степень
 ( | ) = deg  · .
Так как  ( | ) ≤ , следовательно deg  = 1. Таким образом, над точкой  будут
лежать только рациональные точки поля  ()/ . Известно, что расширение поля
констант не разветвлено, то есть индекс ветвления ( | ) = 1, для всех точек  ∈
∈ P () и всех точек  ∈ P () таких, что  | . Если 1 , . . . ,  — все точки поля
 ()/ , лежащие над  , тогда из условия

∑︁
( | ) ·  ( | ) = 
=1
ISSN 2222-8896. Вестн. Волгогр. гос. ун-та. Сер. 1, Мат. Физ. 2016. № 4 (35)
77
МАТЕМАТИКА
заключаем, что  = 1. Следовательно, над точкой  будет лежать одна точка поля
 ()/ . Лемма доказана.
Пусть  ′ / ′ — алгебраическое расширение поля / . Для точки  ∈ P конорма
определяется следующим образом:
∑︁
Con ′ / ( ) =
( | ) · ,
|
где сумма берется по всем точкам , лежащим над точкой  , а целое число ( | ) —
индекс ветвления точки  над  .
Для элемента  − α ∈  () обозначим ( − α )0 — дивизор нулей этого элемента.
Имеем
( − α )0 = α .
Рассмотрим дивизор нулей этого же элемента в поле  () =  ′ :
∑︁
′
( − α)0 = Con ′ / (( − α)0 ) = Con ′ / (α ) =
( | ) ·  = .
|
Таким образом, точка , лежащая над точкой α , является единственным нулем элемента  − α.
Пусть  — элементы поля  (), причем
 () =

∏︁
( − α ), α ∈  , 1 ≤  ≤ .
=1
Каждому элементу  поставим в соответствие элемент  () , определяемый следующим образом:
−1
∑︁

() )−1  −
 () = (
=0
+

∑︁
=1
−1
∑︁
α α (
̸=

∑︁
=0
 −3
() )
α (
−1
∑︁

() )−2  +
=0
−2
 − · · · + (−1)

∑︁
α1 · . . . · α−2
1 <...<−2

∑︁
−1
+ (−1)
−1
∑︁

()  +
=0
α1 · . . . · α−1  + (−1) α ,
1 <...<−1
где Tr(α ) =

∏︀
α . Здесь Tr — отображение следа:
=1
Tr :  →  ,  ∈ ,  > 1.
Элемент  ∈  такой, что Tr() = 1.
Теорема. Пусть  — -мерный подкод  -кода  =  (, ∞ ), носитель которого удовлетворяет условию |( )| =  (). Для любого кодового слова  ∈ 
существует элемент  ∈  [] такой, что
TrCon () = .
78
Ю.С. Касаткина, А.С. Касаткина. О конструкции кривой, соответствующей подкоду
МАТЕМАТИКА
Доказательство. Пусть  — -мерный подкод  -кода Гоппы  =  (, ∞ ). Предположим, что код  порождается кодовыми словами 1 , . . . ,  , где  = ( ), 1 ≤
≤  ≤ . Элементы 1 , . . . ,  ∈ (∞ ) являются линейно независимыми над  . Осуществим выбор базиса кода  таким образом, чтобы элементы  , 1 ≤  ≤  допускали
представление в виде

∏︁
 () =
( − α ),
=1
где α ∈  , 1 ≤  ≤ . Каждому элементу  () поставим в соответствие  ∈  [].
Пусть точка  ∈ supp(Con()), 1 ≤  ≤ , тогда
 = −γ , γ ∈  .
Для точек  ∈ supp(Con()), 1 ≤  ≤  выполняется
Tr( ( )) =  (γ ).
Тогда для 1 ≤  ≤  получим
TrCon() ( ) = Tr( (1 ), . . . ,  ( )) = ( (γ1 ), . . . ,  (γ )) =  .
Пусть  — кодовое слово, тогда  =

∑︀
β  , β ∈  , следовательно, получим
=1
=

∑︁
=1
β   =

∑︁

∑︁
β  ).
β TrCon() ( ) = TrCon() (
=1
=1
Теорема доказана.
Таким образом, если  — -мерный подкод  -кода  =  (, ∞ ), носитель
которого удовлетворяет условию
|( )| =  (),
элементы 1 , ... ∈  () такие, что TrCon() ( ) =  , 1 ≤  ≤ , где 1 , ...,  −
базис кода  , то, обозначив  = ⟨1 , . . . ,  ⟩ — -мерное векторное пространство над
полем  , получим
TrCon() ( ) =  .
3. Анализ явного вида кривой, соответствующей подкоду наименьшего веса
рационального кода Гоппы
Пусть  − -мерный подкод рационального кода Гоппы  (, ∞ ), носитель
которого удовлетворяет условию
|( )| =  ( (, ∞ )).
Элементам базиса  этого подкода поставим в соответствие кривые Артина — Шрайера
 с аффинным уравнением
ISSN 2222-8896. Вестн. Волгогр. гос. ун-та. Сер. 1, Мат. Физ. 2016. № 4 (35)
79
МАТЕМАТИКА
 −  =  (), 1 ≤  ≤ ,
здесь элемент  () ∈  соответствует слову  .  -векторное пространство  ⊆
⊆  () и подкод  связывает следующее соотношение:
}︀
{︀
TrCon() ( ) = TrCon() () | ∈  =  ,
где Tr — отображение следа
Tr :  →  .
Для элемента  ∈  обозначим ϕ ( ) =   −  −  ∈  [ ]. Пусть  −
поле разложения всех многочленов ϕ ( ) над полем  =  (). Многочлен ϕ ( ),
соответствующий элементу 0 ̸=  ∈  , либо неприводим над полем  , либо разлагается
в произведение линейных сомножителей. Предположим последнее, то есть существует
элемент  ∈  , являющийся корнем ϕ ( ). Тогда   −  =  и, кроме того, ν () ≥ 0
для всех точек  ∈ P . Вычислим
TrCon  () = (Tr(  − )(1 ), . . . , Tr(  − )( )).
Полагая β = ( ) ∈  , 1 ≤  ≤ , получим:
TrCon  () = (Tr(β1 − β1 ), . . . , Tr(β − β )).
Тогда TrCon  () = 0. С другой стороны, 0 ̸=  ∈  , следовательно, существуют

∑︀
α  . Вычислим
элементы α ∈  такие, что  =
=1



∑︁
∑︁
∑︁
α  ,
α TrCon() ( ) =
α  ) =
TrCon() () = Tr(
=1
=1
=1
где  − кодовое слово, ассоциированное с элементом  ∈  . Таким образом, имеем

∑︀
α  = 0, что возможно только в случае равенства нулю всех коэффициентов α ∈  .
=1
Но это противоречит выбору элемента 0 ̸=  ∈  , следовательно, многочлен ϕ ( )
неприводим. Поле  является полем разложения сепарабельных многочленов ϕ ( )
над  и, следовательно, расширение  / является расширением Галуа.
Рассмотрим элементы 1 , ...,  ∈  такие, что
 −  =  ,
тогда  =  (1 , ...,  ). Обозначим ( / ) − группа Галуа расширения  / .
Отображение σ :  →  определим следующим образом:
σ( ) =  + α , α ∈  , 1 ≤  ≤ ,
тогда σ ∈ ( / ). Имеем
 ≤ |( / )| = [ :  ] ≤  .
Таким образом, [ :  ] =  . Кроме того, для всех σ ∈ ( / ) выполняется
σ = . Тогда расширение  / является элементарным абелевым -расширением [2].
80
Ю.С. Касаткина, А.С. Касаткина. О конструкции кривой, соответствующей подкоду
МАТЕМАТИКА

−1
промежуточных полей  ⊂  ⊂  степени [ :  ] = , каждое
Существует точно −1
из которых определяется следующим образом:
 =  =  (),   −  =  ∈  ∖{0}.
Таким образом, имеем  / — элементарное абелево расширение степени  . Основные параметры этого расширения исследуются в работе [1]. Тогда существует элемент  ∈  такой, что  =  (), при этом минимальный многочлен элемента  над
полем  имеет вид
ϕ( ) = 

−  − ,  =
 ∑︁
−1
∑︁

α−1  .
=1 =0
Поле  — поле рациональных функций кривой  , которая соответствует подкоду  . Таким образом, подкоду наименьшего веса соответствует кривая над полем  ,
задаваемая уравнением


− =
−1
 ∑︁
∑︁

α−1  .
=1 =0
СПИСОК ЛИТЕРАТУРЫ
1. Касаткина, Ю.␣С. Анализ рода кривой, соответствующей подкоду наименьшего веса
рационального кода Гоппы / Ю.␣С. Касаткина, А.␣С. Касаткина // Вестник Волгоградского
государственного университета. Серия 1, Математика. Физика. — 2014. — № 4 (23). —
C. 6–10.
2. Garcia, A. Elementary Abelian p-Extensions of Algebraic Function Fields / A. Garcia,
H. Stichtenoth // Manuscripta math. — 1991. — Vol. 72. — P. 67–79.
3. Stichtenoth, H. Generalized Hemming Weights of Trace Codes / H. Stichtenoth,
V. Voss // IEEE Trans. Inform. Theory. — 1994. — Vol. 40. — P. 554–558.
4. Wei, V.␣K. Generalized Hemming Weights for Linear Codes / V.␣K. Wei // IEEE Trans.
Inform. Theory. — 1991. — Vol. 37. — P. 1412–1418.
REFERENCES
1. Kasatkina Yu.S., Kasatkina A.S. Analiz roda krivoy, sootvеtstvuyushchеy podkodu
naimеnshеgo vеsa ratsionalnogo koda Goppy [On the Genus of the Curve Corresponding to the
Subcode of Low Weight of a Rational Goppa Code]. Vеstnik Volgogradskogo gosudarstvеnnogo
univеrsitеta. Sеriya 1, Matеmatika. Fizika [Science Journal of Volgograd State University.
Mathematics. Physics], 2014, no. 4 (23), pp. 6-10.
2. Garcia A., Stichtenoth H. Elementary Abelian P-Extensions of Algebraic Function
Fields. Manuscripta math., 1991, vol. 72, pp. 67-79.
3. Stichtenoth H., Voss V. Generalized Hemming Weights of Trace Codes. IEEE Trans.
Inform. Theory, 1994, vol. 40, pp. 554-558.
4. Wei V.K. Generalized Hemming Weights for Linear Codes. IEEE Trans. Inform. Theory,
1991, vol. 37, pp. 1412-1418.
ISSN 2222-8896. Вестн. Волгогр. гос. ун-та. Сер. 1, Мат. Физ. 2016. № 4 (35)
81
МАТЕМАТИКА
ON CONSTRUCTION OF THE CURVE CORRESPONDING TO THE SUBCODE
OF LOW WEIGHT OF A RATIONAL GOPPA CODE
Yuliya Sеrgееvna Kasatkina
Senior Lecturer, Department of Computer Security,
Immanuel Kant Baltic Federal University
yuliya_kasatkina@list.ru
А. Nevskogo St., 14, 236041 Kaliningrad, Russian Federation
Anna Sеrgееvna Kasatkina
Lecturer, Department of Economics and Information Technology,
RANEPA (west branch)
kasatkina_ana@mail.ru
Artilleriyskaya St., 18, 236016 Kaliningrad, Russian Federation
Abstract. The theory of codes derived from algebraic curves was initiated
by the works of V.D. Goppa. Since that time this theory has received an active
development. Construction of certain classes of codes is based on the curves with
sufficient number of rational points. In this paper we study curves arising from
the subcode of low weight of a rational Goppa code.
According to algorithm of construction, first of all, it is necessary to
represent subcode of low weight as a trace code. Let  (, ∞ ) be a rational
Goppa code over  with parameters [n, k] and let  denote the -dimensional
subcode of this code such that
|( )| =  ( (, ∞ )).
We need to represent subcode of low weight as follows
{︀
}︀
TrCon() ( ) = TrCon() () | ∈  =  ,
where  is -dimensional  -vector space and Tr is trace map
Tr :  →  .
Vector space  can be constructed in the following way. Let {1 , ...,  } be
a basis of subcode of low weight of a rational Goppa code. Elements 1 , ..., 
correspond to elements of basis and can be constructed as
−1
∑︁
 () = (

() )−1  −
=0

∑︁
α (

∑︁
−1
∑︁
α α (
̸=
−2

() )−2  +
=0
=1
+
· · · + (−1)
−1
∑︁

() )−3  −
=0

∑︁
α1 · . . . · α−2

() +
=0
1 <...<−2
+ (−1)−1
−1
∑︁

∑︁
α1 · . . . · α−1  + (−1) α .
1 <...<−1
82
Ю.С. Касаткина, А.С. Касаткина. О конструкции кривой, соответствующей подкоду
МАТЕМАТИКА
Thus we obtain 1 , ... ∈  () such that TrCon() ( ) =  , 1 ≤  ≤ ,
where {1 , ...,  } is a basis of  .
We denote  = ⟨1 , . . . ,  ⟩. Then  is -dimensional  -vector space and
TrCon() ( ) =  .
Let  be the function field of curve  , corresponding to the subcode of
low weight  . So, the curve over field  corresponds to the subcode of low
weight. The equation of this curve is

 −  =
 ∑︁
−1
∑︁

α−1  .
=1 =0
Key words: geometric Goppa code, generalized Hemming weight of the
code, subcode of low weight, algebraic curve, algorithm for constructing a curve.
ISSN 2222-8896. Вестн. Волгогр. гос. ун-та. Сер. 1, Мат. Физ. 2016. № 4 (35)
83
Документ
Категория
Без категории
Просмотров
9
Размер файла
352 Кб
Теги
рационального, соответствующего, наименьшего, веса, конструкции, подкоду, кривой, гоппы, кода
1/--страниц
Пожаловаться на содержимое документа