[1X2. Coding theory functions in GAP[0X This chapter will recall from the GAP4.4.5 manual some of the GAP coding theory and finite field functions useful for coding theory. Some of these functions are partially written in C for speed. The main functions are -- [10XAClosestVectorCombinationsMatFFEVecFFE[0X, -- [10XAClosestVectorCombinationsMatFFEVecFFECoords[0X, -- [10XCosetLeadersMatFFE[0X, -- [10XDistancesDistributionMatFFEVecFFE[0X, -- [10XDistancesDistributionVecFFEsVecFFE[0X, -- [10XDistanceVecFFE[0X and [10XWeightVecFFE[0X, -- [10XConwayPolynomial[0X and [10XIsCheapConwayPolynomial[0X, -- [10XIsPrimitivePolynomial[0X, and [10XRandomPrimitivePolynomial[0X. However, the GAP command [10XPrimitivePolynomial[0X returns an integer primitive polynomial not the finite field kind. [1X2.1 Distance functions[0X [1X2.1-1 AClosestVectorCombinationsMatFFEVecFFE[0X [2X> AClosestVectorCombinationsMatFFEVecFFE( [0X[3Xmat, F, vec, r, st[0X[2X ) _____[0Xfunction This command runs through the [3XF[0X-linear combinations of the vectors in the rows of the matrix [3Xmat[0X that can be written as linear combinations of exactly [3Xr[0X rows (that is without using zero as a coefficient) and returns a vector from these that is closest to the vector [3Xvec[0X. The length of the rows of [3Xmat[0X and the length of [3Xvec[0X must be equal, and all elements must lie in [3XF[0X. The rows of [3Xmat[0X must be linearly independent. If it finds a vector of distance at most [3Xst[0X, which must be a nonnegative integer, then it stops immediately and returns this vector. [4X--------------------------- Example ----------------------------[0X [4Xgap> F:=GF(3);;[0X [4Xgap> x:= Indeterminate( F );; pol:= x^2+1;[0X [4Xx_1^2+Z(3)^0[0X [4Xgap> C := GeneratorPolCode(pol,8,F);[0X [4Xa cyclic [8,6,1..2]1..2 code defined by generator polynomial over GF(3)[0X [4Xgap> v:=Codeword("12101111");[0X [4X[ 1 2 1 0 1 1 1 1 ][0X [4Xgap> v:=VectorCodeword(v);[0X [4X[ Z(3)^0, Z(3), Z(3)^0, 0*Z(3), Z(3)^0, Z(3)^0, Z(3)^0, Z(3)^0 ][0X [4Xgap> G:=GeneratorMat(C);[0X [4X[ [ Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3) ],[0X [4X [ 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3) ],[0X [4X [ 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3) ],[0X [4X [ 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3) ],[0X [4X [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3) ],[0X [4X [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0 ] ][0X [4Xgap> AClosestVectorCombinationsMatFFEVecFFE(G,F,v,1,1);[0X [4X[ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0 ][0X [4X------------------------------------------------------------------[0X [1X2.1-2 AClosestVectorComb..MatFFEVecFFECoords[0X [2X> AClosestVectorComb..MatFFEVecFFECoords( [0X[3Xmat, F, vec, r, st[0X[2X ) _____[0Xfunction [10XAClosestVectorCombinationsMatFFEVecFFECoords[0X returns a two element list containing (a) the same closest vector as in [10XAClosestVectorCombinationsMatFFEVecFFE[0X, and (b) a vector [3Xv[0X with exactly [3Xr[0X non-zero entries, such that v*mat is the closest vector. [4X--------------------------- Example ----------------------------[0X [4Xgap> F:=GF(3);;[0X [4Xgap> x:= Indeterminate( F );; pol:= x^2+1;[0X [4Xx_1^2+Z(3)^0[0X [4Xgap> C := GeneratorPolCode(pol,8,F);[0X [4Xa cyclic [8,6,1..2]1..2 code defined by generator polynomial over GF(3)[0X [4Xgap> v:=Codeword("12101111"); v:=VectorCodeword(v);;[0X [4X[ 1 2 1 0 1 1 1 1 ][0X [4Xgap> G:=GeneratorMat(C);;[0X [4Xgap> AClosestVectorCombinationsMatFFEVecFFECoords(G,F,v,1,1);[0X [4X[ [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0 ],[0X [4X [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0 ] ][0X [4X------------------------------------------------------------------[0X [1X2.1-3 DistancesDistributionMatFFEVecFFE[0X [2X> DistancesDistributionMatFFEVecFFE( [0X[3Xmat, f, vec[0X[2X ) _________________[0Xfunction [10XDistancesDistributionMatFFEVecFFE[0X returns the distances distribution of the vector [3Xvec[0X to the vectors in the vector space generated by the rows of the matrix [3Xmat[0X over the finite field [3Xf[0X. All vectors must have the same length, and all elements must lie in a common field. The distances distribution is a list d of length Length(vec)+1, such that the value d[i] is the number of vectors in vecs that have distance i+1 to [3Xvec[0X. [4X--------------------------- Example ----------------------------[0X [4Xgap> v:=[ Z(3)^0, Z(3), Z(3)^0, 0*Z(3), Z(3)^0, Z(3)^0, Z(3)^0, Z(3)^0 ];;[0X [4Xgap> vecs:=[ [ Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3) ],[0X [4X> [ 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3) ],[0X [4X> [ 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3) ],[0X [4X> [ 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3) ],[0X [4X> [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3) ],[0X [4X> [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0 ] ];;[0X [4Xgap> DistancesDistributionMatFFEVecFFE(vecs,GF(3),v);[0X [4X[ 0, 4, 6, 60, 109, 216, 192, 112, 30 ][0X [4X------------------------------------------------------------------[0X [1X2.1-4 DistancesDistributionVecFFEsVecFFE[0X [2X> DistancesDistributionVecFFEsVecFFE( [0X[3Xvecs, vec[0X[2X ) __________________[0Xfunction [10XDistancesDistributionVecFFEsVecFFE[0X returns the distances distribution of the vector [3Xvec[0X to the vectors in the list [3Xvecs[0X. All vectors must have the same length, and all elements must lie in a common field. The distances distribution is a list d of length Length(vec)+1, such that the value d[i] is the number of vectors in [3Xvecs[0X that have distance i+1 to [3Xvec[0X. [4X--------------------------- Example ----------------------------[0X [4Xgap> v:=[ Z(3)^0, Z(3), Z(3)^0, 0*Z(3), Z(3)^0, Z(3)^0, Z(3)^0, Z(3)^0 ];;[0X [4Xgap> vecs:=[ [ Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3) ],[0X [4X> [ 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3) ],[0X [4X> [ 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3) ],[0X [4X> [ 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3) ],[0X [4X> [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3) ],[0X [4X> [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0 ] ];;[0X [4Xgap> DistancesDistributionVecFFEsVecFFE(vecs,v);[0X [4X[ 0, 0, 0, 0, 0, 4, 0, 1, 1 ][0X [4X------------------------------------------------------------------[0X [1X2.1-5 WeightVecFFE[0X [2X> WeightVecFFE( [0X[3Xvec[0X[2X ) ______________________________________________[0Xfunction [10XWeightVecFFE[0X returns the weight of the finite field vector [3Xvec[0X, i.e. the number of nonzero entries. [4X--------------------------- Example ----------------------------[0X [4Xgap> v:=[ Z(3)^0, Z(3), Z(3)^0, 0*Z(3), Z(3)^0, Z(3)^0, Z(3)^0, Z(3)^0 ];;[0X [4Xgap> WeightVecFFE(v);[0X [4X7[0X [4X------------------------------------------------------------------[0X [1X2.1-6 DistanceVecFFE[0X [2X> DistanceVecFFE( [0X[3Xvec1, vec2[0X[2X ) _____________________________________[0Xfunction The [13XHamming metric[0X on GF(q)^n is the function dist((v_1,...,v_n),(w_1,...,w_n)) =|\{i\in [1..n]\ |\ v_i\not= w_i\}|. This is also called the (Hamming) distance between v=(v_1,...,v_n) and w=(w_1,...,w_n). [10XDistanceVecFFE[0X returns the distance between the two vectors [3Xvec1[0X and [3Xvec2[0X, which must have the same length and whose elements must lie in a common field. The distance is the number of places where [3Xvec1[0X and [3Xvec2[0X differ. [4X--------------------------- Example ----------------------------[0X [4Xgap> v1:=[ Z(3)^0, Z(3), Z(3)^0, 0*Z(3), Z(3)^0, Z(3)^0, Z(3)^0, Z(3)^0 ];;[0X [4Xgap> v2:=[ Z(3), Z(3)^0, Z(3)^0, 0*Z(3), Z(3)^0, Z(3)^0, Z(3)^0, Z(3)^0 ];;[0X [4Xgap> DistanceVecFFE(v1,v2);[0X [4X2[0X [4X------------------------------------------------------------------[0X [1X2.2 Other functions[0X We basically repeat, with minor variation, the material in the GAP manual or from Frank Luebeck's website [7Xhttp://www.math.rwth-aachen.de:8001/~Frank.Luebeck/data/ConwayPol[0X on Conway polynomials. The [12Xprime fields[0X: If p>= 2 is a prime then GF(p) denotes the field Z}/pZ}, with addition and multiplication performed mod p. The [12Xprime power fields[0X: Suppose q=p^r is a prime power, r>1, and put F=GF(p). Let F[x] denote the ring of all polynomials over F and let f(x) denote a monic irreducible polynomial in F[x] of degree r. The quotient E = F[x]/(f(x))= F[x]/f(x)F[x] is a field with q elements. If f(x) and E are related in this way, we say that f(x) is the [12Xdefining polynomial[0X of E. Any defining polynomial factors completely into distinct linear factors over the field it defines. For any finite field F, the multiplicative group of non-zero elements F^x is a cyclic group. An alpha in F is called a [12Xprimitive element[0X if it is a generator of F^x. A defining polynomial f(x) of F is said to be [12Xprimitive[0X if it has a root in F which is a primitive element. [1X2.2-1 ConwayPolynomial[0X [2X> ConwayPolynomial( [0X[3Xp, n[0X[2X ) _________________________________________[0Xfunction A standard notation for the elements of GF(p) is given via the representatives 0, ..., p-1 of the cosets modulo p. We order these elements by 0 < 1 < 2 < ... < p-1. We introduce an ordering of the polynomials of degree r over GF(p). Let g(x) = g_rx^r + ... + g_0 and h(x) = h_rx^r + ... + h_0 (by convention, g_i=h_i=0 for i > r). Then we define g < h if and only if there is an index k with g_i = h_i for i > k and (-1)^r-k g_k < (-1)^r-k h_k. The [12XConway polynomial[0X f_p,r(x) for GF(p^r) is the smallest polynomial of degree r with respect to this ordering such that: -- f_p,r(x) is monic, -- f_p,r(x) is primitive, that is, any zero is a generator of the (cyclic) multiplicative group of GF(p^r), -- for each proper divisor m of r we have that f_p,m(x^(p^r-1) / (p^m-1)) = 0 mod f_p,r(x); that is, the (p^r-1) / (p^m-1)-th power of a zero of f_p,r(x) is a zero of f_p,m(x). [10XConwayPolynomial(p,n)[0X returns the polynomial f_p,r(x) defined above. [10XIsCheapConwayPolynomial(p,n)[0X returns true if [10XConwayPolynomial( p, n )[0X will give a result in reasonable time. This is either the case when this polynomial is pre-computed, or if n,p are not too big. [1X2.2-2 RandomPrimitivePolynomial[0X [2X> RandomPrimitivePolynomial( [0X[3XF, n[0X[2X ) ________________________________[0Xfunction For a finite field [3XF[0X and a positive integer [3Xn[0X this function returns a primitive polynomial of degree [3Xn[0X over [3XF[0X, that is a zero of this polynomial has maximal multiplicative order |F|^n-1. [10XIsPrimitivePolynomial(f)[0X can be used to check if a univariate polynomial [3Xf[0X is primitive or not.