Goto Chapter: Top 1 2 3 4 5 6 7 8 9 Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

8 Coding theory functions in GAP
 8.1 Distance functions
 8.2 Other functions

8 Coding theory functions in GAP

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

However, the GAP command PrimitivePolynomial returns an integer primitive polynomial not the finite field kind.

8.1 Distance functions

8.1-1 AClosestVectorCombinationsMatFFEVecFFE
‣ 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 ]

8.1-2 AClosestVectorComb..MatFFEVecFFECoords
‣ 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 ] ]

8.1-3 DistancesDistributionMatFFEVecFFE
‣ 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 ]

8.1-4 DistancesDistributionVecFFEsVecFFE
‣ 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 ]

8.1-5 WeightVecFFE
‣ 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

8.1-6 DistanceVecFFE
‣ 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

8.2 Other functions

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.

8.2-1 ConwayPolynomial
‣ 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:

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.

8.2-2 RandomPrimitivePolynomial
‣ 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.

 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 Bib Ind

generated by GAPDoc2HTML