Home Online Manual
Top
Back: Solving systems of polynomial equations
Forward: Polynomial data
FastBack: Non-commutative Algebra
FastForward: Polynomial data
Up: Applications
Top: Singular Manual
Contents: Table of Contents
Index: Index
About: About this document

A.7.2 AG codes

The library brnoeth.lib provides an implementation of the Brill-Noether algorithm for solving the Riemann-Roch problem and applications to Algebraic Geometry codes. The procedures can be applied to plane (singular) curves defined over a prime field of positive characteristic.

 
LIB "brnoeth.lib";
ring s=2,(x,y),lp;            // characteristic 2
poly f=x3y+y3+x;              // the Klein quartic
list KLEIN=Adj_div(f);        // compute the conductor
==> Computing affine singular points ... 
==> Computing all points at infinity ... 
==> Computing affine singular places ... 
==> Computing singular places at infinity ... 
==> Computing non-singular places at infinity ... 
==> Adjunction divisor computed successfully
==>  
==> The genus of the curve is 3
KLEIN=NSplaces(1..3,KLEIN);   // computes places up to degree 3
==> Computing non-singular affine places of degree 1 ... 
==> Computing non-singular affine places of degree 2 ... 
==> Computing non-singular affine places of degree 3 ... 
KLEIN=extcurve(3,KLEIN);      // construct Klein quartic over F_8
==> 
==> Total number of rational places : NrRatPl = 24
==> 
KLEIN[3];                     // display places (degree, number)
==> [1]:
==>    1,1
==> [2]:
==>    1,2
==> [3]:
==>    1,3
==> [4]:
==>    2,1
==> [5]:
==>    3,1
==> [6]:
==>    3,2
==> [7]:
==>    3,3
==> [8]:
==>    3,4
==> [9]:
==>    3,5
==> [10]:
==>    3,6
==> [11]:
==>    3,7
// We define a divisor G of degree 14=6*1+4*2:
intvec G=6,0,0,4,0,0,0,0,0,0,0;   // 6 * place #1 + 4 * place #4
// We compute an evaluation code which evaluates at all rational places
// outside the support of G (place #4 is not rational)
intvec D=2..24;
// in D, the number i refers to the i-th element of the list POINTS in
// the ring KLEIN[1][5].
def RR=KLEIN[1][5];
setring RR; POINTS[1];        // the place in the support of G (not in supp(D))
==> [1]:
==>    0
==> [2]:
==>    1
==> [3]:
==>    0
setring s;
def RR=KLEIN[1][4];
==> // ** redefining RR **
setring RR;
matrix C=AGcode_L(G,D,KLEIN); // generator matrix for the evaluation AG code
==> Forms of degree 5 : 
==> 21
==>  
==> Vector basis successfully computed 
==>  
nrows(C);
==> 12
ncols(C);
==> 23
//
// We can also compute a generator matrix for the residual AG code
matrix CO=AGcode_Omega(G,D,KLEIN);
==> Forms of degree 5 : 
==> 21
==>  
==> Vector basis successfully computed 
==>  
//
// Preparation for decoding:
// We need a divisor of degree at least 6 whose support is disjoint with the
// support of D:
intvec F=6;                   // F = 6*point #1
// in F, the i-th entry refers to the i-th element of the list POINTS in
// the ring KLEIN[1][5]
list K=prepSV(G,D,F,KLEIN);
==> Forms of degree 5 : 
==> 21
==>  
==> Vector basis successfully computed 
==>  
==> Forms of degree 4 : 
==> 15
==>  
==> Vector basis successfully computed 
==>  
==> Forms of degree 4 : 
==> 15
==>  
==> Vector basis successfully computed 
==>  
K[size(K)][1];                // error-correcting capacity
==> 3
//
//  Encoding and Decoding:
matrix word[1][11];           // a word of length 11 is encoded
word = 1,1,1,1,1,1,1,1,1,1,1;
def y=word*CO;                // the code word (length: 23)
matrix disturb[1][23];
disturb[1,1]=1;
disturb[1,10]=a;
disturb[1,12]=1+a;
y=y+disturb;                  // disturb the code word (3 errors)
def yy=decodeSV(y,K);         // error correction
yy-y;                         // display the error
==> _[1,1]=1
==> _[1,2]=0
==> _[1,3]=0
==> _[1,4]=0
==> _[1,5]=0
==> _[1,6]=0
==> _[1,7]=0
==> _[1,8]=0
==> _[1,9]=0
==> _[1,10]=(a)
==> _[1,11]=0
==> _[1,12]=(a+1)
==> _[1,13]=0
==> _[1,14]=0
==> _[1,15]=0
==> _[1,16]=0
==> _[1,17]=0
==> _[1,18]=0
==> _[1,19]=0
==> _[1,20]=0
==> _[1,21]=0
==> _[1,22]=0
==> _[1,23]=0