<?xml version="1.0" encoding="UTF-8"?> <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en"> <head> <title>GAP (guava) - Chapter 2: Coding theory functions in GAP</title> <meta http-equiv="content-type" content="text/html; charset=UTF-8" /> <meta name="generator" content="GAPDoc2HTML" /> <link rel="stylesheet" type="text/css" href="manual.css" /> </head> <body> <div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div> <div class="chlinkprevnexttop"> <a href="chap0.html">Top of Book</a> <a href="chap1.html">Previous Chapter</a> <a href="chap3.html">Next Chapter</a> </div> <p><a id="X7A93308C82637F4F" name="X7A93308C82637F4F"></a></p> <div class="ChapSects"><a href="chap2.html#X7A93308C82637F4F">2. <span class="Heading">Coding theory functions in GAP</span></a> <div class="ContSect"><span class="nocss"> </span><a href="chap2.html#X80F192497C008691">2.1 <span class="Heading"> Distance functions </span></a> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X82E5987E81487D18">2.1-1 AClosestVectorCombinationsMatFFEVecFFE</a></span> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X870DE258833C5AA0">2.1-2 AClosestVectorComb..MatFFEVecFFECoords</a></span> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X85135CEB86E61D49">2.1-3 DistancesDistributionMatFFEVecFFE</a></span> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X7F2F630984A9D3D6">2.1-4 DistancesDistributionVecFFEsVecFFE</a></span> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X7C9F4D657F9BA5A1">2.1-5 WeightVecFFE</a></span> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X85AA5C6587559C1C">2.1-6 DistanceVecFFE</a></span> </div> <div class="ContSect"><span class="nocss"> </span><a href="chap2.html#X87C3D1B984960984">2.2 <span class="Heading"> Other functions </span></a> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X7C2425A786F09054">2.2-1 ConwayPolynomial</a></span> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X7ECC593583E68A6C">2.2-2 RandomPrimitivePolynomial</a></span> </div> </div> <h3>2. <span class="Heading">Coding theory functions in GAP</span></h3> <p>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</p> <ul> <li><p><code class="code">AClosestVectorCombinationsMatFFEVecFFE</code>,</p> </li> <li><p><code class="code">AClosestVectorCombinationsMatFFEVecFFECoords</code>,</p> </li> <li><p><code class="code">CosetLeadersMatFFE</code>,</p> </li> <li><p><code class="code">DistancesDistributionMatFFEVecFFE</code>,</p> </li> <li><p><code class="code">DistancesDistributionVecFFEsVecFFE</code>,</p> </li> <li><p><code class="code">DistanceVecFFE</code> and <code class="code">WeightVecFFE</code>,</p> </li> <li><p><code class="code">ConwayPolynomial</code> and <code class="code">IsCheapConwayPolynomial</code>,</p> </li> <li><p><code class="code">IsPrimitivePolynomial</code>, and <code class="code">RandomPrimitivePolynomial</code>.</p> </li> </ul> <p>However, the GAP command <code class="code">PrimitivePolynomial</code> returns an integer primitive polynomial not the finite field kind.</p> <p><a id="X80F192497C008691" name="X80F192497C008691"></a></p> <h4>2.1 <span class="Heading"> Distance functions </span></h4> <p><a id="X82E5987E81487D18" name="X82E5987E81487D18"></a></p> <h5>2.1-1 AClosestVectorCombinationsMatFFEVecFFE</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AClosestVectorCombinationsMatFFEVecFFE</code>( <var class="Arg">mat, F, vec, r, st</var> )</td><td class="tdright">( function )</td></tr></table></div> <p>This command runs through the <var class="Arg">F</var>-linear combinations of the vectors in the rows of the matrix <var class="Arg">mat</var> that can be written as linear combinations of exactly <var class="Arg">r</var> rows (that is without using zero as a coefficient) and returns a vector from these that is closest to the vector <var class="Arg">vec</var>. The length of the rows of <var class="Arg">mat</var> and the length of <var class="Arg">vec</var> must be equal, and all elements must lie in <var class="Arg">F</var>. The rows of <var class="Arg">mat</var> must be linearly independent. If it finds a vector of distance at most <var class="Arg">st</var>, which must be a nonnegative integer, then it stops immediately and returns this vector.</p> <table class="example"> <tr><td><pre> 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 ] </pre></td></tr></table> <p><a id="X870DE258833C5AA0" name="X870DE258833C5AA0"></a></p> <h5>2.1-2 AClosestVectorComb..MatFFEVecFFECoords</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AClosestVectorComb..MatFFEVecFFECoords</code>( <var class="Arg">mat, F, vec, r, st</var> )</td><td class="tdright">( function )</td></tr></table></div> <p><code class="code">AClosestVectorCombinationsMatFFEVecFFECoords</code> returns a two element list containing (a) the same closest vector as in <code class="code">AClosestVectorCombinationsMatFFEVecFFE</code>, and (b) a vector <var class="Arg">v</var> with exactly <var class="Arg">r</var> non-zero entries, such that v*mat is the closest vector.</p> <table class="example"> <tr><td><pre> 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 ] ] </pre></td></tr></table> <p><a id="X85135CEB86E61D49" name="X85135CEB86E61D49"></a></p> <h5>2.1-3 DistancesDistributionMatFFEVecFFE</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> DistancesDistributionMatFFEVecFFE</code>( <var class="Arg">mat, f, vec</var> )</td><td class="tdright">( function )</td></tr></table></div> <p><code class="code">DistancesDistributionMatFFEVecFFE</code> returns the distances distribution of the vector <var class="Arg">vec</var> to the vectors in the vector space generated by the rows of the matrix <var class="Arg">mat</var> over the finite field <var class="Arg">f</var>. 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 <var class="Arg">vec</var>.</p> <table class="example"> <tr><td><pre> 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 ] </pre></td></tr></table> <p><a id="X7F2F630984A9D3D6" name="X7F2F630984A9D3D6"></a></p> <h5>2.1-4 DistancesDistributionVecFFEsVecFFE</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> DistancesDistributionVecFFEsVecFFE</code>( <var class="Arg">vecs, vec</var> )</td><td class="tdright">( function )</td></tr></table></div> <p><code class="code">DistancesDistributionVecFFEsVecFFE</code> returns the distances distribution of the vector <var class="Arg">vec</var> to the vectors in the list <var class="Arg">vecs</var>. 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 <var class="Arg">vecs</var> that have distance i+1 to <var class="Arg">vec</var>.</p> <table class="example"> <tr><td><pre> 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 ] </pre></td></tr></table> <p><a id="X7C9F4D657F9BA5A1" name="X7C9F4D657F9BA5A1"></a></p> <h5>2.1-5 WeightVecFFE</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> WeightVecFFE</code>( <var class="Arg">vec</var> )</td><td class="tdright">( function )</td></tr></table></div> <p><code class="code">WeightVecFFE</code> returns the weight of the finite field vector <var class="Arg">vec</var>, i.e. the number of nonzero entries.</p> <table class="example"> <tr><td><pre> 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 </pre></td></tr></table> <p><a id="X85AA5C6587559C1C" name="X85AA5C6587559C1C"></a></p> <h5>2.1-6 DistanceVecFFE</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> DistanceVecFFE</code>( <var class="Arg">vec1, vec2</var> )</td><td class="tdright">( function )</td></tr></table></div> <p>The <em>Hamming metric</em> on GF(q)^n is the function</p> <p class="pcenter"> dist((v_1,...,v_n),(w_1,...,w_n)) =|\{i\in [1..n]\ |\ v_i\not= w_i\}|. </p> <p>This is also called the (Hamming) distance between v=(v_1,...,v_n) and w=(w_1,...,w_n). <code class="code">DistanceVecFFE</code> returns the distance between the two vectors <var class="Arg">vec1</var> and <var class="Arg">vec2</var>, which must have the same length and whose elements must lie in a common field. The distance is the number of places where <var class="Arg">vec1</var> and <var class="Arg">vec2</var> differ.</p> <table class="example"> <tr><td><pre> 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 </pre></td></tr></table> <p><a id="X87C3D1B984960984" name="X87C3D1B984960984"></a></p> <h4>2.2 <span class="Heading"> Other functions </span></h4> <p>We basically repeat, with minor variation, the material in the GAP manual or from Frank Luebeck's website <span class="URL"><a href="http://www.math.rwth-aachen.de:8001/~Frank.Luebeck/data/ConwayPol">http://www.math.rwth-aachen.de:8001/~Frank.Luebeck/data/ConwayPol</a></span> on Conway polynomials. The <strong class="button">prime fields</strong>: If p>= 2 is a prime then GF(p) denotes the field Z}/pZ}, with addition and multiplication performed mod p.</p> <p>The <strong class="button">prime power fields</strong>: 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 <strong class="button">defining polynomial</strong> of E. Any defining polynomial factors completely into distinct linear factors over the field it defines.</p> <p>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 <strong class="button">primitive element</strong> if it is a generator of F^x. A defining polynomial f(x) of F is said to be <strong class="button">primitive</strong> if it has a root in F which is a primitive element.</p> <p><a id="X7C2425A786F09054" name="X7C2425A786F09054"></a></p> <h5>2.2-1 ConwayPolynomial</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ConwayPolynomial</code>( <var class="Arg">p, n</var> )</td><td class="tdright">( function )</td></tr></table></div> <p>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.</p> <p>The <strong class="button">Conway polynomial</strong> f_p,r(x) for GF(p^r) is the smallest polynomial of degree r with respect to this ordering such that:</p> <ul> <li><p>f_p,r(x) is monic,</p> </li> <li><p>f_p,r(x) is primitive, that is, any zero is a generator of the (cyclic) multiplicative group of GF(p^r),</p> </li> <li><p>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).</p> </li> </ul> <p><code class="code">ConwayPolynomial(p,n)</code> returns the polynomial f_p,r(x) defined above.</p> <p><code class="code">IsCheapConwayPolynomial(p,n)</code> returns true if <code class="code">ConwayPolynomial( p, n )</code> 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.</p> <p><a id="X7ECC593583E68A6C" name="X7ECC593583E68A6C"></a></p> <h5>2.2-2 RandomPrimitivePolynomial</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> RandomPrimitivePolynomial</code>( <var class="Arg">F, n</var> )</td><td class="tdright">( function )</td></tr></table></div> <p>For a finite field <var class="Arg">F</var> and a positive integer <var class="Arg">n</var> this function returns a primitive polynomial of degree <var class="Arg">n</var> over <var class="Arg">F</var>, that is a zero of this polynomial has maximal multiplicative order |F|^n-1.</p> <p><code class="code">IsPrimitivePolynomial(f)</code> can be used to check if a univariate polynomial <var class="Arg">f</var> is primitive or not.</p> <div class="chlinkprevnextbot"> <a href="chap0.html">Top of Book</a> <a href="chap1.html">Previous Chapter</a> <a href="chap3.html">Next Chapter</a> </div> <div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div> <hr /> <p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p> </body> </html>