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
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
|
<?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 3: Codewords</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="chap2.html">Previous Chapter</a> <a href="chap4.html">Next Chapter</a> </div>
<p><a id="X836BAA9A7EBD08B1" name="X836BAA9A7EBD08B1"></a></p>
<div class="ChapSects"><a href="chap3.html#X836BAA9A7EBD08B1">3. <span class="Heading">Codewords</span></a>
<div class="ContSect"><span class="nocss"> </span><a href="chap3.html#X81B73ABB87DA8E49">3.1 <span class="Heading">Construction of Codewords</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7B9E353D852851AA">3.1-1 Codeword</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7E7ED91C79BF3EF3">3.1-2 CodewordNr</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7F25479781E6E109">3.1-3 IsCodeword</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap3.html#X8253374284B475B6">3.2 <span class="Heading">Comparisons of Codewords</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X8123456781234567">3.2-1 =</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap3.html#X7ADE7E95867A14E1">3.3 <span class="Heading">Arithmetic Operations for Codewords</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7F2703417F270341">3.3-1 +</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X81B1391281B13912">3.3-2 -</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7F2703417F270341">3.3-3 +</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap3.html#X7BBA5DCD7A8BD60D">3.4 <span class="Heading">
Functions that Convert Codewords to Vectors or Polynomials
</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X87C8B0B178496F6A">3.4-1 VectorCodeword</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X822465E884D0F484">3.4-2 PolyCodeword</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap3.html#X81D3230A797FE6E3">3.5 <span class="Heading">
Functions that Change the Display Form of a Codeword
</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7E3E174B7954AA6B">3.5-1 TreatAsVector</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7A6828148490BD2E">3.5-2 TreatAsPoly</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap3.html#X805BF7147C68CACD">3.6 <span class="Heading">
Other Codeword Functions
</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X8000B6597EF0282F">3.6-1 NullWord</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7CDA1B547D55E6FB">3.6-2 DistanceCodeword</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7B689C0284AC4296">3.6-3 Support</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7AD61C237D8D3849">3.6-4 WeightCodeword</a></span>
</div>
</div>
<h3>3. <span class="Heading">Codewords</span></h3>
<p>Let GF(q) denote a finite field with q (a prime power) elements. A <em>code</em> is a subset C of some finite-dimensional vector space V over GF(q). The <em>length</em> of C is the dimension of V. Usually, V=GF(q)^n and the length is the number of coordinate entries. When C is itself a vector space over GF(q) then it is called a <em>linear code</em> and the <em>dimension</em> of C is its dimension as a vector space over GF(q).</p>
<p>In <strong class="pkg">GUAVA</strong>, a `codeword' is a GAP record, with one of its components being an element in V. Likewise, a `code' is a GAP record, with one of its components being a subset (or subspace with given basis, if C is linear) of V.</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(20,10,GF(4));
a [20,10,?] randomly generated code over GF(4)
gap> c:=Random(C);
[ 1 a 0 0 0 1 1 a^2 0 0 a 1 1 1 a 1 1 a a 0 ]
gap> NamesOfComponents(C);
[ "LeftActingDomain", "GeneratorsOfLeftOperatorAdditiveGroup", "WordLength",
"GeneratorMat", "name", "Basis", "NiceFreeLeftModule", "Dimension",
"Representative", "ZeroImmutable" ]
gap> NamesOfComponents(c);
[ "VectorCodeword", "WordLength", "treatAsPoly" ]
gap> c!.VectorCodeword;
[ immutable compressed vector length 20 over GF(4) ]
gap> Display(last);
[ Z(2^2), Z(2^2), Z(2^2), Z(2)^0, Z(2^2), Z(2^2)^2, 0*Z(2), Z(2^2), Z(2^2),
Z(2)^0, Z(2^2)^2, 0*Z(2), 0*Z(2), Z(2^2), 0*Z(2), 0*Z(2), 0*Z(2), Z(2^2)^2,
Z(2)^0, 0*Z(2) ]
gap> C!.Dimension;
10
</pre></td></tr></table>
<p>Mathematically, a `codeword' is an element of a code C, but in <strong class="pkg">GUAVA</strong> the <code class="code">Codeword</code> and <code class="code">VectorCodeword</code> commands have implementations which do not check if the codeword belongs to C (i.e., are independent of the code itself). They exist primarily to make it easier for the user to construct a the associated GAP record. Using these commands, one can enter into a GAP both a codeword c (belonging to C) and a received word r (not belonging to C) using the same command. The user can input codewords in different formats (as strings, vectors, and polynomials), and output information is formatted in a readable way.</p>
<p>A codeword c in a linear code C arises in practice by an initial encoding of a 'block' message m, adding enough redundancy to recover m after c is transmitted via a 'noisy' communication medium. In <strong class="pkg">GUAVA</strong>, for linear codes, the map mlongmapsto c is computed using the command <code class="code">c:=m*C</code> and recovering m from c is obtained by the command <code class="code">InformationWord(C,c)</code>. These commands are explained more below.</p>
<p>Many operations are available on codewords themselves, although codewords also work together with codes (see chapter <a href="chap4.html#X85FDDF0B7B7D87FB"><b>4.</b></a> on Codes).</p>
<p>The first section describes how codewords are constructed (see <code class="func">Codeword</code> (<a href="chap3.html#X7B9E353D852851AA"><b>3.1-1</b></a>) and <code class="func">IsCodeword</code> (<a href="chap3.html#X7F25479781E6E109"><b>3.1-3</b></a>)). Sections <a href="chap3.html#X8253374284B475B6"><b>3.2</b></a> and <a href="chap3.html#X7ADE7E95867A14E1"><b>3.3</b></a> describe the arithmetic operations applicable to codewords. Section <a href="chap3.html#X7BBA5DCD7A8BD60D"><b>3.4</b></a> describe functions that convert codewords back to vectors or polynomials (see <code class="func">VectorCodeword</code> (<a href="chap3.html#X87C8B0B178496F6A"><b>3.4-1</b></a>) and <code class="func">PolyCodeword</code> (<a href="chap3.html#X822465E884D0F484"><b>3.4-2</b></a>)). Section <b>???</b> describe functions that change the way a codeword is displayed (see <code class="func">TreatAsVector</code> (<a href="chap3.html#X7E3E174B7954AA6B"><b>3.5-1</b></a>) and <code class="func">TreatAsPoly</code> (<a href="chap3.html#X7A6828148490BD2E"><b>3.5-2</b></a>)). Finally, Section <a href="chap3.html#X805BF7147C68CACD"><b>3.6</b></a> describes a function to generate a null word (see <code class="func">NullWord</code> (<a href="chap3.html#X8000B6597EF0282F"><b>3.6-1</b></a>)) and some functions for extracting properties of codewords (see <code class="func">DistanceCodeword</code> (<a href="chap3.html#X7CDA1B547D55E6FB"><b>3.6-2</b></a>), <code class="func">Support</code> (<a href="chap3.html#X7B689C0284AC4296"><b>3.6-3</b></a>) and <code class="func">WeightCodeword</code> (<a href="chap3.html#X7AD61C237D8D3849"><b>3.6-4</b></a>)).</p>
<p><a id="X81B73ABB87DA8E49" name="X81B73ABB87DA8E49"></a></p>
<h4>3.1 <span class="Heading">Construction of Codewords</span></h4>
<p><a id="X7B9E353D852851AA" name="X7B9E353D852851AA"></a></p>
<h5>3.1-1 Codeword</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Codeword</code>( <var class="Arg">obj[, n][, F]</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">Codeword</code> returns a codeword or a list of codewords constructed from <var class="Arg">obj</var>. The object <var class="Arg">obj</var> can be a vector, a string, a polynomial or a codeword. It may also be a list of those (even a mixed list).</p>
<p>If a number <var class="Arg">n</var> is specified, all constructed codewords have length <var class="Arg">n</var>. This is the only way to make sure that all elements of <var class="Arg">obj</var> are converted to codewords of the same length. Elements of <var class="Arg">obj</var> that are longer than <var class="Arg">n</var> are reduced in length by cutting of the last positions. Elements of <var class="Arg">obj</var> that are shorter than <var class="Arg">n</var> are lengthened by adding zeros at the end. If no <var class="Arg">n</var> is specified, each constructed codeword is handled individually.</p>
<p>If a Galois field <var class="Arg">F</var> is specified, all codewords are constructed over this field. This is the only way to make sure that all elements of <var class="Arg">obj</var> are converted to the same field <var class="Arg">F</var> (otherwise they are converted one by one). Note that all elements of <var class="Arg">obj</var> must have elements over <var class="Arg">F</var> or over `Integers'. Converting from one Galois field to another is not allowed. If no <var class="Arg">F</var> is specified, vectors or strings with integer elements will be converted to the smallest Galois field possible.</p>
<p>Note that a significant speed increase is achieved if <var class="Arg">F</var> is specified, even when all elements of <var class="Arg">obj</var> already have elements over <var class="Arg">F</var>.</p>
<p>Every vector in <var class="Arg">obj</var> can be a finite field vector over <var class="Arg">F</var> or a vector over `Integers'. In the last case, it is converted to <var class="Arg">F</var> or, if omitted, to the smallest Galois field possible.</p>
<p>Every string in <var class="Arg">obj</var> must be a string of numbers, without spaces, commas or any other characters. These numbers must be from 0 to 9. The string is converted to a codeword over <var class="Arg">F</var> or, if <var class="Arg">F</var> is omitted, over the smallest Galois field possible. Note that since all numbers in the string are interpreted as one-digit numbers, Galois fields of size larger than 10 are not properly represented when using strings. In fact, no finite field of size larger than 11 arises in this fashion at all.</p>
<p>Every polynomial in <var class="Arg">obj</var> is converted to a codeword of length <var class="Arg">n</var> or, if omitted, of a length dictated by the degree of the polynomial. If <var class="Arg">F</var> is specified, a polynomial in <var class="Arg">obj</var> must be over <var class="Arg">F</var>.</p>
<p>Every element of <var class="Arg">obj</var> that is already a codeword is changed to a codeword of length <var class="Arg">n</var>. If no <var class="Arg">n</var> was specified, the codeword doesn't change. If <var class="Arg">F</var> is specified, the codeword must have base field <var class="Arg">F</var>.</p>
<table class="example">
<tr><td><pre>
gap> c := Codeword([0,1,1,1,0]);
[ 0 1 1 1 0 ]
gap> VectorCodeword( c );
[ 0*Z(2), Z(2)^0, Z(2)^0, Z(2)^0, 0*Z(2) ]
gap> c2 := Codeword([0,1,1,1,0], GF(3));
[ 0 1 1 1 0 ]
gap> VectorCodeword( c2 );
[ 0*Z(3), Z(3)^0, Z(3)^0, Z(3)^0, 0*Z(3) ]
gap> Codeword([c, c2, "0110"]);
[ [ 0 1 1 1 0 ], [ 0 1 1 1 0 ], [ 0 1 1 0 ] ]
gap> p := UnivariatePolynomial(GF(2), [Z(2)^0, 0*Z(2), Z(2)^0]);
Z(2)^0+x_1^2
gap> Codeword(p);
x^2 + 1
</pre></td></tr></table>
<p>This command can also be called using the syntax <code class="code">Codeword(obj,C)</code>. In this format, the elements of <var class="Arg">obj</var> are converted to elements of the same ambient vector space as the elements of a code <var class="Arg">C</var>. The command <code class="code">Codeword(c,C)</code> is the same as calling <code class="code">Codeword(c,n,F)</code>, where <var class="Arg">n</var> is the word length of <var class="Arg">C</var> and the <var class="Arg">F</var> is the ground field of <var class="Arg">C</var>.</p>
<table class="example">
<tr><td><pre>
gap> C := WholeSpaceCode(7,GF(5));
a cyclic [7,7,1]0 whole space code over GF(5)
gap> Codeword(["0220110", [1,1,1]], C);
[ [ 0 2 2 0 1 1 0 ], [ 1 1 1 0 0 0 0 ] ]
gap> Codeword(["0220110", [1,1,1]], 7, GF(5));
[ [ 0 2 2 0 1 1 0 ], [ 1 1 1 0 0 0 0 ] ]
gap> C:=RandomLinearCode(10,5,GF(3));
a linear [10,5,1..3]3..5 random linear code over GF(3)
gap> Codeword("1000000000",C);
[ 1 0 0 0 0 0 0 0 0 0 ]
gap> Codeword("1000000000",10,GF(3));
[ 1 0 0 0 0 0 0 0 0 0 ]
</pre></td></tr></table>
<p><a id="X7E7ED91C79BF3EF3" name="X7E7ED91C79BF3EF3"></a></p>
<h5>3.1-2 CodewordNr</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> CodewordNr</code>( <var class="Arg">C, list</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">CodewordNr</code> returns a list of codewords of <var class="Arg">C</var>. <var class="Arg">list</var> may be a list of integers or a single integer. For each integer of <var class="Arg">list</var>, the corresponding codeword of <var class="Arg">C</var> is returned. The correspondence of a number i with a codeword is determined as follows: if a list of elements of <var class="Arg">C</var> is available, the i^th element is taken. Otherwise, it is calculated by multiplication of the i^th information vector by the generator matrix or generator polynomial, where the information vectors are ordered lexicographically. In particular, the returned codeword(s) could be a vector or a polynomial. So <code class="code">CodewordNr(C, i)</code> is equal to <code class="code">AsSSortedList(C)[i]</code>, described in the next chapter. The latter function first calculates the set of all the elements of C and then returns the i^th element of that set, whereas the former only calculates the i^th codeword.</p>
<table class="example">
<tr><td><pre>
gap> B := BinaryGolayCode();
a cyclic [23,12,7]3 binary Golay code over GF(2)
gap> c := CodewordNr(B, 4);
x^22 + x^20 + x^17 + x^14 + x^13 + x^12 + x^11 + x^10
gap> R := ReedSolomonCode(2,2);
a cyclic [2,1,2]1 Reed-Solomon code over GF(3)
gap> AsSSortedList(R);
[ [ 0 0 ], [ 1 1 ], [ 2 2 ] ]
gap> CodewordNr(R, [1,3]);
[ [ 0 0 ], [ 2 2 ] ]
</pre></td></tr></table>
<p><a id="X7F25479781E6E109" name="X7F25479781E6E109"></a></p>
<h5>3.1-3 IsCodeword</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsCodeword</code>( <var class="Arg">obj</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">IsCodeword</code> returns `true' if <var class="Arg">obj</var>, which can be an object of arbitrary type, is of the codeword type and `false' otherwise. The function will signal an error if <var class="Arg">obj</var> is an unbound variable.</p>
<table class="example">
<tr><td><pre>
gap> IsCodeword(1);
false
gap> IsCodeword(ReedMullerCode(2,3));
false
gap> IsCodeword("11111");
false
gap> IsCodeword(Codeword("11111"));
true
</pre></td></tr></table>
<p><a id="X8253374284B475B6" name="X8253374284B475B6"></a></p>
<h4>3.2 <span class="Heading">Comparisons of Codewords</span></h4>
<p><a id="X8123456781234567" name="X8123456781234567"></a></p>
<h5>3.2-1 =</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> =</code>( <var class="Arg">c1, c2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The equality operator <code class="code">c1 = c2</code> evaluates to `true' if the codewords <var class="Arg">c1</var> and <var class="Arg">c2</var> are equal, and to `false' otherwise. Note that codewords are equal if and only if their base vectors are equal. Whether they are represented as a vector or polynomial has nothing to do with the comparison.</p>
<p>Comparing codewords with objects of other types is not recommended, although it is possible. If <var class="Arg">c2</var> is the codeword, the other object <var class="Arg">c1</var> is first converted to a codeword, after which comparison is possible. This way, a codeword can be compared with a vector, polynomial, or string. If <var class="Arg">c1</var> is the codeword, then problems may arise if <var class="Arg">c2</var> is a polynomial. In that case, the comparison always yields a `false', because the polynomial comparison is called.</p>
<p>The equality operator is also denoted <code class="code">EQ</code>, and <code class="code">EQ(c1,c2)</code> is the same as <code class="code">c1 = c2</code>. There is also an inequality operator, < >, or <code class="code">not EQ</code>.</p>
<table class="example">
<tr><td><pre>
gap> P := UnivariatePolynomial(GF(2), Z(2)*[1,0,0,1]);
Z(2)^0+x_1^3
gap> c := Codeword(P, GF(2));
x^3 + 1
gap> P = c; # codeword operation
true
gap> c2 := Codeword("1001", GF(2));
[ 1 0 0 1 ]
gap> c = c2;
true
gap> C:=HammingCode(3);
a linear [7,4,3]1 Hamming (3,2) code over GF(2)
gap> c1:=Random(C);
[ 1 0 0 1 1 0 0 ]
gap> c2:=Random(C);
[ 0 1 0 0 1 0 1 ]
gap> EQ(c1,c2);
false
gap> not EQ(c1,c2);
true
</pre></td></tr></table>
<p><a id="X7ADE7E95867A14E1" name="X7ADE7E95867A14E1"></a></p>
<h4>3.3 <span class="Heading">Arithmetic Operations for Codewords</span></h4>
<p><a id="X7F2703417F270341" name="X7F2703417F270341"></a></p>
<h5>3.3-1 +</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> +</code>( <var class="Arg">c1, c2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The following operations are always available for codewords. The operands must have a common base field, and must have the same length. No implicit conversions are performed.</p>
<p>The operator <code class="code">+</code> evaluates to the sum of the codewords <var class="Arg">c1</var> and <var class="Arg">c2</var>.</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(10,5,GF(3));
a linear [10,5,1..3]3..5 random linear code over GF(3)
gap> c:=Random(C);
[ 1 0 2 2 2 2 1 0 2 0 ]
gap> Codeword(c+"2000000000");
[ 0 0 2 2 2 2 1 0 2 0 ]
gap> Codeword(c+"1000000000");
</pre></td></tr></table>
<p>The last command returns a GAP ERROR since the `codeword' which <strong class="pkg">GUAVA</strong> associates to "1000000000" belongs to GF(2) and not GF(3).</p>
<p><a id="X81B1391281B13912" name="X81B1391281B13912"></a></p>
<h5>3.3-2 -</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> -</code>( <var class="Arg">c1, c2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Similar to addition: the operator <code class="code">-</code> evaluates to the difference of the codewords <var class="Arg">c1</var> and <var class="Arg">c2</var>.</p>
<p><a id="X7F2703417F270341" name="X7F2703417F270341"></a></p>
<h5>3.3-3 +</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> +</code>( <var class="Arg">v, C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The operator <code class="code">v+C</code> evaluates to the coset code of code <var class="Arg">C</var> after adding a `codeword' <var class="Arg">v</var> to all codewords in <var class="Arg">C</var>. Note that if c in C then mathematically c+C=C but <strong class="pkg">GUAVA</strong> only sees them equal as <em>sets</em>. See <code class="func">CosetCode</code> (<a href="chap6.html#X8799F4BF81B0842B"><b>6.1-17</b></a>).</p>
<p>Note that the command <code class="code">C+v</code> returns the same output as the command <code class="code">v+C</code>.</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(10,5);
a [10,5,?] randomly generated code over GF(2)
gap> c:=Random(C);
[ 0 0 0 0 0 0 0 0 0 0 ]
gap> c+C;
[ add. coset of a [10,5,?] randomly generated code over GF(2) ]
gap> c+C=C;
true
gap> IsLinearCode(c+C);
false
gap> v:=Codeword("100000000");
[ 1 0 0 0 0 0 0 0 0 ]
gap> v+C;
[ add. coset of a [10,5,?] randomly generated code over GF(2) ]
gap> C=v+C;
false
gap> C := GeneratorMatCode( [ [1, 0,0,0], [0, 1,0,0] ], GF(2) );
a linear [4,2,1]1 code defined by generator matrix over GF(2)
gap> Elements(C);
[ [ 0 0 0 0 ], [ 0 1 0 0 ], [ 1 0 0 0 ], [ 1 1 0 0 ] ]
gap> v:=Codeword("0011");
[ 0 0 1 1 ]
gap> C+v;
[ add. coset of a linear [4,2,4]1 code defined by generator matrix over GF(2) ]
gap> Elements(C+v);
[ [ 0 0 1 1 ], [ 0 1 1 1 ], [ 1 0 1 1 ], [ 1 1 1 1 ] ]
</pre></td></tr></table>
<p>In general, the operations just described can also be performed on codewords expressed as vectors, strings or polynomials, although this is not recommended. The vector, string or polynomial is first converted to a codeword, after which the normal operation is performed. For this to go right, make sure that at least one of the operands is a codeword. Further more, it will not work when the right operand is a polynomial. In that case, the polynomial operations (<code class="code">FiniteFieldPolynomialOps</code>) are called, instead of the codeword operations (<code class="code">CodewordOps</code>).</p>
<p>Some other code-oriented operations with codewords are described in <a href="chap4.html#X832DA51986A3882C"><b>4.2</b></a>.</p>
<p><a id="X7BBA5DCD7A8BD60D" name="X7BBA5DCD7A8BD60D"></a></p>
<h4>3.4 <span class="Heading">
Functions that Convert Codewords to Vectors or Polynomials
</span></h4>
<p><a id="X87C8B0B178496F6A" name="X87C8B0B178496F6A"></a></p>
<h5>3.4-1 VectorCodeword</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> VectorCodeword</code>( <var class="Arg">obj</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Here <var class="Arg">obj</var> can be a code word or a list of code words. This function returns the corresponding vectors over a finite field.</p>
<table class="example">
<tr><td><pre>
gap> a := Codeword("011011");;
gap> VectorCodeword(a);
[ 0*Z(2), Z(2)^0, Z(2)^0, 0*Z(2), Z(2)^0, Z(2)^0 ]
</pre></td></tr></table>
<p><a id="X822465E884D0F484" name="X822465E884D0F484"></a></p>
<h5>3.4-2 PolyCodeword</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> PolyCodeword</code>( <var class="Arg">obj</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">PolyCodeword</code> returns a polynomial or a list of polynomials over a Galois field, converted from <var class="Arg">obj</var>. The object <var class="Arg">obj</var> can be a codeword, or a list of codewords.</p>
<table class="example">
<tr><td><pre>
gap> a := Codeword("011011");;
gap> PolyCodeword(a);
x_1+x_1^2+x_1^4+x_1^5
</pre></td></tr></table>
<p><a id="X81D3230A797FE6E3" name="X81D3230A797FE6E3"></a></p>
<h4>3.5 <span class="Heading">
Functions that Change the Display Form of a Codeword
</span></h4>
<p><a id="X7E3E174B7954AA6B" name="X7E3E174B7954AA6B"></a></p>
<h5>3.5-1 TreatAsVector</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> TreatAsVector</code>( <var class="Arg">obj</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">TreatAsVector</code> adapts the codewords in <var class="Arg">obj</var> to make sure they are printed as vectors. <var class="Arg">obj</var> may be a codeword or a list of codewords. Elements of <var class="Arg">obj</var> that are not codewords are ignored. After this function is called, the codewords will be treated as vectors. The vector representation is obtained by using the coefficient list of the polynomial.</p>
<p>Note that this <em>only</em> changes the way a codeword is <em>printed</em>. <code class="code">TreatAsVector</code> returns nothing, it is called only for its side effect. The function <code class="code">VectorCodeword</code> converts codewords to vectors (see <code class="func">VectorCodeword</code> (<a href="chap3.html#X87C8B0B178496F6A"><b>3.4-1</b></a>)).</p>
<table class="example">
<tr><td><pre>
gap> B := BinaryGolayCode();
a cyclic [23,12,7]3 binary Golay code over GF(2)
gap> c := CodewordNr(B, 4);
x^22 + x^20 + x^17 + x^14 + x^13 + x^12 + x^11 + x^10
gap> TreatAsVector(c);
gap> c;
[ 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0 1 0 1 ]
</pre></td></tr></table>
<p><a id="X7A6828148490BD2E" name="X7A6828148490BD2E"></a></p>
<h5>3.5-2 TreatAsPoly</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> TreatAsPoly</code>( <var class="Arg">obj</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">TreatAsPoly</code> adapts the codewords in <var class="Arg">obj</var> to make sure they are printed as polynomials. <var class="Arg">obj</var> may be a codeword or a list of codewords. Elements of <var class="Arg">obj</var> that are not codewords are ignored. After this function is called, the codewords will be treated as polynomials. The finite field vector that defines the codeword is used as a coefficient list of the polynomial representation, where the first element of the vector is the coefficient of degree zero, the second element is the coefficient of degree one, etc, until the last element, which is the coefficient of highest degree.</p>
<p>Note that this <em>only</em> changes the way a codeword is <em>printed</em>. <code class="code">TreatAsPoly</code> returns nothing, it is called only for its side effect. The function <code class="code">PolyCodeword</code> converts codewords to polynomials (see <code class="func">PolyCodeword</code> (<a href="chap3.html#X822465E884D0F484"><b>3.4-2</b></a>)).</p>
<table class="example">
<tr><td><pre>
gap> a := Codeword("00001",GF(2));
[ 0 0 0 0 1 ]
gap> TreatAsPoly(a); a;
x^4
gap> b := NullWord(6,GF(4));
[ 0 0 0 0 0 0 ]
gap> TreatAsPoly(b); b;
0
</pre></td></tr></table>
<p><a id="X805BF7147C68CACD" name="X805BF7147C68CACD"></a></p>
<h4>3.6 <span class="Heading">
Other Codeword Functions
</span></h4>
<p><a id="X8000B6597EF0282F" name="X8000B6597EF0282F"></a></p>
<h5>3.6-1 NullWord</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> NullWord</code>( <var class="Arg">n, F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Other uses: <code class="code">NullWord( n )</code> (default F=GF(2)) and <code class="code">NullWord( C )</code>. <code class="code">NullWord</code> returns a codeword of length <var class="Arg">n</var> over the field <var class="Arg">F</var> of only zeros. The integer <var class="Arg">n</var> must be greater then zero. If only a code <var class="Arg">C</var> is specified, <code class="code">NullWord</code> will return a null word with both the word length and the Galois field of <var class="Arg">C</var>.</p>
<table class="example">
<tr><td><pre>
gap> NullWord(8);
[ 0 0 0 0 0 0 0 0 ]
gap> Codeword("0000") = NullWord(4);
true
gap> NullWord(5,GF(16));
[ 0 0 0 0 0 ]
gap> NullWord(ExtendedTernaryGolayCode());
[ 0 0 0 0 0 0 0 0 0 0 0 0 ]
</pre></td></tr></table>
<p><a id="X7CDA1B547D55E6FB" name="X7CDA1B547D55E6FB"></a></p>
<h5>3.6-2 DistanceCodeword</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> DistanceCodeword</code>( <var class="Arg">c1, c2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">DistanceCodeword</code> returns the Hamming distance from <var class="Arg">c1</var> to <var class="Arg">c2</var>. Both variables must be codewords with equal word length over the same Galois field. The Hamming distance between two words is the number of places in which they differ. As a result, <code class="code">DistanceCodeword</code> always returns an integer between zero and the word length of the codewords.</p>
<table class="example">
<tr><td><pre>
gap> a := Codeword([0, 1, 2, 0, 1, 2]);; b := NullWord(6, GF(3));;
gap> DistanceCodeword(a, b);
4
gap> DistanceCodeword(b, a);
4
gap> DistanceCodeword(a, a);
0
</pre></td></tr></table>
<p><a id="X7B689C0284AC4296" name="X7B689C0284AC4296"></a></p>
<h5>3.6-3 Support</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Support</code>( <var class="Arg">c</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">Support</code> returns a set of integers indicating the positions of the non-zero entries in a codeword <var class="Arg">c</var>.</p>
<table class="example">
<tr><td><pre>
gap> a := Codeword("012320023002");; Support(a);
[ 2, 3, 4, 5, 8, 9, 12 ]
gap> Support(NullWord(7));
[ ]
</pre></td></tr></table>
<p>The support of a list with codewords can be calculated by taking the union of the individual supports. The weight of the support is the length of the set.</p>
<table class="example">
<tr><td><pre>
gap> L := Codeword(["000000", "101010", "222000"], GF(3));;
gap> S := Union(List(L, i -> Support(i)));
[ 1, 2, 3, 5 ]
gap> Length(S);
4
</pre></td></tr></table>
<p><a id="X7AD61C237D8D3849" name="X7AD61C237D8D3849"></a></p>
<h5>3.6-4 WeightCodeword</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> WeightCodeword</code>( <var class="Arg">c</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">WeightCodeword</code> returns the weight of a codeword c, the number of non-zero entries in <var class="Arg">c</var>. As a result, <code class="code">WeightCodeword</code> always returns an integer between zero and the word length of the codeword.</p>
<table class="example">
<tr><td><pre>
gap> WeightCodeword(Codeword("22222"));
5
gap> WeightCodeword(NullWord(3));
0
gap> C := HammingCode(3);
a linear [7,4,3]1 Hamming (3,2) code over GF(2)
gap> Minimum(List(AsSSortedList(C){[2..Size(C)]}, WeightCodeword ) );
3
</pre></td></tr></table>
<div class="chlinkprevnextbot"> <a href="chap0.html">Top of Book</a> <a href="chap2.html">Previous Chapter</a> <a href="chap4.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>
|
