Let \(GF(q)\) denote a finite field with \(q\) (a prime power) elements. A *code* is a subset \(C\) of some finite-dimensional vector space \(V\) over \(GF(q)\). The *length* 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 *linear code* and the *dimension* of \(C\) is its dimension as a vector space over \(GF(q)\).

In **GUAVA**, 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\).

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); [ "Representative", "ZeroImmutable", "name", "LeftActingDomain", "Dimension", "GeneratorsOfLeftOperatorAdditiveGroup", "Basis", "NiceFreeLeftModule", "GeneratorMat", "WordLength" ] 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

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.

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 **GUAVA**, for linear codes, the map \(m\longmapsto c\) is computed using the command `c:=m*C`

and recovering \(m\) from \(c\) is obtained by the command `InformationWord(C,c)`

. These commands are explained more below.

Many operations are available on codewords themselves, although codewords also work together with codes (see chapter 4. on Codes).

The first section describes how codewords are constructed (see `Codeword`

(3.1-1) and `IsCodeword`

(3.1-3)). Sections 3.2 and 3.3 describe the arithmetic operations applicable to codewords. Section 3.4 describe functions that convert codewords back to vectors or polynomials (see `VectorCodeword`

(3.4-1) and `PolyCodeword`

(3.4-2)). Section 3.5 describe functions that change the way a codeword is displayed (see `TreatAsVector`

(3.5-1) and `TreatAsPoly`

(3.5-2)). Finally, Section 3.6 describes a function to generate a null word (see `NullWord`

(3.6-1)) and some functions for extracting properties of codewords (see `DistanceCodeword`

(3.6-2), `Support`

(3.6-3) and `WeightCodeword`

(3.6-4)).

`‣ Codeword` ( obj[, n][, F] ) | ( function ) |

`Codeword`

returns a codeword or a list of codewords constructed from `obj`. The object `obj` can be a vector, a string, a polynomial or a codeword. It may also be a list of those (even a mixed list).

If a number `n` is specified, all constructed codewords have length `n`. This is the only way to make sure that all elements of `obj` are converted to codewords of the same length. Elements of `obj` that are longer than `n` are reduced in length by cutting of the last positions. Elements of `obj` that are shorter than `n` are lengthened by adding zeros at the end. If no `n` is specified, each constructed codeword is handled individually.

If a Galois field `F` is specified, all codewords are constructed over this field. This is the only way to make sure that all elements of `obj` are converted to the same field `F` (otherwise they are converted one by one). Note that all elements of `obj` must have elements over `F` 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.

Note that a significant speed increase is achieved if `F` is specified, even when all elements of `obj` already have elements over `F`.

Every vector in `obj` can be a finite field vector over `F` or a vector over `Integers'. In the last case, it is converted to `F` or, if omitted, to the smallest Galois field possible.

Every string in `obj` 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 `F` or, if `F` 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.

Every polynomial in `obj` is converted to a codeword of length `n` or, if omitted, of a length dictated by the degree of the polynomial. If `F` is specified, a polynomial in `obj` must be over `F`.

Every element of `obj` that is already a codeword is changed to a codeword of length `n`. If no `n` was specified, the codeword doesn't change. If `F` is specified, the codeword must have base field `F`.

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]); x_1^2+Z(2)^0 gap> Codeword(p); x^2 + 1

This command can also be called using the syntax `Codeword(obj,C)`

. In this format, the elements of `obj` are converted to elements of the same ambient vector space as the elements of a code `C`. The command `Codeword(c,C)`

is the same as calling `Codeword(c,n,F)`

, where `n` is the word length of `C` and the `F` is the ground field of `C`.

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 [10,5,?] randomly generated 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 ]

`‣ CodewordNr` ( C, list ) | ( function ) |

`CodewordNr`

returns a list of codewords of `C`. `list` may be a list of integers or a single integer. For each integer of `list`, the corresponding codeword of `C` is returned. The correspondence of a number \(i\) with a codeword is determined as follows: if a list of elements of `C` 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 `CodewordNr(C, i)`

is equal to `AsSSortedList(C)[i]`

, 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.

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 ] ]

`‣ IsCodeword` ( obj ) | ( function ) |

`IsCodeword`

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 `obj` is an unbound variable.

gap> IsCodeword(1); false gap> IsCodeword(ReedMullerCode(2,3)); false gap> IsCodeword("11111"); false gap> IsCodeword(Codeword("11111")); true

`3.2-1 \=`

`‣ \=` ( c1, c2 ) | ( method ) |

The equality operator `c1 = c2`

evaluates to `true' if the codewords `c1` 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.

