[1X5. Generating Codes[0X In this chapter we describe functions for generating codes. Section [14X5.1[0X describes functions for generating unrestricted codes. Section [14X5.2[0X describes functions for generating linear codes. Section [14X5.3[0X describes functions for constructing certain covering codes, such as the Gabidulin codes. Section [14X5.4[0X describes functions for constructing the Golay codes. Section [14X5.5[0X describes functions for generating cyclic codes. Section [14X5.6[0X describes functions for generating codes as the image of an evaluation map applied to a space of functions. For example, generalized Reed-Solomon codes and toric codes are described there. Section [14X5.7[0X describes functions for generating algebraic geometry codes. Section [14X5.8[0X describes functions for constructing low-density parity-check (LDPC) codes. [1X5.1 Generating Unrestricted Codes[0X In this section we start with functions that creating code from user defined matrices or special matrices (see [2XElementsCode[0X ([14X5.1-1[0X), [2XHadamardCode[0X ([14X5.1-2[0X), [2XConferenceCode[0X ([14X5.1-3[0X) and [2XMOLSCode[0X ([14X5.1-4[0X)). These codes are unrestricted codes; they may later be discovered to be linear or cyclic. The next functions generate random codes (see [2XRandomCode[0X ([14X5.1-5[0X)) and the Nordstrom-Robinson code (see [2XNordstromRobinsonCode[0X ([14X5.1-6[0X)), respectively. Finally, we describe two functions for generating Greedy codes. These are codes that contructed by gathering codewords from a space (see [2XGreedyCode[0X ([14X5.1-7[0X) and [2XLexiCode[0X ([14X5.1-8[0X)). [1X5.1-1 ElementsCode[0X [2X> ElementsCode( [0X[3XL[, name], F[0X[2X ) _____________________________________[0Xfunction [10XElementsCode[0X creates an unrestricted code of the list of elements [3XL[0X, in the field [3XF[0X. [3XL[0X must be a list of vectors, strings, polynomials or codewords. [3Xname[0X can contain a short description of the code. If [3XL[0X contains a codeword more than once, it is removed from the list and a GAP set is returned. [4X--------------------------- Example ----------------------------[0X [4Xgap> M := Z(3)^0 * [ [1, 0, 1, 1], [2, 2, 0, 0], [0, 1, 2, 2] ];;[0X [4Xgap> C := ElementsCode( M, "example code", GF(3) );[0X [4Xa (4,3,1..4)2 example code over GF(3)[0X [4Xgap> MinimumDistance( C );[0X [4X4[0X [4Xgap> AsSSortedList( C );[0X [4X[ [ 0 1 2 2 ], [ 1 0 1 1 ], [ 2 2 0 0 ] ][0X [4X------------------------------------------------------------------[0X [1X5.1-2 HadamardCode[0X [2X> HadamardCode( [0X[3XH[, t][0X[2X ) ___________________________________________[0Xfunction The four forms this command can take are [10XHadamardCode(H,t)[0X, [10XHadamardCode(H)[0X, [10XHadamardCode(n,t)[0X, and [10XHadamardCode(n)[0X. In the case when the arguments [3XH[0X and [3Xt[0X are both given, [10XHadamardCode[0X returns a Hadamard code of the t^th kind from the Hadamard matrix [3XH[0X In case only [3XH[0X is given, t = 3 is used. By definition, a Hadamard matrix is a square matrix [3XH[0X with H* H^T = -n* I_n, where n is the size of [3XH[0X. The entries of [3XH[0X are either 1 or -1. The matrix [3XH[0X is first transformed into a binary matrix A_n by replacing the 1's by 0's and the -1's by 1s). The Hadamard matrix of the [13Xfirst kind[0X (t=1) is created by using the rows of A_n as elements, after deleting the first column. This is a (n-1, n, n/2) code. We use this code for creating the Hadamard code of the [13Xsecond kind[0X (t=2), by adding all the complements of the already existing codewords. This results in a (n-1, 2n, n/2 -1) code. The [13Xthird kind[0X (t=3) is created by using the rows of A_n (without cutting a column) and their complements as elements. This way, we have an (n, 2n, n/2)-code. The returned code is generally an unrestricted code, but for n = 2^r, the code is linear. The command [10XHadamardCode(n,t)[0X returns a Hadamard code with parameter [3Xn[0X of the t^th kind. For the command [10XHadamardCode(n)[0X, t=3 is used. When called in these forms, [10XHadamardCode[0X first creates a Hadamard matrix (see [2XHadamardMat[0X ([14X7.3-4[0X)), of size [3Xn[0X and then follows the same procedure as described above. Therefore the same restrictions with respect to [3Xn[0X as for Hadamard matrices hold. [4X--------------------------- Example ----------------------------[0X [4Xgap> H4 := [[1,1,1,1],[1,-1,1,-1],[1,1,-1,-1],[1,-1,-1,1]];;[0X [4Xgap> HadamardCode( H4, 1 );[0X [4Xa (3,4,2)1 Hadamard code of order 4 over GF(2)[0X [4Xgap> HadamardCode( H4, 2 );[0X [4Xa (3,8,1)0 Hadamard code of order 4 over GF(2)[0X [4Xgap> HadamardCode( H4 );[0X [4Xa (4,8,2)1 Hadamard code of order 4 over GF(2) [0X [4Xgap> H4 := [[1,1,1,1],[1,-1,1,-1],[1,1,-1,-1],[1,-1,-1,1]];;[0X [4Xgap> C := HadamardCode( 4 );[0X [4Xa (4,8,2)1 Hadamard code of order 4 over GF(2)[0X [4Xgap> C = HadamardCode( H4 );[0X [4Xtrue [0X [4X------------------------------------------------------------------[0X [1X5.1-3 ConferenceCode[0X [2X> ConferenceCode( [0X[3XH[0X[2X ) ______________________________________________[0Xfunction [10XConferenceCode[0X returns a code of length n-1 constructed from a symmetric 'conference matrix' [3XH[0X. A [13Xconference matrix[0X [3XH[0X is a symmetric matrix of order n, which satisfies H* H^T = ((n-1)* I, with n = 2 mod 4. The rows of frac12(H+I+J), frac12(-H+I+J), plus the zero and all-ones vectors form the elements of a binary non-linear (n-1, 2n, (n-2)/2) code. [5XGUAVA[0X constructs a symmetric conference matrix of order n+1 (n= 1 mod 4) and uses the rows of that matrix, plus the zero and all-ones vectors, to construct a binary non-linear (n, 2(n+1), (n-1)/2)-code. [4X--------------------------- Example ----------------------------[0X [4Xgap> H6 := [[0,1,1,1,1,1],[1,0,1,-1,-1,1],[1,1,0,1,-1,-1],[0X [4X> [1,-1,1,0,1,-1],[1,-1,-1,1,0,1],[1,1,-1,-1,1,0]];;[0X [4Xgap> C1 := ConferenceCode( H6 );[0X [4Xa (5,12,2)1..4 conference code over GF(2)[0X [4Xgap> IsLinearCode( C1 );[0X [4Xfalse [0X [4Xgap> C2 := ConferenceCode( 5 );[0X [4Xa (5,12,2)1..4 conference code over GF(2)[0X [4Xgap> AsSSortedList( C2 );[0X [4X[ [ 0 0 0 0 0 ], [ 0 0 1 1 1 ], [ 0 1 0 1 1 ], [ 0 1 1 0 1 ], [ 0 1 1 1 0 ], [0X [4X [ 1 0 0 1 1 ], [ 1 0 1 0 1 ], [ 1 0 1 1 0 ], [ 1 1 0 0 1 ], [ 1 1 0 1 0 ], [0X [4X [ 1 1 1 0 0 ], [ 1 1 1 1 1 ] ][0X [4X------------------------------------------------------------------[0X [1X5.1-4 MOLSCode[0X [2X> MOLSCode( [0X[3X[n][,]q[0X[2X ) ______________________________________________[0Xfunction [10XMOLSCode[0X returns an (n, q^2, n-1) code over GF(q). The code is created from n-2 'Mutually Orthogonal Latin Squares' (MOLS) of size q x q. The default for [3Xn[0X is 4. [5XGUAVA[0X can construct a MOLS code for n-2 <= q. Here [3Xq[0X must be a prime power, q > 2. If there are no n-2 MOLS, an error is signalled. Since each of the n-2 MOLS is a qx q matrix, we can create a code of size q^2 by listing in each code element the entries that are in the same position in each of the MOLS. We precede each of these lists with the two coordinates that specify this position, making the word length become n. The MOLS codes are MDS codes (see [2XIsMDSCode[0X ([14X4.3-7[0X)). [4X--------------------------- Example ----------------------------[0X [4Xgap> C1 := MOLSCode( 6, 5 );[0X [4Xa (6,25,5)3..4 code generated by 4 MOLS of order 5 over GF(5)[0X [4Xgap> mols := List( [1 .. WordLength(C1) - 2 ], function( nr )[0X [4X> local ls, el;[0X [4X> ls := NullMat( Size(LeftActingDomain(C1)), Size(LeftActingDomain(C1)) );[0X [4X> for el in VectorCodeword( AsSSortedList( C1 ) ) do[0X [4X> ls[IntFFE(el[1])+1][IntFFE(el[2])+1] := el[nr + 2];[0X [4X> od;[0X [4X> return ls;[0X [4X> end );;[0X [4Xgap> AreMOLS( mols );[0X [4Xtrue[0X [4Xgap> C2 := MOLSCode( 11 );[0X [4Xa (4,121,3)2 code generated by 2 MOLS of order 11 over GF(11) [0X [4X------------------------------------------------------------------[0X [1X5.1-5 RandomCode[0X [2X> RandomCode( [0X[3Xn, M, F[0X[2X ) ____________________________________________[0Xfunction [10XRandomCode[0X returns a random unrestricted code of size [3XM[0X with word length [3Xn[0X over [3XF[0X. [3XM[0X must be less than or equal to the number of elements in the space GF(q)^n. The function [10XRandomLinearCode[0X returns a random linear code (see [2XRandomLinearCode[0X ([14X5.2-12[0X)). [4X--------------------------- Example ----------------------------[0X [4Xgap> C1 := RandomCode( 6, 10, GF(8) );[0X [4Xa (6,10,1..6)4..6 random unrestricted code over GF(8)[0X [4Xgap> MinimumDistance(C1);[0X [4X3[0X [4Xgap> C2 := RandomCode( 6, 10, GF(8) );[0X [4Xa (6,10,1..6)4..6 random unrestricted code over GF(8)[0X [4Xgap> C1 = C2;[0X [4Xfalse [0X [4X------------------------------------------------------------------[0X [1X5.1-6 NordstromRobinsonCode[0X [2X> NordstromRobinsonCode( [0X[3X[0X[2X ) ________________________________________[0Xfunction [10XNordstromRobinsonCode[0X returns a Nordstrom-Robinson code, the best code with word length n=16 and minimum distance d=6 over GF(2). This is a non-linear (16, 256, 6) code. [4X--------------------------- Example ----------------------------[0X [4Xgap> C := NordstromRobinsonCode();[0X [4Xa (16,256,6)4 Nordstrom-Robinson code over GF(2)[0X [4Xgap> OptimalityCode( C );[0X [4X0 [0X [4X------------------------------------------------------------------[0X [1X5.1-7 GreedyCode[0X [2X> GreedyCode( [0X[3XL, d, F[0X[2X ) ____________________________________________[0Xfunction [10XGreedyCode[0X returns a Greedy code with design distance [3Xd[0X over the finite field [3XF[0X. The code is constructed using the greedy algorithm on the list of vectors [3XL[0X. (The greedy algorithm checks each vector in [3XL[0X and adds it to the code if its distance to the current code is greater than or equal to [3Xd[0X. It is obvious that the resulting code has a minimum distance of at least [3Xd[0X. Greedy codes are often linear codes. The function [10XLexiCode[0X creates a greedy code from a basis instead of an enumerated list (see [2XLexiCode[0X ([14X5.1-8[0X)). [4X--------------------------- Example ----------------------------[0X [4Xgap> C1 := GreedyCode( Tuples( AsSSortedList( GF(2) ), 5 ), 3, GF(2) );[0X [4Xa (5,4,3..5)2 Greedy code, user defined basis over GF(2)[0X [4Xgap> C2 := GreedyCode( Permuted( Tuples( AsSSortedList( GF(2) ), 5 ),[0X [4X> (1,4) ), 3, GF(2) );[0X [4Xa (5,4,3..5)2 Greedy code, user defined basis over GF(2)[0X [4Xgap> C1 = C2;[0X [4Xfalse [0X [4X------------------------------------------------------------------[0X [1X5.1-8 LexiCode[0X [2X> LexiCode( [0X[3Xn, d, F[0X[2X ) ______________________________________________[0Xfunction In this format, [10XLexicode[0X returns a lexicode with word length [3Xn[0X, design distance [3Xd[0X over [3XF[0X. The code is constructed using the greedy algorithm on the lexicographically ordered list of all vectors of length [3Xn[0X over [3XF[0X. Every time a vector is found that has a distance to the current code of at least [3Xd[0X, it is added to the code. This results, obviously, in a code with minimum distance greater than or equal to [3Xd[0X. Another syntax which one can use is [10XLexiCode( B, d, F )[0X. When called in this format, [10XLexiCode[0X uses the basis [3XB[0X instead of the standard basis. [3XB[0X is a matrix of vectors over [3XF[0X. The code is constructed using the greedy algorithm on the list of vectors spanned by [3XB[0X, ordered lexicographically with respect to [3XB[0X. Note that binary lexicodes are always linear. [4X--------------------------- Example ----------------------------[0X [4Xgap> C := LexiCode( 4, 3, GF(5) );[0X [4Xa (4,17,3..4)2..4 lexicode over GF(5) [0X [4Xgap> B := [ [Z(2)^0, 0*Z(2), 0*Z(2)], [Z(2)^0, Z(2)^0, 0*Z(2)] ];;[0X [4Xgap> C := LexiCode( B, 2, GF(2) );[0X [4Xa linear [3,1,2]1..2 lexicode over GF(2) [0X [4X------------------------------------------------------------------[0X The function [10XGreedyCode[0X creates a greedy code that is not restricted to a lexicographical order (see [2XGreedyCode[0X ([14X5.1-7[0X)). [1X5.2 Generating Linear Codes[0X In this section we describe functions for constructing linear codes. A linear code always has a generator or check matrix. The first two functions generate linear codes from the generator matrix ([2XGeneratorMatCode[0X ([14X5.2-1[0X)) or check matrix ([2XCheckMatCode[0X ([14X5.2-3[0X)). All linear codes can be constructed with these functions. The next functions we describe generate some well-known codes, like Hamming codes ([2XHammingCode[0X ([14X5.2-4[0X)), Reed-Muller codes ([2XReedMullerCode[0X ([14X5.2-5[0X)) and the extended Golay codes ([2XExtendedBinaryGolayCode[0X ([14X5.4-2[0X) and [2XExtendedTernaryGolayCode[0X ([14X5.4-4[0X)). A large and powerful family of codes are alternant codes. They are obtained by a small modification of the parity check matrix of a BCH code (see [2XAlternantCode[0X ([14X5.2-6[0X), [2XGoppaCode[0X ([14X5.2-7[0X), [2XGeneralizedSrivastavaCode[0X ([14X5.2-8[0X) and [2XSrivastavaCode[0X ([14X5.2-9[0X)). Finally, we describe a function for generating random linear codes (see [2XRandomLinearCode[0X ([14X5.2-12[0X)). [1X5.2-1 GeneratorMatCode[0X [2X> GeneratorMatCode( [0X[3XG[, name], F[0X[2X ) _________________________________[0Xfunction [10XGeneratorMatCode[0X returns a linear code with generator matrix [3XG[0X. [3XG[0X must be a matrix over finite field [3XF[0X. [3Xname[0X can contain a short description of the code. The generator matrix is the basis of the elements of the code. The resulting code has word length n, dimension k if [3XG[0X is a k x n-matrix. If GF(q) is the field of the code, the size of the code will be q^k. If the generator matrix does not have full row rank, the linearly dependent rows are removed. This is done by the GAP function [10XBaseMat[0X and results in an equal code. The generator matrix can be retrieved with the function [10XGeneratorMat[0X (see [2XGeneratorMat[0X ([14X4.7-1[0X)). [4X--------------------------- Example ----------------------------[0X [4Xgap> G := Z(3)^0 * [[1,0,1,2,0],[0,1,2,1,1],[0,0,1,2,1]];;[0X [4Xgap> C1 := GeneratorMatCode( G, GF(3) );[0X [4Xa linear [5,3,1..2]1..2 code defined by generator matrix over GF(3)[0X [4Xgap> C2 := GeneratorMatCode( IdentityMat( 5, GF(2) ), GF(2) );[0X [4Xa linear [5,5,1]0 code defined by generator matrix over GF(2)[0X [4Xgap> GeneratorMatCode( List( AsSSortedList( NordstromRobinsonCode() ),[0X [4X> x -> VectorCodeword( x ) ), GF( 2 ) );[0X [4Xa linear [16,11,1..4]2 code defined by generator matrix over GF(2)[0X [4X# This is the smallest linear code that contains the N-R code [0X [4X------------------------------------------------------------------[0X [1X5.2-2 CheckMatCodeMutable[0X [2X> CheckMatCodeMutable( [0X[3XH[, name], F[0X[2X ) ______________________________[0Xfunction [10XCheckMatCodeMutable[0X is the same as [10XCheckMatCode[0X except that the check matrix and generator matrix are mutable. [1X5.2-3 CheckMatCode[0X [2X> CheckMatCode( [0X[3XH[, name], F[0X[2X ) _____________________________________[0Xfunction [10XCheckMatCode[0X returns a linear code with check matrix [3XH[0X. [3XH[0X must be a matrix over Galois field [3XF[0X. [3X[name.[0X can contain a short description of the code. The parity check matrix is the transposed of the nullmatrix of the generator matrix of the code. Therefore, c* H^T = 0 where c is an element of the code. If [3XH[0X is a rx n-matrix, the code has word length n, redundancy r and dimension n-r. If the check matrix does not have full row rank, the linearly dependent rows are removed. This is done by the GAP function [10XBaseMat[0X. and results in an equal code. The check matrix can be retrieved with the function [10XCheckMat[0X (see [2XCheckMat[0X ([14X4.7-2[0X)). [4X--------------------------- Example ----------------------------[0X [4Xgap> G := Z(3)^0 * [[1,0,1,2,0],[0,1,2,1,1],[0,0,1,2,1]];;[0X [4Xgap> C1 := CheckMatCode( G, GF(3) );[0X [4Xa linear [5,2,1..2]2..3 code defined by check matrix over GF(3)[0X [4Xgap> CheckMat(C1);[0X [4X[ [ Z(3)^0, 0*Z(3), Z(3)^0, Z(3), 0*Z(3) ],[0X [4X [ 0*Z(3), Z(3)^0, Z(3), Z(3)^0, Z(3)^0 ],[0X [4X [ 0*Z(3), 0*Z(3), Z(3)^0, Z(3), Z(3)^0 ] ][0X [4Xgap> C2 := CheckMatCode( IdentityMat( 5, GF(2) ), GF(2) );[0X [4Xa cyclic [5,0,5]5 code defined by check matrix over GF(2)[0X [4X------------------------------------------------------------------[0X [1X5.2-4 HammingCode[0X [2X> HammingCode( [0X[3Xr, F[0X[2X ) ______________________________________________[0Xfunction [10XHammingCode[0X returns a Hamming code with redundancy [3Xr[0X over [3XF[0X. A Hamming code is a single-error-correcting code. The parity check matrix of a Hamming code has all nonzero vectors of length [3Xr[0X in its columns, except for a multiplication factor. The decoding algorithm of the Hamming code (see [2XDecode[0X ([14X4.10-1[0X)) makes use of this property. If q is the size of its field [3XF[0X, the returned Hamming code is a linear [(q^r-1)/(q-1), (q^r-1)/(q-1) - r, 3] code. [4X--------------------------- Example ----------------------------[0X [4Xgap> C1 := HammingCode( 4, GF(2) );[0X [4Xa linear [15,11,3]1 Hamming (4,2) code over GF(2)[0X [4Xgap> C2 := HammingCode( 3, GF(9) );[0X [4Xa linear [91,88,3]1 Hamming (3,9) code over GF(9) [0X [4X------------------------------------------------------------------[0X [1X5.2-5 ReedMullerCode[0X [2X> ReedMullerCode( [0X[3Xr, k[0X[2X ) ___________________________________________[0Xfunction [10XReedMullerCode[0X returns a binary 'Reed-Muller code' [3XR(r, k)[0X with dimension [3Xk[0X and order [3Xr[0X. This is a code with length 2^k and minimum distance 2^k-r (see for example, section 1.10 in [HP03]). By definition, the r^th order binary Reed-Muller code of length n=2^m, for 0 <= r <= m, is the set of all vectors f, where f is a Boolean function which is a polynomial of degree at most r. [4X--------------------------- Example ----------------------------[0X [4Xgap> ReedMullerCode( 1, 3 );[0X [4Xa linear [8,4,4]2 Reed-Muller (1,3) code over GF(2) [0X [4X------------------------------------------------------------------[0X See [2XGeneralizedReedMullerCode[0X ([14X5.6-3[0X) for a more general construction. [1X5.2-6 AlternantCode[0X [2X> AlternantCode( [0X[3Xr, Y[, alpha], F[0X[2X ) ________________________________[0Xfunction [10XAlternantCode[0X returns an 'alternant code', with parameters [3Xr[0X, [3XY[0X and [3Xalpha[0X (optional). [3XF[0X denotes the (finite) base field. Here, [3Xr[0X is the design redundancy of the code. [3XY[0X and [3Xalpha[0X are both vectors of length [3Xn[0X from which the parity check matrix is constructed. The check matrix has the form H=([a_i^j y_i]), where 0 <= j<= r-1, 1 <= i<= n, and where [...] is as in [2XVerticalConversionFieldMat[0X ([14X7.3-9[0X)). If no [3Xalpha[0X is specified, the vector [1, a, a^2, .., a^n-1] is used, where a is a primitive element of a Galois field [3XF[0X. [4X--------------------------- Example ----------------------------[0X [4Xgap> Y := [ 1, 1, 1, 1, 1, 1, 1];; a := PrimitiveUnityRoot( 2, 7 );;[0X [4Xgap> alpha := List( [0..6], i -> a^i );;[0X [4Xgap> C := AlternantCode( 2, Y, alpha, GF(8) );[0X [4Xa linear [7,3,3..4]3..4 alternant code over GF(8) [0X [4X------------------------------------------------------------------[0X [1X5.2-7 GoppaCode[0X [2X> GoppaCode( [0X[3XG, L[0X[2X ) ________________________________________________[0Xfunction [10XGoppaCode[0X returns a Goppa code [3XC[0X from Goppa polynomial [3Xg[0X, having coefficients in a Galois Field GF(q). [3XL[0X must be a list of elements in GF(q), that are not roots of [3Xg[0X. The word length of the code is equal to the length of [3XL[0X. The parity check matrix has the form H=([a_i^j / G(a_i)])_0 <= j <= deg(g)-1, a_i in L, where a_iin L and [...] is as in [2XVerticalConversionFieldMat[0X ([14X7.3-9[0X), so H has entries in GF(q), q=p^m. It is known that d(C)>= deg(g)+1, with a better bound in the binary case provided g has no multiple roots. See Huffman and Pless [HP03] section 13.2.2, and MacWilliams and Sloane [MS83] section 12.3, for more details. One can also call [10XGoppaCode[0X using the syntax [10XGoppaCode(g,n)[0X. When called with parameter [3Xn[0X, [5XGUAVA[0X constructs a list L of length [3Xn[0X, such that no element of [3XL[0X is a root of [3Xg[0X. This is a special case of an alternant code. [4X--------------------------- Example ----------------------------[0X [4Xgap> x:=Indeterminate(GF(8),"x");[0X [4Xx[0X [4Xgap> L:=Elements(GF(8));[0X [4X[ 0*Z(2), Z(2)^0, Z(2^3), Z(2^3)^2, Z(2^3)^3, Z(2^3)^4, Z(2^3)^5, Z(2^3)^6 ][0X [4Xgap> g:=x^2+x+1;[0X [4Xx^2+x+Z(2)^0[0X [4Xgap> C:=GoppaCode(g,L);[0X [4Xa linear [8,2,5]3 Goppa code over GF(2)[0X [4Xgap> xx := Indeterminate( GF(2), "xx" );; [0X [4Xgap> gg := xx^2 + xx + 1;; L := AsSSortedList( GF(8) );;[0X [4Xgap> C1 := GoppaCode( gg, L );[0X [4Xa linear [8,2,5]3 Goppa code over GF(2) [0X [4Xgap> y := Indeterminate( GF(2), "y" );; [0X [4Xgap> h := y^2 + y + 1;;[0X [4Xgap> C2 := GoppaCode( h, 8 );[0X [4Xa linear [8,2,5]3 Goppa code over GF(2) [0X [4Xgap> C1=C2;[0X [4Xtrue[0X [4Xgap> C=C1;[0X [4Xtrue[0X [4X------------------------------------------------------------------[0X [1X5.2-8 GeneralizedSrivastavaCode[0X [2X> GeneralizedSrivastavaCode( [0X[3Xa, w, z[, t], F[0X[2X ) _____________________[0Xfunction [10XGeneralizedSrivastavaCode[0X returns a generalized Srivastava code with parameters [3Xa[0X, [3Xw[0X, [3Xz[0X, [3Xt[0X. a = a_1, ..., a_n and w = w_1, ..., w_s are lists of n+s distinct elements of F=GF(q^m), z is a list of length n of nonzero elements of GF(q^m). The parameter [3Xt[0X determines the designed distance: d >= st + 1. The check matrix of this code is the form H=([\frac{z_i}{(a_i - w_j)^k}]), 1<= k<= t, where [...] is as in [2XVerticalConversionFieldMat[0X ([14X7.3-9[0X). We use this definition of H to define the code. The default for [3Xt[0X is 1. The original Srivastava codes (see [2XSrivastavaCode[0X ([14X5.2-9[0X)) are a special case t=1, z_i=a_i^mu, for some mu. [4X--------------------------- Example ----------------------------[0X [4Xgap> a := Filtered( AsSSortedList( GF(2^6) ), e -> e in GF(2^3) );;[0X [4Xgap> w := [ Z(2^6) ];; z := List( [1..8], e -> 1 );;[0X [4Xgap> C := GeneralizedSrivastavaCode( a, w, z, 1, GF(64) );[0X [4Xa linear [8,2,2..5]3..4 generalized Srivastava code over GF(2) [0X [4X------------------------------------------------------------------[0X [1X5.2-9 SrivastavaCode[0X [2X> SrivastavaCode( [0X[3Xa, w[, mu], F[0X[2X ) __________________________________[0Xfunction SrivastavaCode returns a Srivastava code with parameters [3Xa[0X, [3Xw[0X (and optionally [3Xmu[0X). a = a_1, ..., a_n and w = w_1, ..., w_s are lists of n+s distinct elements of F=GF(q^m). The default for [3Xmu[0X is 1. The Srivastava code is a generalized Srivastava code, in which z_i = a_i^mu for some [3Xmu[0X and t=1. J. N. Srivastava introduced this code in 1967, though his work was not published. See Helgert [Hel72] for more details on the properties of this code. Related reference: G. Roelofsen, [12XOn Goppa and Generalized Srivastava Codes[0X PhD thesis, Dept. Math. and Comp. Sci., Eindhoven Univ. of Technology, the Netherlands, 1982. [4X--------------------------- Example ----------------------------[0X [4Xgap> a := AsSSortedList( GF(11) ){[2..8]};;[0X [4Xgap> w := AsSSortedList( GF(11) ){[9..10]};;[0X [4Xgap> C := SrivastavaCode( a, w, 2, GF(11) );[0X [4Xa linear [7,5,3]2 Srivastava code over GF(11)[0X [4Xgap> IsMDSCode( C );[0X [4Xtrue # Always true if F is a prime field [0X [4X------------------------------------------------------------------[0X [1X5.2-10 CordaroWagnerCode[0X [2X> CordaroWagnerCode( [0X[3Xn[0X[2X ) ___________________________________________[0Xfunction [10XCordaroWagnerCode[0X returns a binary Cordaro-Wagner code. This is a code of length [3Xn[0X and dimension 2 having the best possible minimum distance d. This code is just a little bit less trivial than [10XRepetitionCode[0X (see [2XRepetitionCode[0X ([14X5.5-13[0X)). [4X--------------------------- Example ----------------------------[0X [4Xgap> C := CordaroWagnerCode( 11 );[0X [4Xa linear [11,2,7]5 Cordaro-Wagner code over GF(2)[0X [4Xgap> AsSSortedList(C); [0X [4X[ [ 0 0 0 0 0 0 0 0 0 0 0 ], [ 0 0 0 0 1 1 1 1 1 1 1 ], [0X [4X [ 1 1 1 1 0 0 0 1 1 1 1 ], [ 1 1 1 1 1 1 1 0 0 0 0 ] ][0X [4X------------------------------------------------------------------[0X [1X5.2-11 FerreroDesignCode[0X [2X> FerreroDesignCode( [0X[3XP, m[0X[2X ) ________________________________________[0Xfunction [13XRequires the GAP package SONATA[0X A group K together with a group of automorphism H of K such that the semidirect product KH is a Frobenius group with complement H is called a Ferrero pair (K, H) in SONATA. Take a Frobenius (G,+) group with kernel K and complement H. Consider the design D with point set K and block set a^H + b | a, b in K, a not= 0. Here a^H denotes the orbit of a under conjugation by elements of H. Every planar near-ring design of type "*" can be obtained in this way from groups. These designs (from a Frobenius kernel of order v and a Frobenius complement of order k) have v(v-1)/k distinct blocks and they are all of size k. Moreover each of the v points occurs in exactly v-1 distinct blocks. Hence the rows and the columns of the incidence matrix M of the design are always of constant weight. [10XFerreroDesignCode[0X constructs binary linear code arising from the incdence matrix of a design associated to a "Ferrero pair" arising from a fixed-point-free (fpf) automorphism groups and Frobenius group. INPUT: P is a list of prime powers describing an abelian group G. m > 0 is an integer such that G admits a cyclic fpf automorphism group of size m. This means that for all q = p^k in P, OrderMod(p, m) must divide q (see the SONATA documentation for [10XFpfAutomorphismGroupsCyclic[0X). OUTPUT: The binary linear code whose generator matrix is the incidence matrix of a design associated to a "Ferrero pair" arising from the fixed-point-free (fpf) automorphism group of G. The pair (H,K) is called a Ferraro pair and the semidirect product KH is a Frobenius group with complement H. AUTHORS: Peter Mayr and David Joyner [4X--------------------------- Example ----------------------------[0X [4Xgap> G:=AbelianGroup([5,5] );[0X [4X [ pc group of size 25 with 2 generators ][0X [4Xgap> FpfAutomorphismGroupsMaxSize( G );[0X [4X[ 24, 2 ][0X [4Xgap> L:=FpfAutomorphismGroupsCyclic( [5,5], 3 );[0X [4X[ [ [ f1, f2 ] -> [ f1*f2^2, f1*f2^3 ] ],[0X [4X [ pc group of size 25 with 2 generators ] ][0X [4Xgap> D := DesignFromFerreroPair( L[2], Group(L[1][1]), "*" );[0X [4X [ a 2 - ( 25, 3, 2 ) nearring generated design ][0X [4Xgap> M:=IncidenceMat( D );; Length(M); Length(TransposedMat(M));[0X [4X25[0X [4X200[0X [4Xgap> C1:=GeneratorMatCode(M*Z(2),GF(2));[0X [4Xa linear [200,25,1..24]62..100 code defined by generator matrix over GF(2)[0X [4Xgap> MinimumDistance(C1);[0X [4X24[0X [4Xgap> C2:=FerreroDesignCode( [5,5],3);[0X [4Xa linear [200,25,1..24]62..100 code defined by generator matrix over GF(2)[0X [4Xgap> C1=C2;[0X [4Xtrue[0X [4X[0X [4X------------------------------------------------------------------[0X [1X5.2-12 RandomLinearCode[0X [2X> RandomLinearCode( [0X[3Xn, k, F[0X[2X ) ______________________________________[0Xfunction [10XRandomLinearCode[0X returns a random linear code with word length [3Xn[0X, dimension [3Xk[0X over field [3XF[0X. The method used is to first construct a kx n matrix of the block form (I,A), where I is a kx k identity matrix and A is a kx (n-k) matrix constructed using [10XRandom(F)[0X repeatedly. Then the columns are permuted using a randomly selected element of [10XSymmetricGroup(n)[0X. To create a random unrestricted code, use [10XRandomCode[0X (see [2XRandomCode[0X ([14X5.1-5[0X)). [4X--------------------------- Example ----------------------------[0X [4Xgap> C := RandomLinearCode( 15, 4, GF(3) );[0X [4Xa [15,4,?] randomly generated code over GF(3)[0X [4Xgap> Display(C);[0X [4Xa linear [15,4,1..6]6..10 random linear code over GF(3)[0X [4X------------------------------------------------------------------[0X The method [5XGUAVA[0X chooses to output the result of a [10XRandomLinearCode[0X command is different than other codes. For example, the bounds on the minimum distance is not displayed. Howeer, you can use the [10XDisplay[0X command to print this information. This new display method was added in version 1.9 to speed up the command (if n is about 80 and k about 40, for example, the time it took to look up and/or calculate the bounds on the minimum distance was too long). [1X5.2-13 OptimalityCode[0X [2X> OptimalityCode( [0X[3XC[0X[2X ) ______________________________________________[0Xfunction [10XOptimalityCode[0X returns the difference between the smallest known upper bound and the actual size of the code. Note that the value of the function [10XUpperBound[0X is not always equal to the actual upper bound A(n,d) thus the result may not be equal to 0 even if the code is optimal! [10XOptimalityLinearCode[0X is similar but applies only to linear codes. [1X5.2-14 BestKnownLinearCode[0X [2X> BestKnownLinearCode( [0X[3Xn, k, F[0X[2X ) ___________________________________[0Xfunction [10XBestKnownLinearCode[0X returns the best known (as of 11 May 2006) linear code of length [3Xn[0X, dimension [3Xk[0X over field [3XF[0X. The function uses the tables described in section [2XBoundsMinimumDistance[0X ([14X7.1-13[0X) to construct this code. This command can also be called using the syntax [10XBestKnownLinearCode( rec )[0X, where [3Xrec[0X must be a record containing the fields `lowerBound', `upperBound' and `construction'. It uses the information in this field to construct a code. This form is meant to be used together with the function [10XBoundsMinimumDistance[0X (see [2XBoundsMinimumDistance[0X ([14X7.1-13[0X)), if the bounds are already calculated. [4X--------------------------- Example ----------------------------[0X [4Xgap> C1 := BestKnownLinearCode( 23, 12, GF(2) );[0X [4Xa linear [23,12,7]3 punctured code[0X [4Xgap> C1 = BinaryGolayCode();[0X [4Xfalse # it's constructed differently[0X [4Xgap> C1 := BestKnownLinearCode( 23, 12, GF(2) );[0X [4Xa linear [23,12,7]3 punctured code[0X [4Xgap> G1 := MutableCopyMat(GeneratorMat(C1));;[0X [4Xgap> PutStandardForm(G1);[0X [4X()[0X [4Xgap> Display(G1);[0X [4X 1 . . . . . . . . . . . 1 . 1 . 1 1 1 . . . 1[0X [4X . 1 . . . . . . . . . . 1 1 1 1 1 . . 1 . . .[0X [4X . . 1 . . . . . . . . . 1 1 . 1 . . 1 . 1 . 1[0X [4X . . . 1 . . . . . . . . 1 1 . . . 1 1 1 . 1 .[0X [4X . . . . 1 . . . . . . . 1 1 . . 1 1 . 1 1 . 1[0X [4X . . . . . 1 . . . . . . . 1 1 . . 1 1 . 1 1 1[0X [4X . . . . . . 1 . . . . . . . 1 1 . . 1 1 . 1 1[0X [4X . . . . . . . 1 . . . . 1 . 1 1 . 1 1 1 1 . .[0X [4X . . . . . . . . 1 . . . . 1 . 1 1 . 1 1 1 1 .[0X [4X . . . . . . . . . 1 . . . . 1 . 1 1 . 1 1 1 .[0X [4X . . . . . . . . . . 1 . 1 . 1 1 1 . . . 1 1 1[0X [4X . . . . . . . . . . . 1 . 1 . 1 1 1 . . . 1 1[0X [4Xgap> C2 := BinaryGolayCode();[0X [4Xa cyclic [23,12,7]3 binary Golay code over GF(2)[0X [4Xgap> G2 := MutableCopyMat(GeneratorMat(C2));;[0X [4Xgap> PutStandardForm(G2);[0X [4X()[0X [4Xgap> Display(G2);[0X [4X 1 . . . . . . . . . . . 1 . 1 . 1 1 1 . . . 1[0X [4X . 1 . . . . . . . . . . 1 1 1 1 1 . . 1 . . 1[0X [4X . . 1 . . . . . . . . . 1 1 . 1 . . 1 . 1 . 1[0X [4X . . . 1 . . . . . . . . 1 1 . . . 1 1 1 . 1 1[0X [4X . . . . 1 . . . . . . . 1 1 . . 1 1 . 1 1 . .[0X [4X . . . . . 1 . . . . . . . 1 1 . . 1 1 . 1 1 .[0X [4X . . . . . . 1 . . . . . . . 1 1 . . 1 1 . 1 1[0X [4X . . . . . . . 1 . . . . 1 . 1 1 . 1 1 1 1 . .[0X [4X . . . . . . . . 1 . . . . 1 . 1 1 . 1 1 1 1 .[0X [4X . . . . . . . . . 1 . . . . 1 . 1 1 . 1 1 1 1[0X [4X . . . . . . . . . . 1 . 1 . 1 1 1 . . . 1 1 .[0X [4X . . . . . . . . . . . 1 . 1 . 1 1 1 . . . 1 1[0X [4X## Despite their generator matrices are different, they are equivalent codes, see below.[0X [4Xgap> IsEquivalent(C1,C2);[0X [4Xtrue[0X [4Xgap> CodeIsomorphism(C1,C2);[0X [4X(4,14,6,12,5)(7,17,18,11,19)(8,22,13,21,16)(10,23,15,20)[0X [4Xgap> Display( BestKnownLinearCode( 81, 77, GF(4) ) );[0X [4Xa linear [81,77,3]2..3 shortened code of[0X [4Xa linear [85,81,3]1 Hamming (4,4) code over GF(4)[0X [4Xgap> C:=BestKnownLinearCode(174,72);[0X [4Xa linear [174,72,31..36]26..87 code defined by generator matrix over GF(2)[0X [4Xgap> bounds := BoundsMinimumDistance( 81, 77, GF(4) );[0X [4Xrec( n := 81, k := 77, q := 4, [0X [4X references := rec( Ham := [ "%T this reference is unknown, for more info", [0X [4X "%T contact A.E. Brouwer (aeb@cwi.nl)" ], [0X [4X cap := [ "%T this reference is unknown, for more info", [0X [4X "%T contact A.E. Brouwer (aeb@cwi.nl)" ] ), [0X [4X construction := [ (Operation "ShortenedCode"), [0X [4X [ [ (Operation "HammingCode"), [ 4, 4 ] ], [ 1, 2, 3, 4 ] ] ], [0X [4X lowerBound := 3, [0X [4X lowerBoundExplanation := [ "Lb(81,77)=3, by shortening of:", [0X [4X "Lb(85,81)=3, reference: Ham" ], upperBound := 3, [0X [4X upperBoundExplanation := [ "Ub(81,77)=3, by considering shortening to:", [0X [4X "Ub(18,14)=3, reference: cap" ] )[0X [4Xgap> C := BestKnownLinearCode( bounds );[0X [4Xa linear [81,77,3]2..3 shortened code[0X [4Xgap> C = BestKnownLinearCode(81, 77, GF(4) );[0X [4Xtrue[0X [4X------------------------------------------------------------------[0X [1X5.3 Gabidulin Codes[0X These five binary, linear codes are derived from an article by Gabidulin, Davydov and Tombak [GDT91]. All these codes are defined by check matrices. Exact definitions can be found in the article. The Gabidulin code, the enlarged Gabidulin code, the Davydov code, the Tombak code, and the enlarged Tombak code, correspond with theorem 1, 2, 3, 4, and 5, respectively in the article. Like the Hamming codes, these codes have fixed minimum distance and covering radius, but can be arbitrarily long. [1X5.3-1 GabidulinCode[0X [2X> GabidulinCode( [0X[3Xm, w1, w2[0X[2X ) _______________________________________[0Xfunction [10XGabidulinCode[0X yields a code of length 5 . 2^m-2-1, redundancy 2m-1, minimum distance 3 and covering radius 2. [3Xw1[0X and [3Xw2[0X should be elements of GF(2^m-2). [1X5.3-2 EnlargedGabidulinCode[0X [2X> EnlargedGabidulinCode( [0X[3Xm, w1, w2, e[0X[2X ) ____________________________[0Xfunction [10XEnlargedGabidulinCode[0X yields a code of length 7. 2^m-2-2, redundancy 2m, minimum distance 3 and covering radius 2. [3Xw1[0X and [3Xw2[0X are elements of GF(2^m-2). [3Xe[0X is an element of GF(2^m). [1X5.3-3 DavydovCode[0X [2X> DavydovCode( [0X[3Xr, v, ei, ej[0X[2X ) ______________________________________[0Xfunction [10XDavydovCode[0X yields a code of length 2^v + 2^r-v - 3, redundancy [3Xr[0X, minimum distance 4 and covering radius 2. [3Xv[0X is an integer between 2 and r-2. [3Xei[0X and [3Xej[0X are elements of GF(2^v) and GF(2^r-v), respectively. [1X5.3-4 TombakCode[0X [2X> TombakCode( [0X[3Xm, e, beta, gamma, w1, w2[0X[2X ) __________________________[0Xfunction [10XTombakCode[0X yields a code of length 15 * 2^m-3 - 3, redundancy 2m, minimum distance 4 and covering radius 2. [3Xe[0X is an element of GF(2^m). [3Xbeta[0X and [3Xgamma[0X are elements of GF(2^m-1). [3Xw1[0X and [3Xw2[0X are elements of GF(2^m-3). [1X5.3-5 EnlargedTombakCode[0X [2X> EnlargedTombakCode( [0X[3Xm, e, beta, gamma, w1, w2, u[0X[2X ) _______________[0Xfunction [10XEnlargedTombakCode[0X yields a code of length 23 * 2^m-4 - 3, redundancy 2m-1, minimum distance 4 and covering radius 2. The parameters [3Xm[0X, [3Xe[0X, [3Xbeta[0X, [3Xgamma[0X, [3Xw1[0X and [3Xw2[0X are defined as in [10XTombakCode[0X. [3Xu[0X is an element of GF(2^m-1). [4X--------------------------- Example ----------------------------[0X [4Xgap> GabidulinCode( 4, Z(4)^0, Z(4)^1 );[0X [4Xa linear [19,12,3]2 Gabidulin code (m=4) over GF(2)[0X [4Xgap> EnlargedGabidulinCode( 4, Z(4)^0, Z(4)^1, Z(16)^11 );[0X [4Xa linear [26,18,3]2 enlarged Gabidulin code (m=4) over GF(2)[0X [4Xgap> DavydovCode( 6, 3, Z(8)^1, Z(8)^5 );[0X [4Xa linear [13,7,4]2 Davydov code (r=6, v=3) over GF(2)[0X [4Xgap> TombakCode( 5, Z(32)^6, Z(16)^14, Z(16)^10, Z(4)^0, Z(4)^1 );[0X [4Xa linear [57,47,4]2 Tombak code (m=5) over GF(2)[0X [4Xgap> EnlargedTombakCode( 6, Z(32)^6, Z(16)^14, Z(16)^10,[0X [4X> Z(4)^0, Z(4)^0, Z(32)^23 );[0X [4Xa linear [89,78,4]2 enlarged Tombak code (m=6) over GF(2)[0X [4X------------------------------------------------------------------[0X [1X5.4 Golay Codes[0X " The Golay code is probably the most important of all codes for both practical and theoretical reasons. " ([MS83], pg. 64). Though born in Switzerland, M. J. E. Golay (1902-1989) worked for the US Army Labs for most of his career. For more information on his life, see his obit in the June 1990 IEEE Information Society Newsletter. [1X5.4-1 BinaryGolayCode[0X [2X> BinaryGolayCode( [0X[3X[0X[2X ) ______________________________________________[0Xfunction [10XBinaryGolayCode[0X returns a binary Golay code. This is a perfect [23,12,7] code. It is also cyclic, and has generator polynomial g(x)=1+x^2+x^4+x^5+x^6+x^10+x^11. Extending it results in an extended Golay code (see [2XExtendedBinaryGolayCode[0X ([14X5.4-2[0X)). There's also the ternary Golay code (see [2XTernaryGolayCode[0X ([14X5.4-3[0X)). [4X--------------------------- Example ----------------------------[0X [4Xgap> C:=BinaryGolayCode();[0X [4Xa cyclic [23,12,7]3 binary Golay code over GF(2)[0X [4Xgap> ExtendedBinaryGolayCode() = ExtendedCode(BinaryGolayCode());[0X [4Xtrue[0X [4Xgap> IsPerfectCode(C);[0X [4Xtrue [0X [4Xgap> IsCyclicCode(C);[0X [4Xtrue[0X [4X------------------------------------------------------------------[0X [1X5.4-2 ExtendedBinaryGolayCode[0X [2X> ExtendedBinaryGolayCode( [0X[3X[0X[2X ) ______________________________________[0Xfunction [10XExtendedBinaryGolayCode[0X returns an extended binary Golay code. This is a [24,12,8] code. Puncturing in the last position results in a perfect binary Golay code (see [2XBinaryGolayCode[0X ([14X5.4-1[0X)). The code is self-dual. [4X--------------------------- Example ----------------------------[0X [4Xgap> C := ExtendedBinaryGolayCode();[0X [4Xa linear [24,12,8]4 extended binary Golay code over GF(2)[0X [4Xgap> IsSelfDualCode(C);[0X [4Xtrue[0X [4Xgap> P := PuncturedCode(C);[0X [4Xa linear [23,12,7]3 punctured code[0X [4Xgap> P = BinaryGolayCode();[0X [4Xtrue [0X [4Xgap> IsCyclicCode(C);[0X [4Xfalse[0X [4X[0X [4X------------------------------------------------------------------[0X [1X5.4-3 TernaryGolayCode[0X [2X> TernaryGolayCode( [0X[3X[0X[2X ) _____________________________________________[0Xfunction [10XTernaryGolayCode[0X returns a ternary Golay code. This is a perfect [11,6,5] code. It is also cyclic, and has generator polynomial g(x)=2+x^2+2x^3+x^4+x^5. Extending it results in an extended Golay code (see [2XExtendedTernaryGolayCode[0X ([14X5.4-4[0X)). There's also the binary Golay code (see [2XBinaryGolayCode[0X ([14X5.4-1[0X)). [4X--------------------------- Example ----------------------------[0X [4Xgap> C:=TernaryGolayCode();[0X [4Xa cyclic [11,6,5]2 ternary Golay code over GF(3)[0X [4Xgap> ExtendedTernaryGolayCode() = ExtendedCode(TernaryGolayCode());[0X [4Xtrue [0X [4Xgap> IsCyclicCode(C);[0X [4Xtrue[0X [4X------------------------------------------------------------------[0X [1X5.4-4 ExtendedTernaryGolayCode[0X [2X> ExtendedTernaryGolayCode( [0X[3X[0X[2X ) _____________________________________[0Xfunction [10XExtendedTernaryGolayCode[0X returns an extended ternary Golay code. This is a [12,6,6] code. Puncturing this code results in a perfect ternary Golay code (see [2XTernaryGolayCode[0X ([14X5.4-3[0X)). The code is self-dual. [4X--------------------------- Example ----------------------------[0X [4Xgap> C := ExtendedTernaryGolayCode();[0X [4Xa linear [12,6,6]3 extended ternary Golay code over GF(3)[0X [4Xgap> IsSelfDualCode(C);[0X [4Xtrue[0X [4Xgap> P := PuncturedCode(C);[0X [4Xa linear [11,6,5]2 punctured code[0X [4Xgap> P = TernaryGolayCode();[0X [4Xtrue [0X [4Xgap> IsCyclicCode(C);[0X [4Xfalse[0X [4X------------------------------------------------------------------[0X [1X5.5 Generating Cyclic Codes[0X The elements of a cyclic code C are all multiples of a ('generator') polynomial g(x), where calculations are carried out modulo x^n-1. Therefore, as polynomials in x, the elements always have degree less than n. A cyclic code is an ideal in the ring F[x]/(x^n-1) of polynomials modulo x^n - 1. The unique monic polynomial of least degree that generates C is called the [13Xgenerator polynomial[0X of C. It is a divisor of the polynomial x^n-1. The [13Xcheck polynomial[0X is the polynomial h(x) with g(x)h(x)=x^n-1. Therefore it is also a divisor of x^n-1. The check polynomial has the property that c(x)h(x) \equiv 0 \pmod{x^n-1}, for every codeword c(x)in C. The first two functions described below generate cyclic codes from a given generator or check polynomial. All cyclic codes can be constructed using these functions. Two of the Golay codes already described are cyclic (see [2XBinaryGolayCode[0X ([14X5.4-1[0X) and [2XTernaryGolayCode[0X ([14X5.4-3[0X)). For example, the [5XGUAVA[0X record for a binary Golay code contains the generator polynomial: [4X--------------------------- Example ----------------------------[0X [4Xgap> C := BinaryGolayCode();[0X [4Xa cyclic [23,12,7]3 binary Golay code over GF(2)[0X [4Xgap> NamesOfComponents(C);[0X [4X[ "LeftActingDomain", "GeneratorsOfLeftOperatorAdditiveGroup", "WordLength",[0X [4X "GeneratorMat", "GeneratorPol", "Dimension", "Redundancy", "Size", "name",[0X [4X "lowerBoundMinimumDistance", "upperBoundMinimumDistance", "WeightDistribution",[0X [4X "boundsCoveringRadius", "MinimumWeightOfGenerators", [0X [4X "UpperBoundOptimalMinimumDistance" ][0X [4Xgap> C!.GeneratorPol;[0X [4Xx_1^11+x_1^10+x_1^6+x_1^5+x_1^4+x_1^2+Z(2)^0[0X [4X------------------------------------------------------------------[0X Then functions that generate cyclic codes from a prescribed set of roots of the generator polynomial are described, including the BCH codes (see [2XRootsCode[0X ([14X5.5-3[0X), [2XBCHCode[0X ([14X5.5-4[0X), [2XReedSolomonCode[0X ([14X5.5-5[0X) and [2XQRCode[0X ([14X5.5-7[0X)). Finally we describe the trivial codes (see [2XWholeSpaceCode[0X ([14X5.5-11[0X), [2XNullCode[0X ([14X5.5-12[0X), [2XRepetitionCode[0X ([14X5.5-13[0X)), and the command [10XCyclicCodes[0X which lists all cyclic codes ([2XCyclicCodes[0X ([14X5.5-14[0X)). [1X5.5-1 GeneratorPolCode[0X [2X> GeneratorPolCode( [0X[3Xg, n[, name], F[0X[2X ) ______________________________[0Xfunction [10XGeneratorPolCode[0X creates a cyclic code with a generator polynomial [3Xg[0X, word length [3Xn[0X, over [3XF[0X. [3Xname[0X can contain a short description of the code. If [3Xg[0X is not a divisor of x^n-1, it cannot be a generator polynomial. In that case, a code is created with generator polynomial gcd( g, x^n-1 ), i.e. the greatest common divisor of [3Xg[0X and x^n-1. This is a valid generator polynomial that generates the ideal (g). See [2XGenerating Cyclic Codes[0X ([14X5.5[0X). [4X--------------------------- Example ----------------------------[0X [4Xgap> x:= Indeterminate( GF(2) );; P:= x^2+1;[0X [4XZ(2)^0+x^2[0X [4Xgap> C1 := GeneratorPolCode(P, 7, GF(2));[0X [4Xa cyclic [7,6,1..2]1 code defined by generator polynomial over GF(2)[0X [4Xgap> GeneratorPol( C1 );[0X [4XZ(2)^0+x[0X [4Xgap> C2 := GeneratorPolCode( x+1, 7, GF(2)); [0X [4Xa cyclic [7,6,1..2]1 code defined by generator polynomial over GF(2)[0X [4Xgap> GeneratorPol( C2 );[0X [4XZ(2)^0+x[0X [4X------------------------------------------------------------------[0X [1X5.5-2 CheckPolCode[0X [2X> CheckPolCode( [0X[3Xh, n[, name], F[0X[2X ) __________________________________[0Xfunction [10XCheckPolCode[0X creates a cyclic code with a check polynomial [3Xh[0X, word length [3Xn[0X, over [3XF[0X. [3Xname[0X can contain a short description of the code (as a string). If [3Xh[0X is not a divisor of x^n-1, it cannot be a check polynomial. In that case, a code is created with check polynomial gcd( h, x^n-1 ), i.e. the greatest common divisor of [3Xh[0X and x^n-1. This is a valid check polynomial that yields the same elements as the ideal (h). See [14X5.5[0X. [4X--------------------------- Example ----------------------------[0X [4Xgap> x:= Indeterminate( GF(3) );; P:= x^2+2;[0X [4X-Z(3)^0+x_1^2[0X [4Xgap> H := CheckPolCode(P, 7, GF(3));[0X [4Xa cyclic [7,1,7]4 code defined by check polynomial over GF(3)[0X [4Xgap> CheckPol(H);[0X [4X-Z(3)^0+x_1[0X [4Xgap> Gcd(P, X(GF(3))^7-1);[0X [4X-Z(3)^0+x_1[0X [4X------------------------------------------------------------------[0X [1X5.5-3 RootsCode[0X [2X> RootsCode( [0X[3Xn, list[0X[2X ) _____________________________________________[0Xfunction This is the generalization of the BCH, Reed-Solomon and quadratic residue codes (see [2XBCHCode[0X ([14X5.5-4[0X), [2XReedSolomonCode[0X ([14X5.5-5[0X) and [2XQRCode[0X ([14X5.5-7[0X)). The user can give a length of the code [3Xn[0X and a prescribed set of zeros. The argument [3Xlist[0X must be a valid list of primitive n^th roots of unity in a splitting field GF(q^m). The resulting code will be over the field GF(q). The function will return the largest possible cyclic code for which the list [3Xlist[0X is a subset of the roots of the code. From this list, [5XGUAVA[0X calculates the entire set of roots. This command can also be called with the syntax [10XRootsCode( n, list, q )[0X. In this second form, the second argument is a list of integers, ranging from 0 to n-1. The resulting code will be over a field GF(q). [5XGUAVA[0X calculates a primitive n^th root of unity, alpha, in the extension field of GF(q). It uses the set of the powers of alpha in the list as a prescribed set of zeros. [4X--------------------------- Example ----------------------------[0X [4Xgap> a := PrimitiveUnityRoot( 3, 14 );[0X [4XZ(3^6)^52[0X [4Xgap> C1 := RootsCode( 14, [ a^0, a, a^3 ] );[0X [4Xa cyclic [14,7,3..6]3..7 code defined by roots over GF(3)[0X [4Xgap> MinimumDistance( C1 );[0X [4X4[0X [4Xgap> b := PrimitiveUnityRoot( 2, 15 );[0X [4XZ(2^4)[0X [4Xgap> C2 := RootsCode( 15, [ b, b^2, b^3, b^4 ] );[0X [4Xa cyclic [15,7,5]3..5 code defined by roots over GF(2)[0X [4Xgap> C2 = BCHCode( 15, 5, GF(2) );[0X [4Xtrue [0X [4XC3 := RootsCode( 4, [ 1, 2 ], 5 );[0X [4XRootsOfCode( C3 );[0X [4XC3 = ReedSolomonCode( 4, 3 );[0X [4X[0X [4X------------------------------------------------------------------[0X [1X5.5-4 BCHCode[0X [2X> BCHCode( [0X[3Xn[, b], delta, F[0X[2X ) ______________________________________[0Xfunction The function [10XBCHCode[0X returns a 'Bose-Chaudhuri-Hockenghem code' (or [13XBCH code[0X for short). This is the largest possible cyclic code of length [3Xn[0X over field [3XF[0X, whose generator polynomial has zeros a^{b},a^{b+1}, ..., a^{b+delta-2}, where a is a primitive n^th root of unity in the splitting field GF(q^m), [3Xb[0X is an integer 0<= b<= n-delta+1 and m is the multiplicative order of q modulo [3Xn[0X. (The integers b,...,b+delta-2 typically lie in the range 1,...,n-1.) Default value for [3Xb[0X is 1, though the algorithm allows b=0. The length [3Xn[0X of the code and the size q of the field must be relatively prime. The generator polynomial is equal to the least common multiple of the minimal polynomials of a^{b}, a^{b+1}, ..., a^{b+delta-2}. The set of zeroes of the generator polynomial is equal to the union of the sets \{a^x\ |\ x \in C_k\}, where C_k is the k^th cyclotomic coset of q modulo n and b<= k<= b+delta-2 (see [2XCyclotomicCosets[0X ([14X7.5-12[0X)). Special cases are b=1 (resulting codes are called 'narrow-sense' BCH codes), and n=q^m-1 (known as 'primitive' BCH codes). [5XGUAVA[0X calculates the largest value of d for which the BCH code with designed distance d coincides with the BCH code with designed distance [3Xdelta[0X. This distance d is called the [13XBose distance[0X of the code. The true minimum distance of the code is greater than or equal to the Bose distance. Printed are the designed distance (to be precise, the Bose distance) d, and the starting power b. The Sugiyama decoding algorithm has been implemented for this code (see [2XDecode[0X ([14X4.10-1[0X)). [4X--------------------------- Example ----------------------------[0X [4Xgap> C1 := BCHCode( 15, 3, 5, GF(2) );[0X [4Xa cyclic [15,5,7]5 BCH code, delta=7, b=1 over GF(2)[0X [4Xgap> DesignedDistance( C1 );[0X [4X7[0X [4Xgap> C2 := BCHCode( 23, 2, GF(2) );[0X [4Xa cyclic [23,12,5..7]3 BCH code, delta=5, b=1 over GF(2)[0X [4Xgap> DesignedDistance( C2 ); [0X [4X5[0X [4Xgap> MinimumDistance(C2);[0X [4X7 [0X [4X------------------------------------------------------------------[0X See [2XRootsCode[0X ([14X5.5-3[0X) for a more general construction. [1X5.5-5 ReedSolomonCode[0X [2X> ReedSolomonCode( [0X[3Xn, d[0X[2X ) __________________________________________[0Xfunction [10XReedSolomonCode[0X returns a 'Reed-Solomon code' of length [3Xn[0X, designed distance [3Xd[0X. This code is a primitive narrow-sense BCH code over the field GF(q), where q=n+1. The dimension of an RS code is n-d+1. According to the Singleton bound (see [2XUpperBoundSingleton[0X ([14X7.1-1[0X)) the dimension cannot be greater than this, so the true minimum distance of an RS code is equal to [3Xd[0X and the code is maximum distance separable (see [2XIsMDSCode[0X ([14X4.3-7[0X)). [4X--------------------------- Example ----------------------------[0X [4Xgap> C1 := ReedSolomonCode( 3, 2 );[0X [4Xa cyclic [3,2,2]1 Reed-Solomon code over GF(4)[0X [4Xgap> IsCyclicCode(C1);[0X [4Xtrue[0X [4Xgap> C2 := ReedSolomonCode( 4, 3 );[0X [4Xa cyclic [4,2,3]2 Reed-Solomon code over GF(5)[0X [4Xgap> RootsOfCode( C2 );[0X [4X[ Z(5), Z(5)^2 ][0X [4Xgap> IsMDSCode(C2);[0X [4Xtrue [0X [4X------------------------------------------------------------------[0X See [2XGeneralizedReedSolomonCode[0X ([14X5.6-2[0X) for a more general construction. [1X5.5-6 ExtendedReedSolomonCode[0X [2X> ExtendedReedSolomonCode( [0X[3Xn, d[0X[2X ) __________________________________[0Xfunction [10XExtendedReedSolomonCode[0X creates a Reed-Solomon code of length n-1 with designed distance d-1 and then returns the code which is extended by adding an overall parity-check symbol. The motivation for creating this function is calling [2XExtendedCode[0X ([14X6.1-1[0X) function over a Reed-Solomon code will take considerably long time. [4X--------------------------- Example ----------------------------[0X [4Xgap> C := ExtendedReedSolomonCode(17, 13);[0X [4Xa linear [17,5,13]9..12 extended Reed Solomon code over GF(17)[0X [4Xgap> IsMDSCode(C);[0X [4Xtrue[0X [4X------------------------------------------------------------------[0X [1X5.5-7 QRCode[0X [2X> QRCode( [0X[3Xn, F[0X[2X ) ___________________________________________________[0Xfunction [10XQRCode[0X returns a quadratic residue code. If [3XF[0X is a field GF(q), then q must be a quadratic residue modulo [3Xn[0X. That is, an x exists with x^2 = q mod n. Both [3Xn[0X and q must be primes. Its generator polynomial is the product of the polynomials x-a^i. a is a primitive n^th root of unity, and i is an integer in the set of quadratic residues modulo [3Xn[0X. [4X--------------------------- Example ----------------------------[0X [4Xgap> C1 := QRCode( 7, GF(2) );[0X [4Xa cyclic [7,4,3]1 quadratic residue code over GF(2)[0X [4Xgap> IsEquivalent( C1, HammingCode( 3, GF(2) ) );[0X [4Xtrue[0X [4Xgap> IsCyclicCode(C1);[0X [4Xtrue[0X [4Xgap> IsCyclicCode(HammingCode( 3, GF(2) ));[0X [4Xfalse[0X [4Xgap> C2 := QRCode( 11, GF(3) );[0X [4Xa cyclic [11,6,4..5]2 quadratic residue code over GF(3)[0X [4Xgap> C2 = TernaryGolayCode();[0X [4Xtrue [0X [4Xgap> Q1 := QRCode( 7, GF(2));[0X [4Xa cyclic [7,4,3]1 quadratic residue code over GF(2)[0X [4Xgap> P1:=AutomorphismGroup(Q1); IdGroup(P1);[0X [4XGroup([ (1,2)(5,7), (2,3)(4,7), (2,4)(5,6), (3,5)(6,7), (3,7)(5,6) ])[0X [4X[ 168, 42 ][0X [4X------------------------------------------------------------------[0X [1X5.5-8 QQRCodeNC[0X [2X> QQRCodeNC( [0X[3Xp[0X[2X ) ___________________________________________________[0Xfunction [10XQQRCodeNC[0X is the same as [10XQQRCode[0X, except that it uses [10XGeneratorMatCodeNC[0X instead of [10XGeneratorMatCode[0X. [1X5.5-9 QQRCode[0X [2X> QQRCode( [0X[3Xp[0X[2X ) _____________________________________________________[0Xfunction [10XQQRCode[0X returns a quasi-quadratic residue code, as defined by Proposition 2.2 in Bazzi-Mittel [BMd)]. The parameter [3Xp[0X must be a prime. Its generator matrix has the block form G=(Q,N). Here Q is a px circulant matrix whose top row is (0,x_1,...,x_p-1), where x_i=1 if and only if i is a quadratic residue mod p, and N is a px circulant matrix whose top row is (0,y_1,...,y_p-1), where x_i+y_i=1 for all i. (In fact, this matrix can be recovered as the component [10XDoublyCirculant[0X of the code.) [4X--------------------------- Example ----------------------------[0X [4Xgap> C1 := QQRCode( 7);[0X [4Xa linear [14,7,1..4]3..5 code defined by generator matrix over GF(2)[0X [4Xgap> G1:=GeneratorMat(C1);;[0X [4Xgap> Display(G1);[0X [4X . 1 1 . 1 . . . . . 1 . 1 1[0X [4X 1 . 1 1 1 . . . . 1 1 1 . 1[0X [4X . . . 1 1 . 1 . 1 1 . . . 1[0X [4X . . 1 . 1 1 1 1 . 1 . . 1 1[0X [4X . . . . . . . 1 . . 1 1 1 .[0X [4X . . . . . . . . . 1 1 1 . 1[0X [4X . . . . . . . . 1 . . 1 1 1[0X [4Xgap> Display(C1!.DoublyCirculant);[0X [4X . 1 1 . 1 . . . . . 1 . 1 1[0X [4X 1 1 . 1 . . . . . 1 . 1 1 .[0X [4X 1 . 1 . . . 1 . 1 . 1 1 . .[0X [4X . 1 . . . 1 1 1 . 1 1 . . .[0X [4X 1 . . . 1 1 . . 1 1 . . . 1[0X [4X . . . 1 1 . 1 1 1 . . . 1 .[0X [4X . . 1 1 . 1 . 1 . . . 1 . 1[0X [4Xgap> MinimumDistance(C1);[0X [4X4[0X [4Xgap> C2 := QQRCode( 29); MinimumDistance(C2);[0X [4Xa linear [58,28,1..14]8..29 code defined by generator matrix over GF(2)[0X [4X12[0X [4Xgap> Aut2:=AutomorphismGroup(C2); IdGroup(Aut2);[0X [4X[ permutation group of size 812 with 4 generators ][0X [4X[ 812, 7 ][0X [4X------------------------------------------------------------------[0X [1X5.5-10 FireCode[0X [2X> FireCode( [0X[3Xg, b[0X[2X ) _________________________________________________[0Xfunction [10XFireCode[0X constructs a (binary) Fire code. [3Xg[0X is a primitive polynomial of degree m, and a factor of x^r-1. [3Xb[0X an integer 0 <= b <= m not divisible by r, that determines the burst length of a single error burst that can be corrected. The argument [3Xg[0X can be a polynomial with base ring GF(2), or a list of coefficients in GF(2). The generator polynomial of the code is defined as the product of [3Xg[0X and x^2b-1+1. Here is the general definition of 'Fire code', named after P. Fire, who introduced these codes in 1959 in order to correct burst errors. First, a definition. If F=GF(q) and fin F[x] then we say f has [13Xorder[0X e if f(x)|(x^e-1). A [13XFire code[0X is a cyclic code over F with generator polynomial g(x)= (x^2t-1-1)p(x), where p(x) does not divide x^2t-1-1 and satisfies deg(p(x))>= t. The length of such a code is the order of g(x). Non-binary Fire codes have not been implemented. . [4X--------------------------- Example ----------------------------[0X [4Xgap> x:= Indeterminate( GF(2) );; G:= x^3+x^2+1;[0X [4XZ(2)^0+x^2+x^3[0X [4Xgap> Factors( G );[0X [4X[ Z(2)^0+x^2+x^3 ][0X [4Xgap> C := FireCode( G, 3 );[0X [4Xa cyclic [35,27,1..4]2..6 3 burst error correcting fire code over GF(2)[0X [4Xgap> MinimumDistance( C );[0X [4X4 # Still it can correct bursts of length 3 [0X [4X------------------------------------------------------------------[0X [1X5.5-11 WholeSpaceCode[0X [2X> WholeSpaceCode( [0X[3Xn, F[0X[2X ) ___________________________________________[0Xfunction [10XWholeSpaceCode[0X returns the cyclic whole space code of length [3Xn[0X over [3XF[0X. This code consists of all polynomials of degree less than [3Xn[0X and coefficients in [3XF[0X. [4X--------------------------- Example ----------------------------[0X [4Xgap> C := WholeSpaceCode( 5, GF(3) );[0X [4Xa cyclic [5,5,1]0 whole space code over GF(3)[0X [4X------------------------------------------------------------------[0X [1X5.5-12 NullCode[0X [2X> NullCode( [0X[3Xn, F[0X[2X ) _________________________________________________[0Xfunction [10XNullCode[0X returns the zero-dimensional nullcode with length [3Xn[0X over [3XF[0X. This code has only one word: the all zero word. It is cyclic though! [4X--------------------------- Example ----------------------------[0X [4Xgap> C := NullCode( 5, GF(3) );[0X [4Xa cyclic [5,0,5]5 nullcode over GF(3)[0X [4Xgap> AsSSortedList( C );[0X [4X[ [ 0 0 0 0 0 ] ][0X [4X------------------------------------------------------------------[0X [1X5.5-13 RepetitionCode[0X [2X> RepetitionCode( [0X[3Xn, F[0X[2X ) ___________________________________________[0Xfunction [10XRepetitionCode[0X returns the cyclic repetition code of length [3Xn[0X over [3XF[0X. The code has as many elements as [3XF[0X, because each codeword consists of a repetition of one of these elements. [4X--------------------------- Example ----------------------------[0X [4Xgap> C := RepetitionCode( 3, GF(5) );[0X [4Xa cyclic [3,1,3]2 repetition code over GF(5)[0X [4Xgap> AsSSortedList( C );[0X [4X[ [ 0 0 0 ], [ 1 1 1 ], [ 2 2 2 ], [ 4 4 4 ], [ 3 3 3 ] ][0X [4Xgap> IsPerfectCode( C );[0X [4Xfalse[0X [4Xgap> IsMDSCode( C );[0X [4Xtrue [0X [4X------------------------------------------------------------------[0X [1X5.5-14 CyclicCodes[0X [2X> CyclicCodes( [0X[3Xn, F[0X[2X ) ______________________________________________[0Xfunction [10XCyclicCodes[0X returns a list of all cyclic codes of length [3Xn[0X over [3XF[0X. It constructs all possible generator polynomials from the factors of x^n-1. Each combination of these factors yields a generator polynomial after multiplication. [4X--------------------------- Example ----------------------------[0X [4Xgap> CyclicCodes(3,GF(3));[0X [4X[ a cyclic [3,3,1]0 enumerated code over GF(3), [0X [4Xa cyclic [3,2,1..2]1 enumerated code over GF(3), [0X [4Xa cyclic [3,1,3]2 enumerated code over GF(3), [0X [4Xa cyclic [3,0,3]3 enumerated code over GF(3) ][0X [4X------------------------------------------------------------------[0X [1X5.5-15 NrCyclicCodes[0X [2X> NrCyclicCodes( [0X[3Xn, F[0X[2X ) ____________________________________________[0Xfunction The function [10XNrCyclicCodes[0X calculates the number of cyclic codes of length [3Xn[0X over field [3XF[0X. [4X--------------------------- Example ----------------------------[0X [4Xgap> NrCyclicCodes( 23, GF(2) );[0X [4X8[0X [4Xgap> codelist := CyclicCodes( 23, GF(2) );[0X [4X[ a cyclic [23,23,1]0 enumerated code over GF(2), [0X [4X a cyclic [23,22,1..2]1 enumerated code over GF(2), [0X [4X a cyclic [23,11,1..8]4..7 enumerated code over GF(2), [0X [4X a cyclic [23,0,23]23 enumerated code over GF(2), [0X [4X a cyclic [23,11,1..8]4..7 enumerated code over GF(2), [0X [4X a cyclic [23,12,1..7]3 enumerated code over GF(2), [0X [4X a cyclic [23,1,23]11 enumerated code over GF(2), [0X [4X a cyclic [23,12,1..7]3 enumerated code over GF(2) ][0X [4Xgap> BinaryGolayCode() in codelist;[0X [4Xtrue[0X [4Xgap> RepetitionCode( 23, GF(2) ) in codelist;[0X [4Xtrue[0X [4Xgap> CordaroWagnerCode( 23 ) in codelist;[0X [4Xfalse # This code is not cyclic [0X [4X------------------------------------------------------------------[0X [1X5.5-16 QuasiCyclicCode[0X [2X> QuasiCyclicCode( [0X[3XG, s, F[0X[2X ) _______________________________________[0Xfunction [10XQuasiCyclicCode( G, k, F )[0X generates a rate 1/m quasi-cyclic code over field [3XF[0X. The input [3XG[0X is a list of univariate polynomials and m is the cardinality of this list. Note that m must be at least 2. The input [3Xs[0X is the size of each circulant and it may not necessarily be the same as the code dimension k, i.e. k le s. There also exists another version, [10XQuasiCyclicCode( G, s )[0X which produces quasi-cyclic codes over F_2 only. Here the parameter [3Xs[0X holds the same definition and the input [3XG[0X is a list of integers, where each integer is an octal representation of a binary univariate polynomial. [4X--------------------------- Example ----------------------------[0X [4Xgap> #[0X [4Xgap> # This example show the case for k = s[0X [4Xgap> #[0X [4Xgap> L1 := PolyCodeword( Codeword("10000000000", GF(4)) );[0X [4XZ(2)^0[0X [4Xgap> L2 := PolyCodeword( Codeword("12223201000", GF(4)) );[0X [4Xx^7+Z(2^2)*x^5+Z(2^2)^2*x^4+Z(2^2)*x^3+Z(2^2)*x^2+Z(2^2)*x+Z(2)^0[0X [4Xgap> L3 := PolyCodeword( Codeword("31111220110", GF(4)) );[0X [4Xx^9+x^8+Z(2^2)*x^6+Z(2^2)*x^5+x^4+x^3+x^2+x+Z(2^2)^2[0X [4Xgap> L4 := PolyCodeword( Codeword("13320333010", GF(4)) );[0X [4Xx^9+Z(2^2)^2*x^7+Z(2^2)^2*x^6+Z(2^2)^2*x^5+Z(2^2)*x^3+Z(2^2)^2*x^2+Z(2^2)^2*x+\[0X [4XZ(2)^0[0X [4Xgap> L5 := PolyCodeword( Codeword("20102211100", GF(4)) );[0X [4Xx^8+x^7+x^6+Z(2^2)*x^5+Z(2^2)*x^4+x^2+Z(2^2)[0X [4Xgap> C := QuasiCyclicCode( [L1, L2, L3, L4, L5], 11, GF(4) );[0X [4Xa linear [55,11,1..32]24..41 quasi-cyclic code over GF(4)[0X [4Xgap> MinimumDistance(C);[0X [4X29[0X [4Xgap> Display(C);[0X [4Xa linear [55,11,29]24..41 quasi-cyclic code over GF(4)[0X [4Xgap> #[0X [4Xgap> # This example show the case for k < s[0X [4Xgap> #[0X [4Xgap> L1 := PolyCodeword( Codeword("02212201220120211002000",GF(3)) );[0X [4X-x^19+x^16+x^15-x^14-x^12+x^11-x^9-x^8+x^7-x^5-x^4+x^3-x^2-x[0X [4Xgap> L2 := PolyCodeword( Codeword("00221100200120220001110",GF(3)) );[0X [4Xx^21+x^20+x^19-x^15-x^14-x^12+x^11-x^8+x^5+x^4-x^3-x^2[0X [4Xgap> L3 := PolyCodeword( Codeword("22021011202221111020021",GF(3)) );[0X [4Xx^22-x^21-x^18+x^16+x^15+x^14+x^13-x^12-x^11-x^10-x^8+x^7+x^6+x^4-x^3-x-Z(3)^0[0X [4Xgap> C := QuasiCyclicCode( [L1, L2, L3], 23, GF(3) );[0X [4Xa linear [69,12,1..37]27..46 quasi-cyclic code over GF(3)[0X [4Xgap> MinimumDistance(C);[0X [4X34[0X [4Xgap> Display(C);[0X [4Xa linear [69,12,34]27..46 quasi-cyclic code over GF(3)[0X [4Xgap> #[0X [4Xgap> # This example show the binary case using octal representation[0X [4Xgap> #[0X [4Xgap> L1 := 001;; # 0 000 001[0X [4Xgap> L2 := 013;; # 0 001 011[0X [4Xgap> L3 := 015;; # 0 001 101[0X [4Xgap> L4 := 077;; # 0 111 111[0X [4Xgap> C := QuasiCyclicCode( [L1, L2, L3, L4], 7 );[0X [4Xa linear [28,7,1..12]8..14 quasi-cyclic code over GF(2)[0X [4Xgap> MinimumDistance(C);[0X [4X12[0X [4Xgap> Display(C);[0X [4Xa linear [28,7,12]8..14 quasi-cyclic code over GF(2)[0X [4X------------------------------------------------------------------[0X [1X5.5-17 CyclicMDSCode[0X [2X> CyclicMDSCode( [0X[3Xq, m, k[0X[2X ) _________________________________________[0Xfunction Given the input parameters [3Xq[0X, [3Xm[0X and [3Xk[0X, this function returns a [q^m + 1, k, q^m - k + 2] cyclic MDS code over GF(q^m). If q^m is even, any value of k can be used, otherwise only odd value of k is accepted. [4X--------------------------- Example ----------------------------[0X [4Xgap> C:=CyclicMDSCode(2,6,24);[0X [4Xa cyclic [65,24,42]31..41 MDS code over GF(64)[0X [4Xgap> IsMDSCode(C);[0X [4Xtrue[0X [4Xgap> C:=CyclicMDSCode(5,3,77);[0X [4Xa cyclic [126,77,50]35..49 MDS code over GF(125)[0X [4Xgap> IsMDSCode(C);[0X [4Xtrue[0X [4Xgap> C:=CyclicMDSCode(3,3,25);[0X [4Xa cyclic [28,25,4]2..3 MDS code over GF(27)[0X [4Xgap> GeneratorPol(C);[0X [4Xx^3+Z(3^3)^7*x^2+Z(3^3)^20*x-Z(3)^0[0X [4Xgap>[0X [4X------------------------------------------------------------------[0X [1X5.5-18 FourNegacirculantSelfDualCode[0X [2X> FourNegacirculantSelfDualCode( [0X[3Xax, bx, k[0X[2X ) _______________________[0Xfunction A four-negacirculant self-dual code has a generator matrix G of the the following form - - | | A | B | G = | I_2k |-----+-----| | | -B^T| A^T | - - where AA^T + BB^T = -I_k and A, B and their transposed are all k x k negacirculant matrices. The generator matrix G returns a [2k, k, d]_q self-dual code over GF(q). For discussion on four-negacirculant self-dual codes, refer to [HHKK07]. The input parameters [3Xax[0X and [3Xbx[0X are the defining polynomials over GF(q) of negacirculant matrices A and B respectively. The last parameter [3Xk[0X is the dimension of the code. [4X--------------------------- Example ----------------------------[0X [4Xgap> ax:=PolyCodeword(Codeword("1200200", GF(3)));[0X [4X-x_1^4-x_1+Z(3)^0[0X [4Xgap> bx:=PolyCodeword(Codeword("2020221", GF(3)));[0X [4Xx_1^6-x_1^5-x_1^4-x_1^2-Z(3)^0[0X [4Xgap> C:=FourNegacirculantSelfDualCode(ax, bx, 14);;[0X [4Xgap> MinimumDistance(C);;[0X [4Xgap> CoveringRadius(C);;[0X [4Xgap> IsSelfDualCode(C);[0X [4Xtrue[0X [4Xgap> Display(C);[0X [4Xa linear [28,14,9]7 four-negacirculant self-dual code over GF(3)[0X [4Xgap> Display( GeneratorMat(C) );[0X [4X 1 . . . . . . . . . . . . . 1 2 . . 2 . . 2 . 2 . 2 2 1[0X [4X . 1 . . . . . . . . . . . . . 1 2 . . 2 . 2 2 . 2 . 2 2[0X [4X . . 1 . . . . . . . . . . . . . 1 2 . . 2 1 2 2 . 2 . 2[0X [4X . . . 1 . . . . . . . . . . 1 . . 1 2 . . 1 1 2 2 . 2 .[0X [4X . . . . 1 . . . . . . . . . . 1 . . 1 2 . . 1 1 2 2 . 2[0X [4X . . . . . 1 . . . . . . . . . . 1 . . 1 2 1 . 1 1 2 2 .[0X [4X . . . . . . 1 . . . . . . . 1 . . 1 . . 1 . 1 . 1 1 2 2[0X [4X . . . . . . . 1 . . . . . . 1 1 2 2 . 2 . 1 . . 1 . . 1[0X [4X . . . . . . . . 1 . . . . . . 1 1 2 2 . 2 2 1 . . 1 . .[0X [4X . . . . . . . . . 1 . . . . 1 . 1 1 2 2 . . 2 1 . . 1 .[0X [4X . . . . . . . . . . 1 . . . . 1 . 1 1 2 2 . . 2 1 . . 1[0X [4X . . . . . . . . . . . 1 . . 1 . 1 . 1 1 2 2 . . 2 1 . .[0X [4X . . . . . . . . . . . . 1 . 1 1 . 1 . 1 1 . 2 . . 2 1 .[0X [4X . . . . . . . . . . . . . 1 2 1 1 . 1 . 1 . . 2 . . 2 1[0X [4Xgap> ax:=PolyCodeword(Codeword("013131000", GF(7)));[0X [4Xx_1^5+Z(7)*x_1^4+x_1^3+Z(7)*x_1^2+x_1[0X [4Xgap> bx:=PolyCodeword(Codeword("425435030", GF(7)));[0X [4XZ(7)*x_1^7+Z(7)^5*x_1^5+Z(7)*x_1^4+Z(7)^4*x_1^3+Z(7)^5*x_1^2+Z(7)^2*x_1+Z(7)^4[0X [4Xgap> C:=FourNegacirculantSelfDualCodeNC(ax, bx, 18);[0X [4Xa linear [36,18,1..13]0..36 four-negacirculant self-dual code over GF(7)[0X [4Xgap> IsSelfDualCode(C);[0X [4Xtrue[0X [4X------------------------------------------------------------------[0X [1X5.5-19 FourNegacirculantSelfDualCodeNC[0X [2X> FourNegacirculantSelfDualCodeNC( [0X[3Xax, bx, k[0X[2X ) _____________________[0Xfunction This function is the same as [10XFourNegacirculantSelfDualCode[0X, except this version is faster as it does not estimate the minimum distance and covering radius of the code. [1X5.6 Evaluation Codes[0X [1X5.6-1 EvaluationCode[0X [2X> EvaluationCode( [0X[3XP, L, R[0X[2X ) ________________________________________[0Xfunction Input: [3XF[0X is a finite field, [3XL[0X is a list of rational functions in R=F[x_1,...,x_r], [3XP[0X is a list of n points in F^r at which all of the functions in [3XL[0X are defined. Output: The 'evaluation code' C, which is the image of the evalation map Eval_P:span(L)\rightarrow F^n, given by flongmapsto (f(p_1),...,f(p_n)), where P=p_1,...,p_n and f in L. The generator matrix of C is G=(f_i(p_j))_f_iin L,p_jin P. This command returns a "record" object [10XC[0X with several extra components (type [10XNamesOfComponents(C)[0X to see them all): [10XC!.EvaluationMat[0X (not the same as the generator matrix in general), [10XC!.points[0X (namely [3XP[0X), [10XC!.basis[0X (namely [3XL[0X), and [10XC!.ring[0X (namely [3XR[0X). [4X--------------------------- Example ----------------------------[0X [4Xgap> F:=GF(11);[0X [4XGF(11)[0X [4Xgap> R := PolynomialRing(F,2);;[0X [4Xgap> indets := IndeterminatesOfPolynomialRing(R);;[0X [4Xgap> x:=indets[1];; y:=indets[2];;[0X [4Xgap> L:=[x^2*y,x*y,x^5,x^4,x^3,x^2,x,x^0];;[0X [4Xgap> Pts:=[ [ Z(11)^9, Z(11) ], [ Z(11)^8, Z(11) ], [ Z(11)^7, 0*Z(11) ],[0X [4X [ Z(11)^6, 0*Z(11) ], [ Z(11)^5, 0*Z(11) ], [ Z(11)^4, 0*Z(11) ],[0X [4X [ Z(11)^3, Z(11) ], [ Z(11)^2, 0*Z(11) ], [ Z(11), 0*Z(11) ], [0X [4X [ Z(11)^0, 0*Z(11) ], [ 0*Z(11), Z(11) ] ];;[0X [4Xgap> C:=EvaluationCode(Pts,L,R);[0X [4Xa linear [11,8,1..3]2..3 evaluation code over GF(11)[0X [4Xgap> MinimumDistance(C);[0X [4X3[0X [4X[0X [4X------------------------------------------------------------------[0X [1X5.6-2 GeneralizedReedSolomonCode[0X [2X> GeneralizedReedSolomonCode( [0X[3XP, k, R[0X[2X ) ____________________________[0Xfunction Input: R=F[x], where [3XF[0X is a finite field, [3Xk[0X is a positive integer, [3XP[0X is a list of n points in F. Output: The C which is the image of the evaluation map Eval_P:F[x]_k\rightarrow F^n, given by flongmapsto (f(p_1),...,f(p_n)), where P=p_1,...,p_nsubset F and f ranges over the space F[x]_k of all polynomials of degree less than k. This command returns a "record" object [10XC[0X with several extra components (type [10XNamesOfComponents(C)[0X to see them all): [10XC!.points[0X (namely [3XP[0X), [10XC!.degree[0X (namely [3Xk[0X), and [10XC!.ring[0X (namely [3XR[0X). This code can be decoded using [10XDecodeword[0X, which applies the special decoder method (the interpolation method), or using [10XGeneralizedReedSolomonDecoderGao[0X which applies an algorithm of S. Gao (see [2XGeneralizedReedSolomonDecoderGao[0X ([14X4.10-3[0X)). This code has a special decoder record which implements the interpolation algorithm described in section 5.2 of Justesen and Hoholdt [JH04]. See [2XDecode[0X ([14X4.10-1[0X) and [2XDecodeword[0X ([14X4.10-2[0X) for more details. The weighted version has implemented with the option [10XGeneralizedReedSolomonCode(P,k,R,wts)[0X, where wts = [v_1, ..., v_n] is a sequence of n non-zero elements from the base field F of [3XR[0X. See also the generalized Reed--Solomon code GRS_k(P, V) described in [MS83], p.303. The list-decoding algorithm of Sudan-Guraswami (described in section 12.1 of [JH04]) has been implemented for generalized Reed-Solomon codes. See [2XGeneralizedReedSolomonListDecoder[0X ([14X4.10-4[0X). [4X--------------------------- Example ----------------------------[0X [4Xgap> R:=PolynomialRing(GF(11),["t"]);[0X [4XGF(11)[t][0X [4Xgap> P:=List([1,3,4,5,7],i->Z(11)^i);[0X [4X[ Z(11), Z(11)^3, Z(11)^4, Z(11)^5, Z(11)^7 ][0X [4Xgap> C:=GeneralizedReedSolomonCode(P,3,R);[0X [4Xa linear [5,3,1..3]2 generalized Reed-Solomon code over GF(11)[0X [4Xgap> MinimumDistance(C);[0X [4X3[0X [4Xgap> V:=[Z(11)^0,Z(11)^0,Z(11)^0,Z(11)^0,Z(11)];[0X [4X[ Z(11)^0, Z(11)^0, Z(11)^0, Z(11)^0, Z(11) ][0X [4Xgap> C:=GeneralizedReedSolomonCode(P,3,R,V);[0X [4Xa linear [5,3,1..3]2 weighted generalized Reed-Solomon code over GF(11)[0X [4Xgap> MinimumDistance(C);[0X [4X3[0X [4X------------------------------------------------------------------[0X See [2XEvaluationCode[0X ([14X5.6-1[0X) for a more general construction. [1X5.6-3 GeneralizedReedMullerCode[0X [2X> GeneralizedReedMullerCode( [0X[3XPts, r, F[0X[2X ) ___________________________[0Xfunction [10XGeneralizedReedMullerCode[0X returns a 'Reed-Muller code' C with length |Pts| and order r. One considers (a) a basis of monomials for the vector space over F=GF(q) of all polynomials in F[x_1,...,x_d] of degree at most r, and (b) a set Pts of points in F^d. The generator matrix of the associated [13XReed-Muller code[0X C is G=(f(p))_fin B,p in Pts. This code C is constructed using the command [10XGeneralizedReedMullerCode(Pts,r,F)[0X. When Pts is the set of all q^d points in F^d then the command [10XGeneralizedReedMuller(d,r,F)[0X yields the code. When Pts is the set of all (q-1)^d points with no coordinate equal to 0 then this is can be constructed using the [10XToricCode[0X command (as a special case). This command returns a "record" object [10XC[0X with several extra components (type [10XNamesOfComponents(C)[0X to see them all): [10XC!.points[0X (namely [3XPts[0X) and [10XC!.degree[0X (namely [3Xr[0X). [4X--------------------------- Example ----------------------------[0X [4Xgap> Pts:=ToricPoints(2,GF(5));[0X [4X[ [ Z(5)^0, Z(5)^0 ], [ Z(5)^0, Z(5) ], [ Z(5)^0, Z(5)^2 ], [ Z(5)^0, Z(5)^3 ],[0X [4X [ Z(5), Z(5)^0 ], [ Z(5), Z(5) ], [ Z(5), Z(5)^2 ], [ Z(5), Z(5)^3 ],[0X [4X [ Z(5)^2, Z(5)^0 ], [ Z(5)^2, Z(5) ], [ Z(5)^2, Z(5)^2 ], [ Z(5)^2, Z(5)^3 ],[0X [4X [ Z(5)^3, Z(5)^0 ], [ Z(5)^3, Z(5) ], [ Z(5)^3, Z(5)^2 ], [ Z(5)^3, Z(5)^3 ] ][0X [4Xgap> C:=GeneralizedReedMullerCode(Pts,2,GF(5));[0X [4Xa linear [16,6,1..11]6..10 generalized Reed-Muller code over GF(5)[0X [4X------------------------------------------------------------------[0X See [2XEvaluationCode[0X ([14X5.6-1[0X) for a more general construction. [1X5.6-4 ToricPoints[0X [2X> ToricPoints( [0X[3Xn, F[0X[2X ) ______________________________________________[0Xfunction [10XToricPoints(n,F)[0X returns the points in (F^x)^n. [4X--------------------------- Example ----------------------------[0X [4Xgap> ToricPoints(2,GF(5));[0X [4X[ [ Z(5)^0, Z(5)^0 ], [ Z(5)^0, Z(5) ], [ Z(5)^0, Z(5)^2 ], [0X [4X [ Z(5)^0, Z(5)^3 ], [ Z(5), Z(5)^0 ], [ Z(5), Z(5) ], [ Z(5), Z(5)^2 ], [0X [4X [ Z(5), Z(5)^3 ], [ Z(5)^2, Z(5)^0 ], [ Z(5)^2, Z(5) ], [ Z(5)^2, Z(5)^2 ], [0X [4X [ Z(5)^2, Z(5)^3 ], [ Z(5)^3, Z(5)^0 ], [ Z(5)^3, Z(5) ], [0X [4X [ Z(5)^3, Z(5)^2 ], [ Z(5)^3, Z(5)^3 ] ][0X [4X------------------------------------------------------------------[0X [1X5.6-5 ToricCode[0X [2X> ToricCode( [0X[3XL, F[0X[2X ) ________________________________________________[0Xfunction This function returns the toric codes as in D. Joyner [Joy04] (see also J. P. Hansen [Han99]). This is a truncated (generalized) Reed-Muller code. Here [3XL[0X is a list of integral vectors and [3XF[0X is the finite field. The size of [3XF[0X must be different from 2. This command returns a record object [10XC[0X with an extra component (type [10XNamesOfComponents(C)[0X to see them all): [10XC!.exponents[0X (namely [3XL[0X). [4X--------------------------- Example ----------------------------[0X [4Xgap> C:=ToricCode([[1,0],[3,4]],GF(3));[0X [4Xa linear [4,1,4]2 toric code over GF(3)[0X [4Xgap> Display(GeneratorMat(C));[0X [4X 1 1 2 2[0X [4Xgap> Elements(C);[0X [4X[ [ 0 0 0 0 ], [ 1 1 2 2 ], [ 2 2 1 1 ] ][0X [4X------------------------------------------------------------------[0X See [2XEvaluationCode[0X ([14X5.6-1[0X) for a more general construction. [1X5.7 Algebraic geometric codes[0X Certain [5XGUAVA[0X functions related to algebraic geometric codes are described in this section. [1X5.7-1 AffineCurve[0X [2X> AffineCurve( [0X[3Xpoly, ring[0X[2X ) ________________________________________[0Xfunction This function simply defines the data structure of an affine plane curve. In [5XGUAVA[0X, an affine curve is a record [3Xcrv[0X having two components: a polynomial [3Xpoly[0X, accessed in [5XGUAVA[0X by [3Xcrv.polynomial[0X, and a polynomial ring over a field F in two variables [3Xring[0X, accessed in [5XGUAVA[0X by [3Xcrv.ring[0X, containing [3Xpoly[0X. You use this function to define a curve in [5XGUAVA[0X. For example, for the ring, one could take Q}[x,y], and for the polynomial one could take f(x,y)=x^2+y^2-1. For the affine line, simply taking Q}[x,y] for the ring and f(x,y)=y for the polynomial. (Not sure if F neeeds to be a field in fact ...) To compute its degree, simply use the [2XDegreeMultivariatePolynomial[0X ([14X7.6-2[0X) command. [4X--------------------------- Example ----------------------------[0X [4Xgap>[0X [4Xgap> F:=GF(11);;[0X [4Xgap> R2:=PolynomialRing(F,2);[0X [4XPolynomialRing(..., [ x_1, x_2 ])[0X [4Xgap> vars:=IndeterminatesOfPolynomialRing(R2);;[0X [4Xgap> x:=vars[1];; y:=vars[2];;[0X [4Xgap> poly:=y;; crvP1:=AffineCurve(poly,R2);[0X [4Xrec( ring := PolynomialRing(..., [ x_1, x_2 ]), polynomial := x_2 )[0X [4Xgap> degree_crv:=DegreeMultivariatePolynomial(poly,R2);[0X [4X1[0X [4Xgap> poly:=y^2-x*(x^2-1);; ell_crv:=AffineCurve(poly,R2);[0X [4Xrec( ring := PolynomialRing(..., [ x_1, x_2 ]), polynomial := -x_1^3+x_2^2+x_1 )[0X [4Xgap> degree_crv:=DegreeMultivariatePolynomial(poly,R2);[0X [4X3[0X [4Xgap> poly:=x^2+y^2-1;; circle:=AffineCurve(poly,R2);[0X [4Xrec( ring := PolynomialRing(..., [ x_1, x_2 ]), polynomial := x_1^2+x_2^2-Z(11)^0 )[0X [4Xgap> degree_crv:=DegreeMultivariatePolynomial(poly,R2);[0X [4X2[0X [4Xgap> q:=3;;[0X [4Xgap> F:=GF(q^2);;[0X [4Xgap> R:=PolynomialRing(F,2);;[0X [4Xgap> vars:=IndeterminatesOfPolynomialRing(R);[0X [4X[ x_1, x_2 ][0X [4Xgap> x:=vars[1];[0X [4Xx_1[0X [4Xgap> y:=vars[2];[0X [4Xx_2[0X [4Xgap> crv:=AffineCurve(y^q+y-x^(q+1),R);[0X [4Xrec( ring := PolynomialRing(..., [ x_1, x_2 ]), polynomial := -x_1^4+x_2^3+x_2 )[0X [4Xgap>[0X [4X------------------------------------------------------------------[0X In GAP, a [13Xpoint[0X on a curve defined by f(x,y)=0 is simply a list [3X[a,b][0X of elements of F satisfying this polynomial equation. [1X5.7-2 AffinePointsOnCurve[0X [2X> AffinePointsOnCurve( [0X[3Xf, R, E[0X[2X ) ___________________________________[0Xfunction [10XAffinePointsOnCurve(f,R,E)[0X returns the points (x,y) in E^2 satisying f(x,y)=0, where [3Xf[0X is an element of R=F[x,y]. [4X--------------------------- Example ----------------------------[0X [4Xgap> F:=GF(11);;[0X [4Xgap> R := PolynomialRing(F,["x","y"]);[0X [4XPolynomialRing(..., [ x, y ])[0X [4Xgap> indets := IndeterminatesOfPolynomialRing(R);;[0X [4Xgap> x:=indets[1];; y:=indets[2];;[0X [4Xgap> P:=AffinePointsOnCurve(y^2-x^11+x,R,F);[0X [4X[ [ Z(11)^9, 0*Z(11) ], [ Z(11)^8, 0*Z(11) ], [ Z(11)^7, 0*Z(11) ], [0X [4X [ Z(11)^6, 0*Z(11) ], [ Z(11)^5, 0*Z(11) ], [ Z(11)^4, 0*Z(11) ], [0X [4X [ Z(11)^3, 0*Z(11) ], [ Z(11)^2, 0*Z(11) ], [ Z(11), 0*Z(11) ], [0X [4X [ Z(11)^0, 0*Z(11) ], [ 0*Z(11), 0*Z(11) ] ][0X [4X------------------------------------------------------------------[0X [1X5.7-3 GenusCurve[0X [2X> GenusCurve( [0X[3Xcrv[0X[2X ) ________________________________________________[0Xfunction If [3Xcrv[0X represents f(x,y)=0, where f is a polynomial of degree d, then this function simply returns (d-1)(d-2)/2. At the present, the function does not check if the curve is singular (in which case the result may be false). [4X--------------------------- Example ----------------------------[0X [4Xgap> q:=4;;[0X [4Xgap> F:=GF(q^2);;[0X [4Xgap> a:=X(F);;[0X [4Xgap> R1:=PolynomialRing(F,[a]);;[0X [4Xgap> var1:=IndeterminatesOfPolynomialRing(R1);;[0X [4Xgap> b:=X(F);;[0X [4Xgap> R2:=PolynomialRing(F,[a,b]);;[0X [4Xgap> var2:=IndeterminatesOfPolynomialRing(R2);;[0X [4Xgap> crv:=AffineCurve(b^q+b-a^(q+1),R2);;[0X [4Xgap> crv:=AffineCurve(b^q+b-a^(q+1),R2);[0X [4Xrec( ring := PolynomialRing(..., [ x_1, x_1 ]), polynomial := x_1^5+x_1^4+x_1 )[0X [4Xgap> GenusCurve(crv);[0X [4X36[0X [4X[0X [4X------------------------------------------------------------------[0X [1X5.7-4 GOrbitPoint [0X [2X> GOrbitPoint ( [0X[3XGP[0X[2X ) _______________________________________________[0Xfunction [3XP[0X must be a point in projective space P^n(F), [3XG[0X must be a finite subgroup of GL(n+1,F), This function returns all (representatives of projective) points in the orbit G* P. The example below computes the orbit of the automorphism group on the Klein quartic over the field GF(43) on the ``point at infinity''. [4X--------------------------- Example ----------------------------[0X [4Xgap> R:= PolynomialRing( GF(43), 3 );;[0X [4Xgap> vars:= IndeterminatesOfPolynomialRing(R);;[0X [4Xgap> x:= vars[1];; y:= vars[2];; z:= vars[3];;[0X [4Xgap> zz:=Z(43)^6;[0X [4XZ(43)^6[0X [4Xgap> zzz:=Z(43);[0X [4XZ(43)[0X [4Xgap> rho1:=zz^0*[[zz^4,0,0],[0,zz^2,0],[0,0,zz]];[0X [4X[ [ Z(43)^24, 0*Z(43), 0*Z(43) ], [0X [4X[ 0*Z(43), Z(43)^12, 0*Z(43) ], [0X [4X[ 0*Z(43), 0*Z(43), Z(43)^6 ] ][0X [4Xgap> rho2:=zz^0*[[0,1,0],[0,0,1],[1,0,0]];[0X [4X[ [ 0*Z(43), Z(43)^0, 0*Z(43) ], [0X [4X[ 0*Z(43), 0*Z(43), Z(43)^0 ], [0X [4X[ Z(43)^0, 0*Z(43), 0*Z(43) ] ][0X [4Xgap> rho3:=(-1)*[[(zz-zz^6 )/zzz^7,( zz^2-zz^5 )/ zzz^7, ( zz^4-zz^3 )/ zzz^7],[0X [4X> [( zz^2-zz^5 )/ zzz^7, ( zz^4-zz^3 )/ zzz^7, ( zz-zz^6 )/ zzz^7],[0X [4X> [( zz^4-zz^3 )/ zzz^7, ( zz-zz^6 )/ zzz^7, ( zz^2-zz^5 )/ zzz^7]];[0X [4X[ [ Z(43)^9, Z(43)^28, Z(43)^12 ], [0X [4X[ Z(43)^28, Z(43)^12, Z(43)^9 ], [0X [4X[ Z(43)^12, Z(43)^9, Z(43)^28 ] ][0X [4Xgap> G:=Group([rho1,rho2,rho3]);; #PSL(2,7)[0X [4Xgap> Size(G);[0X [4X168[0X [4Xgap> P:=[1,0,0]*zzz^0;[0X [4X[ Z(43)^0, 0*Z(43), 0*Z(43) ][0X [4Xgap> O:=GOrbitPoint(G,P);[0X [4X[ [ Z(43)^0, 0*Z(43), 0*Z(43) ], [ 0*Z(43), Z(43)^0, 0*Z(43) ], [0X [4X[ 0*Z(43), 0*Z(43), Z(43)^0 ], [ Z(43)^0, Z(43)^39, Z(43)^16 ], [0X [4X[ Z(43)^0, Z(43)^33, Z(43)^28 ], [ Z(43)^0, Z(43)^27, Z(43)^40 ],[0X [4X[ Z(43)^0, Z(43)^21, Z(43)^10 ], [ Z(43)^0, Z(43)^15, Z(43)^22 ], [0X [4X[ Z(43)^0, Z(43)^9, Z(43)^34 ], [ Z(43)^0, Z(43)^3, Z(43)^4 ], [0X [4X[ Z(43)^3, Z(43)^22, Z(43)^6 ], [ Z(43)^3, Z(43)^16, Z(43)^18 ],[0X [4X[ Z(43)^3, Z(43)^10, Z(43)^30 ], [ Z(43)^3, Z(43)^4, Z(43)^0 ], [0X [4X[ Z(43)^3, Z(43)^40, Z(43)^12 ], [ Z(43)^3, Z(43)^34, Z(43)^24 ], [0X [4X[ Z(43)^3, Z(43)^28, Z(43)^36 ], [ Z(43)^4, Z(43)^30, Z(43)^27 ],[0X [4X[ Z(43)^4, Z(43)^24, Z(43)^39 ], [ Z(43)^4, Z(43)^18, Z(43)^9 ], [0X [4X[ Z(43)^4, Z(43)^12, Z(43)^21 ], [ Z(43)^4, Z(43)^6, Z(43)^33 ], [0X [4X[ Z(43)^4, Z(43)^0, Z(43)^3 ], [ Z(43)^4, Z(43)^36, Z(43)^15 ] ][0X [4Xgap> Length(O);[0X [4X24[0X [4X[0X [4X------------------------------------------------------------------[0X Informally, a [13Xdivisor[0X on a curve is a formal integer linear combination of points on the curve, D=m_1P_1+...+m_kP_k, where the m_i are integers (the ``multiplicity'' of P_i in D) and P_i are (F-rational) points on the affine plane curve. In other words, a divisor is an element of the free abelian group generated by the F-rational affine points on the curve. The [13Xsupport[0X of a divisor D is simply the set of points which occurs in the sum defining D with non-zero ``multiplicity''. The data structure for a divisor on an affine plane curve is a record having the following components: -- the coefficients (the integer weights of the points in the support), -- the support, -- the curve, itself a record which has components: polynomial and polynomial ring. [1X5.7-5 DivisorOnAffineCurve[0X [2X> DivisorOnAffineCurve( [0X[3Xcdivsdivcrv[0X[2X ) ______________________________[0Xfunction This is the command you use to define a divisor in [5XGUAVA[0X. Of course, [3Xcrv[0X is the curve on which the divisor lives, [3Xcdiv[0X is the list of coefficients (or ``multiplicities''), [3Xsdiv[0X is the list of points on [3Xcrv[0X in the support. [4X--------------------------- Example ----------------------------[0X [4Xgap> q:=5;[0X [4X5[0X [4Xgap> F:=GF(q);[0X [4XGF(5)[0X [4Xgap> R:=PolynomialRing(F,2);;[0X [4Xgap> vars:=IndeterminatesOfPolynomialRing(R);[0X [4X[ x_1, x_2 ][0X [4Xgap> x:=vars[1];[0X [4Xx_1[0X [4Xgap> y:=vars[2];[0X [4Xx_2[0X [4Xgap> crv:=AffineCurve(y^3-x^3-x-1,R);[0X [4Xrec( ring := PolynomialRing(..., [ x_1, x_2 ]), [0X [4X polynomial := -x_1^3+x_2^3-x_1-Z(5)^0 )[0X [4Xgap> Pts:=AffinePointsOnCurve(crv,R,F);;[0X [4Xgap> supp:=[Pts[1],Pts[2]];[0X [4X[ [ 0*Z(5), Z(5)^0 ], [ Z(5)^0, Z(5) ] ][0X [4Xgap> D:=DivisorOnAffineCurve([1,-1],supp,crv);[0X [4Xrec( coeffs := [ 1, -1 ], [0X [4X support := [ [ 0*Z(5), Z(5)^0 ], [ Z(5)^0, Z(5) ] ],[0X [4X curve := rec( ring := PolynomialRing(..., [ x_1, x_2 ]), [0X [4X polynomial := -x_1^3+x_2^3-x_1-Z(5)^0 ) )[0X [4X[0X [4X------------------------------------------------------------------[0X [1X5.7-6 DivisorAddition [0X [2X> DivisorAddition ( [0X[3XD1D2[0X[2X ) _________________________________________[0Xfunction If D_1=m_1P_1+...+m_kP_k and D_2=n_1P_1+...+n_kP_k are divisors then D_1+D_2=(m_1+n_1)P_1+...+(m_k+n_k)P_k. [1X5.7-7 DivisorDegree [0X [2X> DivisorDegree ( [0X[3XD[0X[2X ) ______________________________________________[0Xfunction If D=m_1P_1+...+m_kP_k is a divisor then the [13Xdegree[0X is m_1+...+m_k. [1X5.7-8 DivisorNegate [0X [2X> DivisorNegate ( [0X[3XD[0X[2X ) ______________________________________________[0Xfunction Self-explanatory. [1X5.7-9 DivisorIsZero [0X [2X> DivisorIsZero ( [0X[3XD[0X[2X ) ______________________________________________[0Xfunction Self-explanatory. [1X5.7-10 DivisorsEqual [0X [2X> DivisorsEqual ( [0X[3XD1D2[0X[2X ) ___________________________________________[0Xfunction Self-explanatory. [1X5.7-11 DivisorGCD [0X [2X> DivisorGCD ( [0X[3XD1D2[0X[2X ) ______________________________________________[0Xfunction If m=p_1^e_1...p_k^e_k and n=p_1^f_1...p_k^f_k are two integers then their greatest common divisor is GCD(m,n)=p_1^min(e_1,f_1)...p_k^min(e_k,f_k). A similar definition works for two divisors on a curve. If D_1=e_1P_1+...+e_kP_k and D_2n=f_1P_1+...+f_kP_k are two divisors on a curve then their [13Xgreatest common divisor[0X is GCD(m,n)=min(e_1,f_1)P_1+...+min(e_k,f_k)P_k. This function computes this quantity. [1X5.7-12 DivisorLCM [0X [2X> DivisorLCM ( [0X[3XD1D2[0X[2X ) ______________________________________________[0Xfunction If m=p_1^e_1...p_k^e_k and n=p_1^f_1...p_k^f_k are two integers then their least common multiple is LCM(m,n)=p_1^max(e_1,f_1)...p_k^max(e_k,f_k). A similar definition works for two divisors on a curve. If D_1=e_1P_1+...+e_kP_k and D_2=f_1P_1+...+f_kP_k are two divisors on a curve then their [13Xleast common multiple[0X is LCM(m,n)=max(e_1,f_1)P_1+...+max(e_k,f_k)P_k. This function computes this quantity. [4X--------------------------- Example ----------------------------[0X [4Xgap> F:=GF(11);[0X [4XGF(11)[0X [4Xgap> R1:=PolynomialRing(F,["a"]);;[0X [4Xgap> var1:=IndeterminatesOfPolynomialRing(R1);; a:=var1[1];;[0X [4Xgap> b:=X(F,"b",var1);[0X [4Xb[0X [4Xgap> var2:=Concatenation(var1,[b]);[0X [4X[ a, b ][0X [4Xgap> R2:=PolynomialRing(F,var2);[0X [4XPolynomialRing(..., [ a, b ])[0X [4Xgap> crvP1:=AffineCurve(b,R2);[0X [4Xrec( ring := PolynomialRing(..., [ a, b ]), polynomial := b )[0X [4Xgap> div1:=DivisorOnAffineCurve([1,2,3,4],[Z(11)^2,Z(11)^3,Z(11)^7,Z(11)],crvP1);[0X [4Xrec( coeffs := [ 1, 2, 3, 4 ], [0X [4X support := [ Z(11)^2, Z(11)^3, Z(11)^7, Z(11) ], [0X [4X curve := rec( ring := PolynomialRing(..., [ a, b ]), polynomial := b ) )[0X [4Xgap> DivisorDegree(div1);[0X [4X10[0X [4Xgap> div2:=DivisorOnAffineCurve([1,2,3,4],[Z(11),Z(11)^2,Z(11)^3,Z(11)^4],crvP1);[0X [4Xrec( coeffs := [ 1, 2, 3, 4 ], [0X [4X support := [ Z(11), Z(11)^2, Z(11)^3, Z(11)^4 ], [0X [4X curve := rec( ring := PolynomialRing(..., [ a, b ]), polynomial := b ) )[0X [4Xgap> DivisorDegree(div2);[0X [4X10[0X [4Xgap> div3:=DivisorAddition(div1,div2);[0X [4Xrec( coeffs := [ 5, 3, 5, 4, 3 ], [0X [4X support := [ Z(11), Z(11)^2, Z(11)^3, Z(11)^4, Z(11)^7 ], [0X [4X curve := rec( ring := PolynomialRing(..., [ a, b ]), polynomial := b ) )[0X [4Xgap> DivisorDegree(div3);[0X [4X20[0X [4Xgap> DivisorIsEffective(div1);[0X [4Xtrue[0X [4Xgap> DivisorIsEffective(div2);[0X [4Xtrue[0X [4Xgap>[0X [4Xgap> ndiv1:=DivisorNegate(div1);[0X [4Xrec( coeffs := [ -1, -2, -3, -4 ], [0X [4X support := [ Z(11)^2, Z(11)^3, Z(11)^7, Z(11) ], [0X [4X curve := rec( ring := PolynomialRing(..., [ a, b ]), polynomial := b ) )[0X [4Xgap> zdiv:=DivisorAddition(div1,ndiv1);[0X [4Xrec( coeffs := [ 0, 0, 0, 0 ], [0X [4X support := [ Z(11), Z(11)^2, Z(11)^3, Z(11)^7 ], [0X [4X curve := rec( ring := PolynomialRing(..., [ a, b ]), polynomial := b ) )[0X [4Xgap> DivisorIsZero(zdiv);[0X [4Xtrue[0X [4Xgap> div_gcd:=DivisorGCD(div1,div2);[0X [4Xrec( coeffs := [ 1, 1, 2, 0, 0 ], [0X [4X support := [ Z(11), Z(11)^2, Z(11)^3, Z(11)^4, Z(11)^7 ], [0X [4X curve := rec( ring := PolynomialRing(..., [ a, b ]), polynomial := b ) )[0X [4Xgap> div_lcm:=DivisorLCM(div1,div2);[0X [4Xrec( coeffs := [ 4, 2, 3, 4, 3 ], [0X [4X support := [ Z(11), Z(11)^2, Z(11)^3, Z(11)^4, Z(11)^7 ], [0X [4X curve := rec( ring := PolynomialRing(..., [ a, b ]), polynomial := b ) )[0X [4Xgap> DivisorDegree(div_gcd);[0X [4X4[0X [4Xgap> DivisorDegree(div_lcm);[0X [4X16[0X [4Xgap> DivisorEqual(div3,DivisorAddition(div_gcd,div_lcm));[0X [4Xtrue[0X [4X[0X [4X------------------------------------------------------------------[0X Let G denote a finite subgroup of PGL(2,F) and let D denote a divisor on the projective line P^1(F). If G leaves D unchanged (it may permute the points in the support of D but must preserve their sum in D) then the Riemann-Roch space L(D) is a G-module. The commands in this section help explore the G-module structure of L(D) in the case then the ground field F is finite. [1X5.7-13 RiemannRochSpaceBasisFunctionP1 [0X [2X> RiemannRochSpaceBasisFunctionP1 ( [0X[3XPkR2[0X[2X ) _________________________[0Xfunction Input: [3XR2[0X is a polynomial ring in two variables, say F[x,y]; [3XP[0X is an element of the base field, say F; [3Xk[0X is an integer. Output: 1/(x-P)^k [1X5.7-14 DivisorOfRationalFunctionP1 [0X [2X> DivisorOfRationalFunctionP1 ( [0X[3Xf, R[0X[2X ) _____________________________[0Xfunction Here R = F[x,y] is a polynomial ring in the variables x,y and f is a rational function of x. Simply returns the principal divisor on P}^1 associated to f. [4X--------------------------- Example ----------------------------[0X [4X[0X [4Xgap> F:=GF(11);[0X [4XGF(11)[0X [4Xgap> R1:=PolynomialRing(F,["a"]);;[0X [4Xgap> var1:=IndeterminatesOfPolynomialRing(R1);; a:=var1[1];;[0X [4Xgap> b:=X(F,"b",var1);[0X [4Xb[0X [4Xgap> var2:=Concatenation(var1,[b]);[0X [4X[ a, b ][0X [4Xgap> R2:=PolynomialRing(F,var2);[0X [4XPolynomialRing(..., [ a, b ])[0X [4Xgap> pt:=Z(11);[0X [4XZ(11)[0X [4Xgap> f:=RiemannRochSpaceBasisFunctionP1(pt,2,R2);[0X [4X(Z(11)^0)/(a^2+Z(11)^7*a+Z(11)^2)[0X [4Xgap> Df:=DivisorOfRationalFunctionP1(f,R2);[0X [4Xrec( coeffs := [ -2 ], support := [ Z(11) ], [0X [4X curve := rec( ring := PolynomialRing(..., [ a, b ]), polynomial := a )[0X [4X )[0X [4Xgap> Df.support;[0X [4X[ Z(11) ][0X [4Xgap> F:=GF(11);;[0X [4Xgap> R:=PolynomialRing(F,2);;[0X [4Xgap> vars:=IndeterminatesOfPolynomialRing(R);;[0X [4Xgap> a:=vars[1];;[0X [4Xgap> b:=vars[2];;[0X [4Xgap> f:=(a^4+Z(11)^6*a^3-a^2+Z(11)^7*a+Z(11)^0)/(a^4+Z(11)*a^2+Z(11)^7*a+Z(11));;[0X [4Xgap> divf:=DivisorOfRationalFunctionP1(f,R);[0X [4Xrec( coeffs := [ 3, 1 ], support := [ Z(11), Z(11)^7 ],[0X [4X curve := rec( ring := PolynomialRing(..., [ a, b ]), polynomial := a ) )[0X [4Xgap> denf:=DenominatorOfRationalFunction(f); RootsOfUPol(denf);[0X [4Xa^4+Z(11)*a^2+Z(11)^7*a+Z(11)[0X [4X[ ][0X [4Xgap> numf:=NumeratorOfRationalFunction(f); RootsOfUPol(numf);[0X [4Xa^4+Z(11)^6*a^3-a^2+Z(11)^7*a+Z(11)^0[0X [4X[ Z(11)^7, Z(11), Z(11), Z(11) ][0X [4X[0X [4X------------------------------------------------------------------[0X [1X5.7-15 RiemannRochSpaceBasisP1 [0X [2X> RiemannRochSpaceBasisP1 ( [0X[3XD[0X[2X ) ____________________________________[0Xfunction This returns the basis of the Riemann-Roch space L(D) associated to the divisor [3XD[0X on the projective line P}^1. [4X--------------------------- Example ----------------------------[0X [4Xgap> F:=GF(11);[0X [4XGF(11)[0X [4Xgap> R1:=PolynomialRing(F,["a"]);;[0X [4Xgap> var1:=IndeterminatesOfPolynomialRing(R1);; a:=var1[1];;[0X [4Xgap> b:=X(F,"b",var1);[0X [4Xb[0X [4Xgap> var2:=Concatenation(var1,[b]);[0X [4X[ a, b ][0X [4Xgap> R2:=PolynomialRing(F,var2);[0X [4XPolynomialRing(..., [ a, b ])[0X [4Xgap> crvP1:=AffineCurve(b,R2);[0X [4Xrec( ring := PolynomialRing(..., [ a, b ]), polynomial := b )[0X [4Xgap> D:=DivisorOnAffineCurve([1,2,3,4],[Z(11)^2,Z(11)^3,Z(11)^7,Z(11)],crvP1);[0X [4Xrec( coeffs := [ 1, 2, 3, 4 ], [0X [4X support := [ Z(11)^2, Z(11)^3, Z(11)^7, Z(11) ], [0X [4X curve := rec( ring := PolynomialRing(..., [ a, b ]), polynomial := b ) )[0X [4Xgap> B:=RiemannRochSpaceBasisP1(D);[0X [4X[ Z(11)^0, (Z(11)^0)/(a+Z(11)^7), (Z(11)^0)/(a+Z(11)^8), [0X [4X(Z(11)^0)/(a^2+Z(11)^9*a+Z(11)^6), (Z(11)^0)/(a+Z(11)^2), [0X [4X(Z(11)^0)/(a^2+Z(11)^3*a+Z(11)^4), (Z(11)^0)/(a^3+a^2+Z(11)^2*a+Z(11)^6),[0X [4X (Z(11)^0)/(a+Z(11)^6), (Z(11)^0)/(a^2+Z(11)^7*a+Z(11)^2), [0X [4X(Z(11)^0)/(a^3+Z(11)^4*a^2+a+Z(11)^8), [0X [4X(Z(11)^0)/(a^4+Z(11)^8*a^3+Z(11)*a^2+a+Z(11)^4) ][0X [4Xgap> DivisorOfRationalFunctionP1(B[1],R2).support;[0X [4X[ ][0X [4Xgap> DivisorOfRationalFunctionP1(B[2],R2).support;[0X [4X[ Z(11)^2 ][0X [4Xgap> DivisorOfRationalFunctionP1(B[3],R2).support;[0X [4X[ Z(11)^3 ][0X [4Xgap> DivisorOfRationalFunctionP1(B[4],R2).support;[0X [4X[ Z(11)^3 ][0X [4Xgap> DivisorOfRationalFunctionP1(B[5],R2).support;[0X [4X[ Z(11)^7 ][0X [4Xgap> DivisorOfRationalFunctionP1(B[6],R2).support;[0X [4X[ Z(11)^7 ][0X [4Xgap> DivisorOfRationalFunctionP1(B[7],R2).support;[0X [4X[ Z(11)^7 ][0X [4Xgap> DivisorOfRationalFunctionP1(B[8],R2).support;[0X [4X[ Z(11) ][0X [4Xgap> DivisorOfRationalFunctionP1(B[9],R2).support;[0X [4X[ Z(11) ][0X [4Xgap> DivisorOfRationalFunctionP1(B[10],R2).support;[0X [4X[ Z(11) ][0X [4Xgap> DivisorOfRationalFunctionP1(B[11],R2).support;[0X [4X[ Z(11) ][0X [4X[0X [4X------------------------------------------------------------------[0X [1X5.7-16 MoebiusTransformation [0X [2X> MoebiusTransformation ( [0X[3XAR[0X[2X ) _____________________________________[0Xfunction The arguments are a 2x 2 matrix A with entries in a field F and a polynomial ring [3XR[0Xof one variable, say F[x]. This function returns the linear fractional transformatio associated to [3XA[0X. These transformations can be composed with each other using GAP's [10XValue[0X command. [1X5.7-17 ActionMoebiusTransformationOnFunction [0X [2X> ActionMoebiusTransformationOnFunction ( [0X[3XAfR2[0X[2X ) ___________________[0Xfunction The arguments are a 2x 2 matrix A with entries in a field F, a rational function [3Xf[0X of one variable, say in F(x), and a polynomial ring [3XR2[0X, say F[x,y]. This function simply returns the composition of the function [3Xf[0X with the Möbius transformation of [3XA[0X. [1X5.7-18 ActionMoebiusTransformationOnDivisorP1 [0X [2X> ActionMoebiusTransformationOnDivisorP1 ( [0X[3XAD[0X[2X ) ____________________[0Xfunction A Möbius transformation may be regarded as an automorphism of the projective line P^1. This function simply returns the image of the divisor [3XD[0X under the Möbius transformation defined by [3XA[0X, provided that [10XIsActionMoebiusTransformationOnDivisorDefinedP1(A,D)[0X returns true. [1X5.7-19 IsActionMoebiusTransformationOnDivisorDefinedP1 [0X [2X> IsActionMoebiusTransformationOnDivisorDefinedP1 ( [0X[3XAD[0X[2X ) ___________[0Xfunction Returns true of none of the points in the support of the divisor [3XD[0X is the pole of the Möbius transformation. [4X--------------------------- Example ----------------------------[0X [4Xgap> F:=GF(11);[0X [4XGF(11)[0X [4Xgap> R1:=PolynomialRing(F,["a"]);;[0X [4Xgap> var1:=IndeterminatesOfPolynomialRing(R1);; a:=var1[1];;[0X [4Xgap> b:=X(F,"b",var1);[0X [4Xb[0X [4Xgap> var2:=Concatenation(var1,[b]);[0X [4X[ a, b ][0X [4Xgap> R2:=PolynomialRing(F,var2);[0X [4XPolynomialRing(..., [ a, b ])[0X [4Xgap> crvP1:=AffineCurve(b,R2);[0X [4Xrec( ring := PolynomialRing(..., [ a, b ]), polynomial := b )[0X [4Xgap> D:=DivisorOnAffineCurve([1,2,3,4],[Z(11)^2,Z(11)^3,Z(11)^7,Z(11)],crvP1);[0X [4Xrec( coeffs := [ 1, 2, 3, 4 ], [0X [4X support := [ Z(11)^2, Z(11)^3, Z(11)^7, Z(11) ], [0X [4X curve := rec( ring := PolynomialRing(..., [ a, b ]), polynomial := b ) )[0X [4Xgap> A:=Z(11)^0*[[1,2],[1,4]];[0X [4X[ [ Z(11)^0, Z(11) ], [ Z(11)^0, Z(11)^2 ] ][0X [4Xgap> ActionMoebiusTransformationOnDivisorDefinedP1(A,D);[0X [4Xfalse[0X [4Xgap> A:=Z(11)^0*[[1,2],[3,4]];[0X [4X[ [ Z(11)^0, Z(11) ], [ Z(11)^8, Z(11)^2 ] ][0X [4Xgap> ActionMoebiusTransformationOnDivisorDefinedP1(A,D);[0X [4Xtrue[0X [4Xgap> ActionMoebiusTransformationOnDivisorP1(A,D);[0X [4Xrec( coeffs := [ 1, 2, 3, 4 ], [0X [4X support := [ Z(11)^5, Z(11)^6, Z(11)^8, Z(11)^7 ], [0X [4X curve := rec( ring := PolynomialRing(..., [ a, b ]), polynomial := b ) )[0X [4Xgap> f:=MoebiusTransformation(A,R1);[0X [4X(a+Z(11))/(Z(11)^8*a+Z(11)^2)[0X [4Xgap> ActionMoebiusTransformationOnFunction(A,f,R1);[0X [4X-Z(11)^0+Z(11)^3*a^-1[0X [4X[0X [4X------------------------------------------------------------------[0X [1X5.7-20 DivisorAutomorphismGroupP1 [0X [2X> DivisorAutomorphismGroupP1 ( [0X[3XD[0X[2X ) _________________________________[0Xfunction Input: A divisor [3XD[0X on P^1(F), where F is a finite field. Output: A subgroup Aut(D)subset Aut(P^1) preserving [3XD[0X. Very slow. [4X--------------------------- Example ----------------------------[0X [4Xgap> F:=GF(11);[0X [4XGF(11)[0X [4Xgap> R1:=PolynomialRing(F,["a"]);;[0X [4Xgap> var1:=IndeterminatesOfPolynomialRing(R1);; a:=var1[1];;[0X [4Xgap> b:=X(F,"b",var1);[0X [4Xb[0X [4Xgap> var2:=Concatenation(var1,[b]);[0X [4X[ a, b ][0X [4Xgap> R2:=PolynomialRing(F,var2);[0X [4XPolynomialRing(..., [ a, b ])[0X [4Xgap> crvP1:=AffineCurve(b,R2);[0X [4Xrec( ring := PolynomialRing(..., [ a, b ]), polynomial := b )[0X [4Xgap> D:=DivisorOnAffineCurve([1,2,3,4],[Z(11)^2,Z(11)^3,Z(11)^7,Z(11)],crvP1);[0X [4Xrec( coeffs := [ 1, 2, 3, 4 ], [0X [4X support := [ Z(11)^2, Z(11)^3, Z(11)^7, Z(11) ], [0X [4X curve := rec( ring := PolynomialRing(..., [ a, b ]), polynomial := b ) )[0X [4Xgap> agp:=DivisorAutomorphismGroupP1(D);; time;[0X [4X7305[0X [4Xgap> IdGroup(agp);[0X [4X[ 10, 2 ][0X [4X[0X [4X------------------------------------------------------------------[0X [1X5.7-21 MatrixRepresentationOnRiemannRochSpaceP1 [0X [2X> MatrixRepresentationOnRiemannRochSpaceP1 ( [0X[3XgD[0X[2X ) __________________[0Xfunction Input: An element [3Xg[0X in G, a subgroup of Aut(D)subset Aut(P^1), and a divisor [3XD[0X on P^1(F), where F is a finite field. Output: a dx d matrix, where d = dim, L(D), representing the action of [3Xg[0X on L(D). Note: [3Xg[0X sends L(D) to r* L(D), where r is a polynomial of degree 1 depending on [3Xg[0X and [3XD[0X. Also very slow. The GAP command [10XBrauerCharacterValue[0X can be used to ``lift'' the eigenvalues of this matrix to the complex numbers. [4X--------------------------- Example ----------------------------[0X [4Xgap> F:=GF(11);[0X [4XGF(11)[0X [4Xgap> R1:=PolynomialRing(F,["a"]);;[0X [4Xgap> var1:=IndeterminatesOfPolynomialRing(R1);; a:=var1[1];;[0X [4Xgap> b:=X(F,"b",var1);[0X [4Xb[0X [4Xgap> var2:=Concatenation(var1,[b]);[0X [4X[ a, b ][0X [4Xgap> R2:=PolynomialRing(F,var2);[0X [4XPolynomialRing(..., [ a, b ])[0X [4Xgap> crvP1:=AffineCurve(b,R2);[0X [4Xrec( ring := PolynomialRing(..., [ a, b ]), polynomial := b )[0X [4Xgap> D:=DivisorOnAffineCurve([1,1,1,4],[Z(11)^2,Z(11)^3,Z(11)^7,Z(11)],crvP1);[0X [4Xrec( coeffs := [ 1, 1, 1, 4 ], [0X [4X support := [ Z(11)^2, Z(11)^3, Z(11)^7, Z(11) ], [0X [4X curve := rec( ring := PolynomialRing(..., [ a, b ]), polynomial := b ) )[0X [4Xgap> agp:=DivisorAutomorphismGroupP1(D);; time;[0X [4X7198[0X [4Xgap> IdGroup(agp);[0X [4X[ 20, 5 ][0X [4Xgap> g:=Random(agp);[0X [4X[ [ Z(11)^4, Z(11)^9 ], [ Z(11)^0, Z(11)^9 ] ][0X [4Xgap> rho:=MatrixRepresentationOnRiemannRochSpaceP1(g,D);[0X [4X[ [ Z(11)^0, 0*Z(11), 0*Z(11), 0*Z(11), 0*Z(11), 0*Z(11), 0*Z(11), 0*Z(11) ], [0X [4X[ Z(11)^0, 0*Z(11), 0*Z(11), Z(11), 0*Z(11), 0*Z(11), 0*Z(11), 0*Z(11) ],[0X [4X [ Z(11)^7, 0*Z(11), Z(11)^5, 0*Z(11), 0*Z(11), 0*Z(11), 0*Z(11), 0*Z(11) ], [0X [4X[ Z(11)^4, Z(11)^9, 0*Z(11), 0*Z(11), 0*Z(11), 0*Z(11), 0*Z(11), 0*Z(11) ],[0X [4X [ Z(11)^2, 0*Z(11), 0*Z(11), 0*Z(11), Z(11)^5, 0*Z(11), 0*Z(11), 0*Z(11) ], [0X [4X[ Z(11)^4, 0*Z(11), 0*Z(11), 0*Z(11), Z(11)^8, Z(11)^0, 0*Z(11), 0*Z(11) ],[0X [4X [ Z(11)^6, 0*Z(11), 0*Z(11), 0*Z(11), Z(11)^7, Z(11)^0, Z(11)^5, 0*Z(11) ], [0X [4X[ Z(11)^8, 0*Z(11), 0*Z(11), 0*Z(11), Z(11)^3, Z(11)^3, Z(11)^9, Z(11)^0 ] ][0X [4Xgap> Display(rho);[0X [4X 1 . . . . . . .[0X [4X 1 . . 2 . . . .[0X [4X 7 . 10 . . . . .[0X [4X 5 6 . . . . . .[0X [4X 4 . . . 10 . . .[0X [4X 5 . . . 3 1 . .[0X [4X 9 . . . 7 1 10 .[0X [4X 3 . . . 8 8 6 1[0X [4X[0X [4X------------------------------------------------------------------[0X [1X5.7-22 GoppaCodeClassical[0X [2X> GoppaCodeClassical( [0X[3Xdiv, pts[0X[2X ) ___________________________________[0Xfunction Input: A divisor [3Xdiv[0X on the projective line P}^1(F) over a finite field F and a list [3Xpts[0X of points P_1,...,P_nsubset F disjoint from the support of [3Xdiv[0X. Output: The classical (evaluation) Goppa code associated to this data. This is the code C=\{(f(P_1),...,f(P_n))\ |\ f\in L(D)_F\}. [4X--------------------------- Example ----------------------------[0X [4Xgap> F:=GF(11);;[0X [4Xgap> R2:=PolynomialRing(F,2);;[0X [4Xgap> vars:=IndeterminatesOfPolynomialRing(R2);;[0X [4Xgap> a:=vars[1];;b:=vars[2];;[0X [4Xgap> cdiv:=[ 1, 2, -1, -2 ];[0X [4X[ 1, 2, -1, -2 ][0X [4Xgap> sdiv:=[ Z(11)^2, Z(11)^3, Z(11)^6, Z(11)^9 ];[0X [4X[ Z(11)^2, Z(11)^3, Z(11)^6, Z(11)^9 ][0X [4Xgap> crv:=rec(polynomial:=b,ring:=R2);[0X [4Xrec( polynomial := x_2, ring := PolynomialRing(..., [ x_1, x_2 ]) )[0X [4Xgap> div:=DivisorOnAffineCurve(cdiv,sdiv,crv);[0X [4Xrec( coeffs := [ 1, 2, -1, -2 ], support := [ Z(11)^2, Z(11)^3, Z(11)^6, Z(11)^9 ],[0X [4X curve := rec( polynomial := x_2, ring := PolynomialRing(..., [ x_1, x_2 ]) ) )[0X [4Xgap> pts:=Difference(Elements(GF(11)),div.support);[0X [4X[ 0*Z(11), Z(11)^0, Z(11), Z(11)^4, Z(11)^5, Z(11)^7, Z(11)^8 ][0X [4Xgap> C:=GoppaCodeClassical(div,pts);[0X [4Xa linear [7,2,1..6]4..5 code defined by generator matrix over GF(11)[0X [4Xgap> MinimumDistance(C);[0X [4X6[0X [4X------------------------------------------------------------------[0X [1X5.7-23 EvaluationBivariateCode[0X [2X> EvaluationBivariateCode( [0X[3Xpts, L, crv[0X[2X ) ___________________________[0Xfunction Input: [10Xpts[0X is a set of affine points on [10Xcrv[0X, [10XL[0X is a list of rational functions on [10Xcrv[0X. Output: The evaluation code associated to the points in [10Xpts[0X and functions in [10XL[0X, but specifically for affine plane curves and this function checks if points are "bad" (if so removes them from the list [10Xpts[0X automatically). A point is ``bad'' if either it does not lie on the set of non-singular F-rational points (places of degree 1) on the curve. Very similar to [10XEvaluationCode[0X (see [2XEvaluationCode[0X ([14X5.6-1[0X) for a more general construction). [1X5.7-24 EvaluationBivariateCodeNC[0X [2X> EvaluationBivariateCodeNC( [0X[3Xpts, L, crv[0X[2X ) _________________________[0Xfunction As in [10XEvaluationBivariateCode[0X but does not check if the points are ``bad''. Input: [10Xpts[0X is a set of affine points on [10Xcrv[0X, [10XL[0X is a list of rational functions on [10Xcrv[0X. Output: The evaluation code associated to the points in [10Xpts[0X and functions in [10XL[0X. [4X--------------------------- Example ----------------------------[0X [4Xgap> q:=4;;[0X [4Xgap> F:=GF(q^2);;[0X [4Xgap> R:=PolynomialRing(F,2);;[0X [4Xgap> vars:=IndeterminatesOfPolynomialRing(R);;[0X [4Xgap> x:=vars[1];;[0X [4Xgap> y:=vars[2];;[0X [4Xgap> crv:=AffineCurve(y^q+y-x^(q+1),R);[0X [4Xrec( ring := PolynomialRing(..., [ x_1, x_2 ]), polynomial := x_1^5+x_2^4+x_2 )[0X [4Xgap> L:=[ x^0, x, x^2*y^-1 ];[0X [4X[ Z(2)^0, x_1, x_1^2/x_2 ][0X [4Xgap> Pts:=AffinePointsOnCurve(crv.polynomial,crv.ring,F);;[0X [4Xgap> C1:=EvaluationBivariateCode(Pts,L,crv); time;[0X [4X[0X [4X[0X [4X Automatically removed the following 'bad' points (either a pole or not [0X [4X on the curve):[0X [4X[ [ 0*Z(2), 0*Z(2) ] ][0X [4X[0X [4Xa linear [63,3,1..60]51..59 evaluation code over GF(16)[0X [4X52[0X [4Xgap> P:=Difference(Pts,[[ 0*Z(2^4)^0, 0*Z(2)^0 ]]);;[0X [4Xgap> C2:=EvaluationBivariateCodeNC(P,L,crv); time;[0X [4Xa linear [63,3,1..60]51..59 evaluation code over GF(16)[0X [4X48[0X [4Xgap> C3:=EvaluationCode(P,L,R); time;[0X [4Xa linear [63,3,1..56]51..59 evaluation code over GF(16)[0X [4X58[0X [4Xgap> MinimumDistance(C1);[0X [4X56[0X [4Xgap> MinimumDistance(C2);[0X [4X56[0X [4Xgap> MinimumDistance(C3);[0X [4X56[0X [4Xgap>[0X [4X------------------------------------------------------------------[0X [1X5.7-25 OnePointAGCode[0X [2X> OnePointAGCode( [0X[3Xf, P, m, R[0X[2X ) _____________________________________[0Xfunction Input: [3Xf[0X is a polynomial in R=F[x,y], where [3XF[0X is a finite field, [3Xm[0X is a positive integer (the multiplicity of the `point at infinity' infty on the curve f(x,y)=0), [3XP[0X is a list of n points on the curve over F. Output: The C which is the image of the evaluation map Eval_P:L(m \cdot \infty)\rightarrow F^n, given by flongmapsto (f(p_1),...,f(p_n)), where p_i in P. Here L(m * infty) denotes the Riemann-Roch space of the divisor m * infty on the curve. This has a basis consisting of monomials x^iy^j, where (i,j) range over a polygon depending on m and f(x,y). For more details on the Riemann-Roch space of the divisor m * infty see Proposition III.10.5 in Stichtenoth [Sti93]. This command returns a "record" object [10XC[0X with several extra components (type [10XNamesOfComponents(C)[0X to see them all): [10XC!.points[0X (namely [3XP[0X), [10XC!.multiplicity[0X (namely [3Xm[0X), [10XC!.curve[0X (namely [3Xf[0X) and [10XC!.ring[0X (namely [3XR[0X). [4X--------------------------- Example ----------------------------[0X [4Xgap> F:=GF(11);[0X [4XGF(11)[0X [4Xgap> R := PolynomialRing(F,["x","y"]);[0X [4XPolynomialRing(..., [ x, y ])[0X [4Xgap> indets := IndeterminatesOfPolynomialRing(R);[0X [4X[ x, y ][0X [4Xgap> x:=indets[1]; y:=indets[2];[0X [4Xx[0X [4Xy[0X [4Xgap> P:=AffinePointsOnCurve(y^2-x^11+x,R,F);;[0X [4Xgap> C:=OnePointAGCode(y^2-x^11+x,P,15,R);[0X [4Xa linear [11,8,1..0]2..3 one-point AG code over GF(11)[0X [4Xgap> MinimumDistance(C);[0X [4X4[0X [4Xgap> Pts:=List([1,2,4,6,7,8,9,10,11],i->P[i]);;[0X [4Xgap> C:=OnePointAGCode(y^2-x^11+x,PT,10,R);[0X [4Xa linear [9,6,1..4]2..3 one-point AG code over GF(11)[0X [4Xgap> MinimumDistance(C);[0X [4X4[0X [4X------------------------------------------------------------------[0X See [2XEvaluationCode[0X ([14X5.6-1[0X) for a more general construction. [1X5.8 Low-Density Parity-Check Codes[0X Low-density parity-check (LDPC) codes form a class of linear block codes whose parity-check matrix--as the name implies, is sparse. LDPC codes were introduced by Robert Gallager in 1962 [Gal62] as his PhD work. Due to the decoding complexity for the technology back then, these codes were forgotten. Not until the late 1990s, these codes were rediscovered and research results have shown that LDPC codes can achieve near Shannon's capacity performance provided that their block length is long enough and soft-decision iterative decoder is employed. Note that the bit-flipping decoder (see [10XBitFlipDecoder[0X) is a hard-decision decoder and hence capacity achieving performance cannot be achieved despite having a large block length. Based on the structure of their parity-check matrix, LDPC codes may be categorised into two classes: -- Regular LDPC codes This class of codes has a fixed number of non zeros per column and per row in their parity-check matrix. These codes are usually denoted as (n,j,k) codes where n is the block length, j is the number of non zeros per column in their parity-check matrix and k is the number of non zeros per row in their parity-check matrix. -- Irregular LDPC codes The irregular codes, on the other hand, do not have a fixed number of non zeros per column and row in their parity-check matrix. This class of codes are commonly represented by two polynomials which denote the distribution of the number of non zeros in the columns and rows respectively of their parity-check matrix. [1X5.8-1 QCLDPCCodeFromGroup[0X [2X> QCLDPCCodeFromGroup( [0X[3Xm, j, k[0X[2X ) ___________________________________[0Xfunction [10XQCLDCCodeFromGroup[0X produces an (n,j,k) regular quasi-cyclic LDPC code over GF(2) of block length n = mk. The term quasi-cyclic in the context of LDPC codes typically refers to LDPC codes whose parity-check matrix H has the following form - - | I_P(0,0) | I_P(0,1) | ... | I_P(0,k-1) | | I_P(1,0) | I_P(1,1) | ... | I_P(1,k-1) | H = | . | . | . | . |, | . | . | . | . | | I_P(j-1,0) | I_P(j-1,1) | ... | I_P(j-1,k-1) | - - where I_P(s,t) is an identity matrix of size m x m which has been shifted so that the 1 on the first row starts at position P(s,t). Let F be a multiplicative group of integers modulo m. If m is a prime, F=0,1,...,m-1, otherwise F contains a set of integers which are relatively prime to m. In both cases, the order of F is equal to phi(m). Let a and b be non zeros of F such that the orders of a and b are k and j respectively. Note that the integers a and b can always be found provided that k and j respectively divide phi(m). Having obtain integers a and b, construct the following j x k matrix P so that the element at row s and column t is given by P(s,t) = a^tb^s, i.e. - - | 1 | a | . . . | a^{k-1} | | b | ab | . . . | a^{k-1}b | P = | . | . | . | . |. | . | . | . | . | | b^{j-1} | ab^{j-1} | . . . | a^{k-1}b^{j-1} | - - The parity-check matrix H of the LDPC code can be obtained by replacing each element of matrix P, i.e. P(s,t), with an identity matrix I_P(s,t) of size m x m. The code rate R of the constructed code is given by R \geq 1 - \frac{j}{k} where the sign >= is due to the possible existence of some non linearly independent rows in H. For more details, refer to the paper by Tanner et al [S}04]. [4X--------------------------- Example ----------------------------[0X [4Xgap> C := QCLDPCCodeFromGroup(7,2,3);[0X [4Xa linear [21,8,1..6]5..10 low-density parity-check code over GF(2)[0X [4Xgap> MinimumWeight(C);[0X [4X[21,8] linear code over GF(2) - minimum weight evaluation[0X [4XKnown lower-bound: 1[0X [4XThere are 3 generator matrices, ranks : 8 8 5 [0X [4XThe weight of the minimum weight codeword satisfies 0 mod 2 congruence[0X [4XEnumerating codewords with information weight 1 (w=1)[0X [4X Found new minimum weight 6[0X [4XNumber of matrices required for codeword enumeration 2[0X [4XCompleted w= 1, 24 codewords enumerated, lower-bound 4, upper-bound 6[0X [4XTermination expected with information weight 2 at matrix 1[0X [4X-----------------------------------------------------------------------------[0X [4XEnumerating codewords with information weight 2 (w=2) using 1 matrices[0X [4XCompleted w= 2, 28 codewords enumerated, lower-bound 6, upper-bound 6[0X [4X-----------------------------------------------------------------------------[0X [4XMinimum weight: 6[0X [4X6[0X [4Xgap> # The quasi-cyclic structure is obvious from the check matrix[0X [4Xgap> Display( CheckMat(C) );[0X [4X 1 . . . . . . . 1 . . . . . . . . 1 . . .[0X [4X . 1 . . . . . . . 1 . . . . . . . . 1 . .[0X [4X . . 1 . . . . . . . 1 . . . . . . . . 1 .[0X [4X . . . 1 . . . . . . . 1 . . . . . . . . 1[0X [4X . . . . 1 . . . . . . . 1 . 1 . . . . . .[0X [4X . . . . . 1 . . . . . . . 1 . 1 . . . . .[0X [4X . . . . . . 1 1 . . . . . . . . 1 . . . .[0X [4X . . . . . 1 . . . . . 1 . . . . 1 . . . .[0X [4X . . . . . . 1 . . . . . 1 . . . . 1 . . .[0X [4X 1 . . . . . . . . . . . . 1 . . . . 1 . .[0X [4X . 1 . . . . . 1 . . . . . . . . . . . 1 .[0X [4X . . 1 . . . . . 1 . . . . . . . . . . . 1[0X [4X . . . 1 . . . . . 1 . . . . 1 . . . . . .[0X [4X . . . . 1 . . . . . 1 . . . . 1 . . . . .[0X [4Xgap> # This is the famous [155,64,20] quasi-cyclic LDPC codes[0X [4Xgap> C := QCLDPCCodeFromGroup(31,3,5);[0X [4Xa linear [155,64,1..24]24..77 low-density parity-check code over GF(2)[0X [4Xgap> # An example using non prime m, it may take a while to construct this code[0X [4Xgap> C := QCLDPCCodeFromGroup(356,4,8);[0X [4Xa linear [2848,1436,1..120]312..1412 low-density parity-check code over GF(2)[0X [4X------------------------------------------------------------------[0X