<p>Let <span class="SimpleMath">\(GF(q)\)</span> denote a finite field with <span class="SimpleMath">\(q\)</span> (a prime power) elements. A <em>code</em> is a subset <span class="SimpleMath">\(C\)</span> of some finite-dimensional vector space <span class="SimpleMath">\(V\)</span> over <spanclass="SimpleMath">\(GF(q)\)</span>. The <em>length</em> of <span class="SimpleMath">\(C\)</span> is the dimension of <span class="SimpleMath">\(V\)</span>. Usually, <span class="SimpleMath">\(V=GF(q)^n\)</span> and the length is the number of coordinate entries. When <span class="SimpleMath">\(C\)</span> is itself a vector space over <span class="SimpleMath">\(GF(q)\)</span> then it is called a <em>linear code</em> and the <em>dimension</em> of <span class="SimpleMath">\(C\)</span> is its dimension as a vector space over <span class="SimpleMath">\(GF(q)\)</span>.</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 <span class="SimpleMath">\(C\)</span> is linear) of <span class="SimpleMath">\(V\)</span>.</p>
<p>Mathematically, a `codeword' is an element of a code \(C\), but in GUAVA the Codeword and VectorCodeword 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 the associated GAP record. Using these commands, one can enter into 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>A codeword <span class="SimpleMath">\(c\)</span> in a linear code <span class="SimpleMath">\(C\)</span> arises in practice by an initial encoding of a 'block' message <span class="SimpleMath">\(m\)</span>, adding enough redundancy to recover <span class="SimpleMath">\(m\)</span> after <span class="SimpleMath">\(c\)</span> is transmitted via a 'noisy' communication medium. In <strong class="pkg">GUAVA</strong>, for linear codes, the map <span class="SimpleMath">\(m\longmapsto c\)</span> is computed using the command <code class="code">c:=m*C</code> and recovering <span class="SimpleMath">\(m\)</span> from <span class="SimpleMath">\(c\)</span> 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_mj.html#X85FDDF0B7B7D87FB"><span class="RefLink">4.</span></a> on Codes).</p>
<p>The first section describes how codewords are constructed (see <code class="func">Codeword</code> (<a href="chap3_mj.html#X7B9E353D852851AA"><span class="RefLink">3.1-1</span></a>) and <code class="func">IsCodeword</code> (<a href="chap3_mj.html#X7F25479781E6E109"><span class="RefLink">3.1-3</span></a>)). Sections <a href="chap3_mj.html#X8253374284B475B6"><span class="RefLink">3.2</span></a> and <a href="chap3_mj.html#X7ADE7E95867A14E1"><span class="RefLink">3.3</span></a> describe the arithmetic operations applicable to codewords. Section <a href="chap3_mj.html#X7BBA5DCD7A8BD60D"><span class="RefLink">3.4</span></a> describe functions that convert codewords back to vectors or polynomials (see <code class="func">VectorCodeword</code> (<a href="chap3_mj.html#X87C8B0B178496F6A"><span class="RefLink">3.4-1</span></a>) and <code class="func">PolyCodeword</code> (<a href="chap3_mj.html#X822465E884D0F484"><span class="RefLink">3.4-2</span></a>)). Section <a href="chap3_mj.html#X81D3230A797FE6E3"><span class="RefLink">3.5</span></a> describe functions that change the way a codeword is displayed (see <code class="func">TreatAsVector</code> (<a href="chap3_mj.html#X7E3E174B7954AA6B"><span class="RefLink">3.5-1</span></a>) and <code class="func">TreatAsPoly</code> (<a href="chap3_mj.html#X7A6828148490BD2E"><span class="RefLink">3.5-2</span></a>)). Finally, Section <a href="chap3_mj.html#X805BF7147C68CACD"><span class="RefLink">3.6</span></a> describes a function to generate a null word (see <code class="func">NullWord</code> (<a href="chap3_mj.html#X8000B6597EF0282F"><span class="RefLink">3.6-1</span></a>)) and some functions for extracting properties of codewords (see <code class="func">DistanceCodeword</code> (<a href="chap3_mj.html#X7CDA1B547D55E6FB"><span class="RefLink">3.6-2</span></a>), <code class="func">Support</code> (<a href="chap3_mj.html#X7B689C0284AC4296"><span class="RefLink">3.6-3</span></a>) and <code class="func">WeightCodeword</code> (<a href="chap3_mj.html#X7AD61C237D8D3849"><span class="RefLink">3.6-4</span></a>)).</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Codeword</code>( <var class="Arg">obj</var>[, <var class="Arg">n</var>][, <var class="Arg">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 <varclass="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 F is specified, vectors or strings with integer elements will be converted to the smallest Galois field possible.
<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 F or, if omitted, to the smallest Galois field possible.
<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 F is specified, the codeword must have base field F.
<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>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CodewordNr</code>( <var class="Arg">C</var>, <var class="Arg">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>. <varclass="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 <span class="SimpleMath">\(i\)</span> with a codeword is determined as follows: if a list of elements of <var class="Arg">C</var> is available, the <span class="SimpleMath">\(i^{th}\)</span> element is taken. Otherwise, it is calculated by multiplication of the <span class="SimpleMath">\(i^{th}\)</span> 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 <span class="SimpleMath">\(C\)</span> and then returns the <span class="SimpleMath">\(i^{th}\)</span> element of that set, whereas the former only calculates the <span class="SimpleMath">\(i^{th}\)</span> codeword.</p>
<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 obj, 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>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ \=</code>( <var class="Arg">c1</var>, <var class="Arg">c2</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>The equality operator <code class="code">c1 = c2</code> evaluates to `true' if the codewordsc1 and c2 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>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>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ \+</code>( <var class="Arg">c1</var>, <var class="Arg">c2</var> )</td><td class="tdright">( method )</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>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ \-</code>( <var class="Arg">c1</var>, <var class="Arg">c2</var> )</td><td class="tdright">( method )</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>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ \+</code>( <var class="Arg">v</var>, <var class="Arg">C</var> )</td><td class="tdright">( method )</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' v to all codewords in C. Note that if \(c \in C\) then mathematically \(c+C=C\) but GUAVA only sees them equal as sets. See CosetCode (6.1-17).
<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>
<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_mj.html#X832DA51986A3882C"><span class="RefLink">4.2</span></a>.</p>
<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>
<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>
<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_mj.html#X87C8B0B178496F6A"><span class="RefLink">3.4-1</span></a>)).</p>
<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_mj.html#X822465E884D0F484"><span class="RefLink">3.4-2</span></a>)).</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NullWord</code>( <var class="Arg">n</var>, <var class="Arg">F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Other uses: <code class="code">NullWord( n )</code> (default <span class="SimpleMath">\(F=GF(2)\)</span>) 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>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DistanceCodeword</code>( <var class="Arg">c1</var>, <var class="Arg">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>
<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>
<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>
<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 <span class="SimpleMath">\(c\)</span>, 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>
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