Comparing codewords with objects of other types is not recommended, although it is possible. If `c2` is the codeword, the other object `c1` 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 `c1` is the codeword, then problems may arise if `c2` is a polynomial. In that case, the comparison always yields a `false', because the polynomial comparison is called.

The equality operator is also denoted `EQ`

, and `EQ(c1,c2)`

is the same as `c1 = c2`

. There is also an inequality operator, < >, or `not EQ`

.

gap> P := UnivariatePolynomial(GF(2), Z(2)*[1,0,0,1]); x_1^3+Z(2)^0 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

`3.3-1 \+`

`‣ \+` ( c1, c2 ) | ( method ) |

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.

The operator `+`

evaluates to the sum of the codewords `c1` and `c2`.

gap> C:=RandomLinearCode(10,5,GF(3)); a [10,5,?] randomly generated 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"); Error, <x> and <y> have different characteristic

The last command returns a GAP ERROR since the `codeword' which **GUAVA** associates to "1000000000" belongs to \(GF(2)\) and not \(GF(3)\).

`3.3-2 \-`

`‣ \-` ( c1, c2 ) | ( method ) |

Similar to addition: the operator `-`

evaluates to the difference of the codewords `c1` and `c2`.

`3.3-3 \+`

`‣ \+` ( v, C ) | ( method ) |

The operator `v+C`

evaluates to the coset code of code `C` 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).

Note that the command `C+v`

returns the same output as the command `v+C`

.

gap> C:=RandomLinearCode(10,5); a [10,5,?] randomly generated code over GF(3) 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..2 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 ] ]

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 (`FiniteFieldPolynomialOps`

) are called, instead of the codeword operations (`CodewordOps`

).

Some other code-oriented operations with codewords are described in 4.2.

`‣ VectorCodeword` ( obj ) | ( function ) |

Here `obj` can be a code word or a list of code words. This function returns the corresponding vectors over a finite field.

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 ]

`‣ PolyCodeword` ( obj ) | ( function ) |

`PolyCodeword`

returns a polynomial or a list of polynomials over a Galois field, converted from `obj`. The object `obj` can be a codeword, or a list of codewords.

gap> a := Codeword("011011");; gap> PolyCodeword(a); x_1^5+x_1^4+x_1^2+x_1

`‣ TreatAsVector` ( obj ) | ( function ) |

`TreatAsVector`

adapts the codewords in `obj` to make sure they are printed as vectors. `obj` may be a codeword or a list of codewords. Elements of `obj` 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.

Note that this *only* changes the way a codeword is *printed*. `TreatAsVector`

returns nothing, it is called only for its side effect. The function `VectorCodeword`

converts codewords to vectors (see `VectorCodeword`

(3.4-1)).

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 ]

`‣ TreatAsPoly` ( obj ) | ( function ) |

`TreatAsPoly`

adapts the codewords in `obj` to make sure they are printed as polynomials. `obj` may be a codeword or a list of codewords. Elements of `obj` 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.

Note that this *only* changes the way a codeword is *printed*. `TreatAsPoly`

returns nothing, it is called only for its side effect. The function `PolyCodeword`

converts codewords to polynomials (see `PolyCodeword`

(3.4-2)).

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

`‣ NullWord` ( n, F ) | ( function ) |

Other uses: `NullWord( n )`

(default \(F=GF(2)\)) and `NullWord( C )`

. `NullWord`

returns a codeword of length `n` over the field `F` of only zeros. The integer `n` must be greater then zero. If only a code `C` is specified, `NullWord`

will return a null word with both the word length and the Galois field of `C`.

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 ]

`‣ DistanceCodeword` ( c1, c2 ) | ( function ) |

`DistanceCodeword`

returns the Hamming distance from `c1` to `c2`. 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, `DistanceCodeword`

always returns an integer between zero and the word length of the codewords.

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

`‣ Support` ( c ) | ( function ) |

`Support`

returns a set of integers indicating the positions of the non-zero entries in a codeword `c`.

gap> a := Codeword("012320023002");; Support(a); [ 2, 3, 4, 5, 8, 9, 12 ] gap> Support(NullWord(7)); [ ]

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.

gap> L := Codeword(["000000", "101010", "222000"], GF(3));; gap> S := Union(List(L, i -> Support(i))); [ 1, 2, 3, 5 ] gap> Length(S); 4

`‣ WeightCodeword` ( c ) | ( function ) |

`WeightCodeword`

returns the weight of a codeword \(c\), the number of non-zero entries in `c`. As a result, `WeightCodeword`

always returns an integer between zero and the word length of the codeword.

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

generated by GAPDoc2HTML