<?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>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
91213ddcfbe7f54821d42c2d9e091326
>
files
>
1393
