高次の座を用いた代数幾何符号の構成 On Constructio

高次の座を用いた代数幾何符号の構成
On Construction of Algebraic Geometric Codes
with High Degree Places
(Update : 2001.02.02)
戒田高康 (Takayasu KAIDA)
八代工業高等専門学校情報電子工学科
Dept. of Information and Electronic Engineering,
Yatsushiro National College of Technology
Outline of the Presentation
• Background and preparations
• Code with high degree places by Xing, et.al.
• Function type code and residue type code
with high degree places
• Relation between Xing’s code and proposed code
• Decoding for proposed code
• An example over an elliptic function field
• Conclusion and future works
Background
• Algebraic geometric (AG) code
– Its code length is restricted by Hasse-Weil bound
• AG code with high degree places
– C.Xing, H.Neidereiter and Y.K.Lam[2,3], 1999.
– T.Kaida, K.Imamura and T.Moriuchi[5,6],
Not only function type but also residue type, 1995~2000
• Relation of codes proposed in [1,2,3]
– One construction is new and interested[4], 1999
Preparations
[7]H.Stichtenoth, Algebraic Function Fields and Codes,
Springer-Verlag, 1993
K  Fq  GF (q)
F / K : an one variablealgebraic functionfield
overa full constantfield K
P : a placeover F / K , FP : the residue field of P,
deg P  m  FP  Fq m
Code Proposed by Xing, et.al.
P1 , P2 ,...,Pr : distinct places with ki  deg Pi for i  1,2,...,r
r
D   Pi , G : divisors with suppG  supp D  
i 1
 i : FP  Ci : an K - linear isomorphism to
i
[ni , ki , d i ] code Ci  K n for i  1,2,...,r
 L(G )  K n

r
 :
 f  ( 1 ( f ( P1 )),..., r ( f ( Pr ))), where n   ni
i 1

T hecode is defined by
C X ( D, G,  )  { ( f )  K n | f  L(G )}
Parameters of the code
r
If deg G   ki t henC X ( D, G,  ) is [ n, k , d ] code wit h
i 1
k  l (G )  deg G  1  g , d   ,


where X  S  {1,...,r}  ki  deg G 
iS




and   min d i S  X 
 iS

Function Type Code
Definit ion1 :
P : a placeover F / K wit h d  deg P
V  {V1 ,V2 ,, Vd } : a basis of FP over K
FP  K d : f ( P)  ( f1 , f 2 , , f d )
such t hat
f ( P)  f1V1  f 2V2    f dVd ,
f j  K for j  1,2,  d
(1)
Function Type Code
Definit ion2 :
P1 , P2 ,  , Pr : r dist inct placesover F / K
wit h d i  deg Pi for i  1,2,  , r
D, G : divisors over F / K such t hat
r
D   Pi , supp G  supp D  Ø
i 1
V ( i ) : a basis of FPi over K for i  1,2,  , r
Vˆ  {V ( 1 ) , V ( 2 ) ,  , V ( r ) } : a basis set
Funct ion t ype of code is defined by
C L ( D, G , Vˆ )  {( f ( P1 ), f ( P2 ),  , f ( Pr )) | f  L(G )} (2)
Residue Type Code
Definition３ :
 : a different al
i module over F / K
P : a placeover F / K with d  deg P
V  {V1 ,V2 , , Vd } : a basis of FP over K
F ' / K ': algebraic funct ionfield such t hat
F '  FK ' and K ': the d - th ext ensionfield
P1 , P2 ,, Pd : r distinct placesover F ' / K ' such t hat
Pi  P, deg Pi  1 for i  1,2,, d
Re sidue map is defined by
Res P ( )  {e1 , e2 ,, ed },
for j  1,2, , d
d
e j   V j ( Pi ) Res Pi ( )
i 1
(3)
Residue Type Code
Lemma４ : T heresidue map of P over F / K
with d  deg P is themap from Ω to K
d
Definition5 :
divisors D, G and basis set Vˆ are setting
the same as Definition1 & 2
Re sidue typecode is defined by
C ( D, G,Vˆ )  {(Res ( ), , Res ( ) |   (G  D)}(4)

P1
Pr
Duality of Function and Residue Code
Definition6 :
K ': an exitensionfield of K , F ' / K ': F '  FK '
P : a placeover F / K
T heconormof P is defined by
ConF '/ F ( P) 
 P',
P ' P
where thesum runs overall places P' over F ' / K '
such thatP'  P
T heconormof D   nP P is defined by
ConF '/ F ( D)   nP ConF '/ F ( P)
Duality of Function and Residue Code
T heorem7 :
T hefuntion type code, C L ( D, G,Vˆ ), is thedual
code of theresidue typecode, C ( D, G,Vˆ )

(Proof): d  LCN (d1 , d 2 ,, d r ), K '  Fq d , F '  FK '
r
di
D'  ConF '/ F (D)   Pij , G '  ConF '/ F (G)
i 1 j 1
CL ( D' , G ' ,Vˆ ) with Vˆ  {{1}, {1}, ,{1}} is
convention
al AG code C L ( D' , G ' ) over K '
Duality of Function and Residue Code
(P roof)
For i  1,2,  , r
V1(i ) ( Pi1 )  V1(i ) ( Pidi )


Ti   

 Vd(i ) ( Pi1 )  Vd(i ) ( Pid )
i
i 
 i
non - singular mat rix
0
T1
 T  


 0
Tr 
Duality of Function and Residue Code
(P roof)
G ' L : generat ormat rixof C L ( D' , G ' )
H ' L : check mat rixof C L ( D ' , G ' )
GL : generat ormat rixof C L ( D, G , Vˆ )
G : generat ormat ixof C ( D, G , Vˆ )


G ' L  GLT ,

t
 H ' L T  G ,
where T t : t he t ransposit ion mat rixof T
G ' L ( H ' L ) t  0  GL (G ) t  0
□
Relation of CX and CL
 : [ki , ki , d i ] code Ci for i  1,2,...,r
 C L ( D, G, Vˆ )  C X ( D, G,  )
