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
AClosestVectorCombinationsMatFFEVecFFE,
AClosestVectorCombinationsMatFFEVecFFECoords,
CosetLeadersMatFFE,
DistancesDistributionMatFFEVecFFE,
DistancesDistributionVecFFEsVecFFE,
DistanceVecFFE and WeightVecFFE,
ConwayPolynomial and IsCheapConwayPolynomial,
IsPrimitivePolynomial, and RandomPrimitivePolynomial.
However, the GAP command PrimitivePolynomial returns an integer primitive polynomial not the finite field kind.
‣ AClosestVectorCombinationsMatFFEVecFFE( mat, F, vec, r, st ) | ( function ) |
This command runs through the F-linear combinations of the vectors in the rows of the matrix mat that can be written as linear combinations of exactly r rows (that is without using zero as a coefficient) and returns a vector from these that is closest to the vector vec. The length of the rows of mat and the length of vec must be equal, and all elements must lie in F. The rows of mat must be linearly independent. If it finds a vector of distance at most st, which must be a nonnegative integer, then it stops immediately and returns this vector.
gap> F:=GF(3);; gap> x:= Indeterminate( F );; pol:= x^2+1; x_1^2+Z(3)^0 gap> C := GeneratorPolCode(pol,8,F); a cyclic [8,6,1..2]1..2 code defined by generator polynomial over GF(3) gap> v:=Codeword("12101111"); [ 1 2 1 0 1 1 1 1 ] gap> v:=VectorCodeword(v); [ Z(3)^0, Z(3), Z(3)^0, 0*Z(3), Z(3)^0, Z(3)^0, Z(3)^0, Z(3)^0 ] gap> G:=GeneratorMat(C); [ [ Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3) ], [ 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3) ], [ 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3) ], [ 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3) ], [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3) ], [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0 ] ] gap> AClosestVectorCombinationsMatFFEVecFFE(G,F,v,1,1); [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0 ]
‣ AClosestVectorComb..MatFFEVecFFECoords( mat, F, vec, r, st ) | ( function ) |
AClosestVectorCombinationsMatFFEVecFFECoords returns a two element list containing (a) the same closest vector as in AClosestVectorCombinationsMatFFEVecFFE, and (b) a vector v with exactly r non-zero entries, such that \(v*mat\) is the closest vector.
gap> F:=GF(3);; gap> x:= Indeterminate( F );; pol:= x^2+1; x_1^2+Z(3)^0 gap> C := GeneratorPolCode(pol,8,F); a cyclic [8,6,1..2]1..2 code defined by generator polynomial over GF(3) gap> v:=Codeword("12101111"); v:=VectorCodeword(v);; [ 1 2 1 0 1 1 1 1 ] gap> G:=GeneratorMat(C);; gap> AClosestVectorCombinationsMatFFEVecFFECoords(G,F,v,1,1); [ [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0 ], [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0 ] ]
‣ DistancesDistributionMatFFEVecFFE( mat, f, vec ) | ( function ) |
DistancesDistributionMatFFEVecFFE returns the distances distribution of the vector vec to the vectors in the vector space generated by the rows of the matrix mat over the finite field f. 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 vec.
gap> v:=[ Z(3)^0, Z(3), Z(3)^0, 0*Z(3), Z(3)^0, Z(3)^0, Z(3)^0, Z(3)^0 ];; gap> 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) ], > [ 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3) ], > [ 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3) ], > [ 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3) ], > [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3) ], > [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0 ] ];; gap> DistancesDistributionMatFFEVecFFE(vecs,GF(3),v); [ 0, 4, 6, 60, 109, 216, 192, 112, 30 ]
‣ DistancesDistributionVecFFEsVecFFE( vecs, vec ) | ( function ) |
DistancesDistributionVecFFEsVecFFE returns the distances distribution of the vector vec to the vectors in the list vecs. 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 vec.
gap> v:=[ Z(3)^0, Z(3), Z(3)^0, 0*Z(3), Z(3)^0, Z(3)^0, Z(3)^0, Z(3)^0 ];; gap> 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) ], > [ 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3) ], > [ 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3) ], > [ 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3) ], > [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3) ], > [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0 ] ];; gap> DistancesDistributionVecFFEsVecFFE(vecs,v); [ 0, 0, 0, 0, 0, 4, 0, 1, 1 ]
‣ WeightVecFFE( vec ) | ( function ) |
WeightVecFFE returns the weight of the finite field vector vec, i.e. the number of nonzero entries.
gap> v:=[ Z(3)^0, Z(3), Z(3)^0, 0*Z(3), Z(3)^0, Z(3)^0, Z(3)^0, Z(3)^0 ];; gap> WeightVecFFE(v); 7
‣ DistanceVecFFE( vec1, vec2 ) | ( function ) |
The Hamming metric 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)\). DistanceVecFFE returns the distance between the two vectors vec1 and vec2, which must have the same length and whose elements must lie in a common field. The distance is the number of places where vec1 and vec2 differ.
gap> v1:=[ Z(3)^0, Z(3), Z(3)^0, 0*Z(3), Z(3)^0, Z(3)^0, Z(3)^0, Z(3)^0 ];; gap> v2:=[ Z(3), Z(3)^0, Z(3)^0, 0*Z(3), Z(3)^0, Z(3)^0, Z(3)^0, Z(3)^0 ];; gap> DistanceVecFFE(v1,v2); 2
We basically repeat, with minor variation, the material in the GAP manual or from Frank Luebeck's website http://www.math.rwth-aachen.de/~Frank.Luebeck/data/ConwayPol on Conway polynomials. The prime fields: If \(p\geq 2\) is a prime then \(GF(p)\) denotes the field \({\mathbb{Z}}/p{\mathbb{Z}}\), with addition and multiplication performed mod \(p\).
The prime power fields: 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 defining polynomial 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^\times\) is a cyclic group. An \(\alpha \in F\) is called a primitive element if it is a generator of \(F^\times\). A defining polynomial \(f(x)\) of \(F\) is said to be primitive if it has a root in \(F\) which is a primitive element.
‣ ConwayPolynomial( p, n ) | ( function ) |
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 \ \ \langle\ \ 1 \ \ \langle\ \ 2 \ \ \langle\ \ ... \ \ \langle\ \ 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\ \ \rangle\ \ r\)). Then we define \(g \ \ \langle\ \ h\) if and only if there is an index \(k\) with \(g_i = h_i\) for \(i \ \ \rangle\ \ k\) and \((-1)^{r-k} g_k \ \ \langle\ \ (-1)^{r-k} h_k\).
The Conway polynomial \(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)}) \equiv 0 \pmod{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)\).
ConwayPolynomial(p,n) returns the polynomial \(f_{p,r}(x)\) defined above.
IsCheapConwayPolynomial(p,n) returns true if ConwayPolynomial( p, n ) 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.
‣ RandomPrimitivePolynomial( F, n ) | ( function ) |
For a finite field F and a positive integer n this function returns a primitive polynomial of degree n over F, that is a zero of this polynomial has maximal multiplicative order \(|F|^n-1\).
IsPrimitivePolynomial(f) can be used to check if a univariate polynomial f is primitive or not.
generated by GAPDoc2HTML