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