※ C L is a specialcase of C X
Decoding for Proposed Codes
• By generator matrix of the dual code
• In extension field by
 
t
G '  GLT or H'  G T 1 ,
0
T1
　where non - singular mat rixT  

,
 0
Tr 
V1( i ) ( Pi1 )  V1( i ) ( Pidi )


Ti  


 for i  1,2,  , r　Vd( i ) ( Pi1 )  Vd( i ) ( Pid )
i
i 
 i
An Example
Example8 :
K  GF (2) , F  K ( x, y ) such that y 3  y  x 2  1  0
F / K : an ellipticfunctionfield
5
Let D   Pi , G  6Q and Vˆ  {{1}, {1}, {1, x}, {1, x}, {1, x, y}}
i 1
L (G )  1, x, y, x 2 , xy, y 2
dx
dx
dx
(G  D) 
, 2
,
2
2
( x  1)(x  x  1) ( x  x  1)(x  y ) y ( x 2  y )
An Example (Ex. 8)
Table 1. Places over F/K with deg≦3 and
local parameters (LP) over F, K(x) and K(y)
Pi
Q
P1
P2
P3
P4
P5
P6
P7
deg
1
1
1
2
2
3
2
3
LP of K(x,y)
y/x
x+1, y
x+1, x2+y
x2+x+1, y
x2+x+1, y+1
x2+y
x
x2+y+1
LP of K(x)
1/x
x+1
x+1
x2+x+1
x2+x+1
x3+x+1
x
x3+x+1
LP of K(y)
1/y
y+1
y+1
y
y+1
y3+y+1
y2+y+1
y3+y2+1
An Example
Example8 :
K '  GF (2 ), F '  FK '
since d1  d 2  1, d 3  d 4  2, d 5  3
6
5
di
D'   Pij , G '  ConF '/ F (G )  6Q
i 1 j 1
  GF(2 ),     1  0
2
2
  GF (2 ),    1  0
6
3
An Example (Ex.8)
Table 2. Places over F’/K’ with deg=1 and their LP
Pij
LP of F’/K’
P11 x+1, y
P41
x+, y+1
P21 x+1, y+1
P42
x+2, y+1
P31 x+, y
P51
x+, y+ 2
P32 x+2, y
P52
x+ 2, y+4
P53
x+4 , y+
Pij
LP of F’/K’
An Example
Example8 :
111010100

110101010



111010000

010010001

011011100

GL  
,
G





111111001


111000101

010011110



010010011

From all code words
C ( D, G , Vˆ ) : (9,6,1) binary code
L
C ( D, G , Vˆ ) : (9,3,3) binary code
Conclusion
• The definition of codes with high degree places
– by Xing, et.al. (function type)
– function type and residue type
• The duality of function and residue type code
• Function type is a special case of Xing’s code
• An example over an elliptic function field
Future Works
• Residue type of Xing’s code
• Theoretical evaluation for the minimum
distance of proposed code
• Decoding method of proposed code
• Relation between proposed code and
conventional codes (AG code, sub-field subcode, concatenated code)
References
[1]C.Xing, H.Niederreiter and K.Y.Lam, “Constructions of algebraic-geometry
codes”, IEEE Trans. Information Theory, vol.45, pp.1186-1193, May 1999.
[2] H.Niederreiter, C.Xing and K.Y.Lam, “A new construction of algebraicgeometry codes”, Applicable Algebra in Engineering, Communication and
Computing, vol.9, pp.373-381, Springer-Verlag, 1999.
[3] C.Xing, H.Niederreiter and K.Y.Lam, “A generalization of algebraicgeometry codes”, IEEE Trans. Information Theory, vol.45, pp.2498-2501,
Nov. 1999.
[4]F.Ozbudak and H.Stichtenoth, “Constructing codes from algebraic curves”,
IEEE Trans. Information Theory, vol.45, pp.2502-2505, Nov. 1999.
[5]戒田高康, 今村恭己, 森内勉, “高次の座を用いた代数幾何符号に関する
考察”, 第18回情報理論とその応用シンポジウム予稿集, pp.231-234, 花
巻, 1995年10月
[6]T.Kaida and K. Imamura, “Residue type of algebraic geometric codes with
high degree places”, Proc. Of International Symposium on Information
Theory and Its Applications, pp.453-456, Honolulu, Nov. 2000.
[7]H.Stichtenoth, Algebraic Function Fields and Codes, Springer-Verlag, 1993.

Download Report