1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
|
<?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>
|
