%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%A  guava.tex                   GUAVA documentation             Reinald Baart
%A                                                       & Jasper Cramwinckel
%A                                                          & Erik Roijackers
%%
%H  @(#)$Id: guava.tex,v $
%%
%Y  Copyright (C)  1994,  Vakgroep Algemene Wiskunde,  T.U. Delft,  Nederland
%%
%H  $Log: guava.tex,v $
%%
\newcommand{\GUAVA}{{\sf GUA\hspace{-0.05cm}V\hspace{-0.05cm}A}}
\Chapter{GUAVA}

{\GUAVA} is a share library package that implements coding theory
algorithms in {\GAP}. Codes can be created and manipulated and
information about codes can be calculated.

{\GUAVA} consists of various files written in the {\GAP} language, and an
external program from J.S.~Leon for dealing with automorphism groups of
codes and isomorphism testing functions. Several algorithms that need the
speed are integrated in the {\GAP} kernel. Please send your bug reports
to the gap-forum ('GAP-Forum@Math.RWTH-Aachen.DE').

{\GUAVA} is written as a final project during our study of Mathematics at
the Delft University of Technology, department of Pure Mathematics, and
in Aachen, at Lehrstuhl D fuer Mathematik.

We would like to thank the {\GAP} people at the R.W.T.H. Aachen for their
support, A.E.~Brouwer for his advice and J.~Simonis for his supervision.

Jasper Cramwinckel, \\
Erik Roijackers, and \\
Reinald Baart.

Delft University of Technology\\
Faculty of Technical Mathematics and Informatics\\
Department of Pure Mathematics

The following sections describe the functions of the {\GUAVA}
(Version~1.2) share libary package for computing with codes. All
functions described here are written entirely in the {\GAP} language,
except for the automorphism group and isomorphism testing functions,
which make use of J.S.~Leon\'s partition backtrack programs.

{\GUAVA} is primarily designed for the construction and analysis of
codes.  The functions can be divided into three subcategories\:

*Construction of codes*:\\
{\GUAVA} can construct *unrestricted*, *linear* and *cyclic
codes*. Information about the code is stored in a record, together with
operations applicable to the code.

*Manipulations of codes*:\\
Manipulation transforms one code into another, or constructs a new code
from two codes. The new code can profit from the data in the record of
the old code(s), so in these cases calculation time decreases.

*Computations of information about codes*:\\
{\GUAVA} can calculate important data of codes very fast. The results are
stored in the code record.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% codewords

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Codewords}

A *codeword* is basically just a vector of finite field elements. In
{\GUAVA}, a codeword is a record, with this base vector as its most
important element.

Codewords have been implemented in {\GUAVA} mainly because of their easy
interfacing with the user. The user can input codewords in different
formats, and output information is formatted in a readable way.

Codewords work together with codes (see "Codes"), although many
operations are available on codewords themselves.

The first sections describe how codewords are constructed (see "Codeword"
and "IsCodeword").

The next sections describe the operations applicable to codewords (see
"Comparisons of Codewords" and "Operations for Codewords").

The next sections describe the functions that convert codewords back to
vectors or polynomials (see "VectorCodeword" and "PolyCodeword"), and
functions that change the way a codeword is displayed (see
"TreatAsVector" and "TreatAsPoly").

The next section describes a single function to generate a null word (see
"NullWord").

The next sections describe the functions for codewords (see
"DistanceCodeword", "Support" and "WeightCodeword").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Codeword}

'Codeword( <obj> [, <n>] [, <F>] )'

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

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> Field(c);
    GF(2)
    gap> c2 := Codeword([0,1,1,1,0], GF(3));
    [ 0 1 1 1 0 ]
    gap> Field(c2);
    GF(3)
    gap> Codeword([c, c2, "0110"]);
    [ [ 0 1 1 1 0 ], [ 0 1 1 1 0 ], [ 0 1 1 0 ] ]
    gap> p := Polynomial(GF(2), [Z(2)^0, 0*Z(2), Z(2)^0]);
    Z(2)^0*(X(GF(2))^2 + 1)
    gap> Codeword(p);
    x^2 + 1 |

'Codeword( <obj>, <C> )'

In this format, the elements of <obj> are converted to elements of the
same vector space as the elements of a code <C>. This is the same as
calling 'Codeword' with the word length of <C> (which is <n>) and the
field of <C> (which is <F>).

|    gap> C := WholeSpaceCode(7,GF(5));
    A perfect cyclic [7,7,1] 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 ] ]  |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% tests for codewords

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsCodeword}

'IsCodeword( <obj> )'

'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(3,2));
    false
    gap> IsCodeword("11111");
    false
    gap> IsCodeword(Codeword("11111"));
    true |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% operations for codewords

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Comparisons of Codewords}

'<$c_1$> = <$c_2$>'\\
'<$c_1$> \<> <$c_2$>'

The equality operator '=' evaluates to 'true' if the codewords <$c_1$>
and <$c_2$> are equal, and to 'false' otherwise. The inequality operator
'\<>' evaluates to 'true' if the codewords <$c_1$> and <$c_2$> are not
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 <$c_2$> is the codeword, the other object
<$c_1$> 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 <$c_1$> is the codeword, then problems may arise if <$c_2$>
is a polynomial. In that case, the comparison always yields a 'false',
because the polynomial comparison is called (see 'Comparisons of
Polynomials').

|    gap> P := Polynomial(GF(2), Z(2)*[1,0,0,1]);
    Z(2)^0*(X(GF(2))^3 + 1)
    gap> c := Codeword(P, GF(2));
    x^3 + 1
    gap> P = c;        # codeword operation
    true
    gap> c = P;        # polynomial operation
    false
    gap> c2 := Codeword("1001", GF(2));
    [ 1 0 0 1 ]
    gap> c = c2;
    true  |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Operations for Codewords}

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.

'<$c_1$> + <$c_2$>'

The operator '+' evaluates to the sum of the codewords <$c_1$> and
<$c_2$>.

'<$c_1$> - <$c_2$>'

The operator '-' evaluates to the difference of the codewords <$c_1$> and
<$c_2$>.

'<C> + <c>'\\
'<c> + <C>'

The operator '+' evaluates to the coset code of code <C> after adding a
codeword <c> to all codewords. See "CosetCode".

In general, the operations just described can also be performed on
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
"Operations for Codes".

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% constructions of codewords

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{VectorCodeword}

'VectorCodeword( <obj> [, <n>] [, <F>] )'\\
'VectorCodeword( <obj>, <C> )'

'VectorCodeword' returns a vector or a list of vectors of elements of a
Galois field, converted 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).

In fact, the object <obj> is treated the same as in the function
'Codeword' (see "Codeword").

|    gap> a := Codeword("011011");; VectorCodeword(a);
    [ 0*Z(2), Z(2)^0, Z(2)^0, 0*Z(2), Z(2)^0, Z(2)^0 ]
    gap> VectorCodeword( [ 0, 1, 2, 1, 2, 1 ] );
    [ 0*Z(3), Z(3)^0, Z(3), Z(3)^0, Z(3), Z(3)^0 ]
    gap> VectorCodeword( [ 0, 0, 0, 0], GF(9) );
    [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3) ] |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{PolyCodeword}

'PolyCodeword( <obj> [, <n>] [, <F>] )'\\
'PolyCodeword( <obj>, <C> )'

'PolyCodeword' returns a polynomial or a list of polynomials over a
Galois field, converted 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).

In fact, the object <obj> is treated the same as in the function
'Codeword' (see "Codeword").

|    gap> a := Codeword("011011");; PolyCodeword(a);
    Z(2)^0*(X(GF(2))^5 + X(GF(2))^4 + X(GF(2))^2 + X(GF(2)))
    gap> PolyCodeword( [ 0, 1, 2, 1, 2 ] );
    Z(3)^0*(2*X(GF(3))^4 + X(GF(3))^3 + 2*X(GF(3))^2 + X(GF(3)))
    gap> PolyCodeword( [ 0, 0, 0, 0], GF(9) );
    0*X(GF(3^2))^0  |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{TreatAsVector}

'TreatAsVector( <obj> )'

'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").

|    gap> B := BinaryGolayCode();
    A perfect cyclic [23,12,7] 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 ]  |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{TreatAsPoly}

'TreatAsPoly( <obj> )'

'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").

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{NullWord}

'NullWord( <n> )'\\
'NullWord( <n>, <F> )'\\
'NullWord( <C> )'

'NullWord' returns a codeword of length <n> over the field <F> of only
zeros.  The default for <F> is 'GF(2)'. <n> must be greater then zero. If
only a code <C> is specified, 'NullWord' will return a null word with 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 ] |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% properties for codewords

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{DistanceCodeword}

'DistanceCodeword( <$c_1$>, <$c_2$> )'

'DistanceCodeword' returns the Hamming distance from $c_1$ to $c_2$. 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  |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Support}

'Support( <c> )'

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{WeightCodeword}

'WeightCodeword( <c> )'

'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 perfect linear [7,4,3] code over GF(2)
    gap> Minimum(List(Elements(C){[2..Size(C)]}, WeightCodeword ) );
    3  |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% codes

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Codes}

A *code* basically is nothing more than a set of *codewords*. We call
these the *elements* of the code. A codeword is a sequence of elements of
a finite field 'GF($q$)' where $q$ is a prime power.  Depending on the
type of code, a codeword can be interpreted as a vector or as a
polynomial. This is explained in more detail in section "Codewords".

In {\GUAVA}, codes can be defined by their elements (this will be called
an *unrestricted code*), by a generator matrix (a *linear code*) or by a
generator polynomial (a *cyclic code*).

Any code can be defined by its elements. If you like, you can give the
code a name.

|    gap> C := ElementsCode(["1100", "1010", "0001"], "example code",
                           GF(2) );
    a (4,3,1..4) example code over GF(2)  |

An $(n,M,d)$ code is a code with *word length* $n$, *size* $M$ and
*minimum distance* $d$. If the minimum distance has not yet been
calculated, the lower bound and upper bound are printed. So\\
|a (4,3,1..4) code over GF(2)|\\
means a binary unrestricted code of length $4$, with $3$ elements and the
minimum distance is greater then or equal to $1$ and less than or equal
to $4$.

|    gap> MinimumDistance(C);
    2
    gap> C;
    a (4,3,2) example code over GF(2)   |

If the set of elements is a linear subspace of $GF(q)^n$, the code is
called *linear*. If a code is linear, it can be defined by its *generator
matrix* or *parity check matrix*.  The generator matrix is a basis for
the elements of a code, the parity check matrix is a basis for the
nullspace of the code.

|    gap> G := GeneratorMatCode([[1,0,1],[0,1,2]], "demo code", GF(3) );
    a linear [3,2,1..2] demo code over GF(3)
    gap> Display(G);
            Construction:
    a linear [3,2,1..2] demo code over GF(3)
            Generator matrix:
    [ 1 0 1 ]
    [ 0 1 2 ]    |

So a linear $[n, k, d]$ code is a code with *word length* $n$,
*dimension* $k$ and *minimum distance* $d$.

If the code is linear and all cyclic shifts of its elements are again
codewords, the code is called *cyclic*. A cyclic code is defined by its
*generator polynomial* or *check polynomial*. All elements are
multiples of the generator polynomial modulo a polynomial $x^n -1$ where
$n$ is the word length of the code. Multiplying a code element with the
check polynomial yields zero (modulo the polynomial $x^n -1$).

|    gap> G := GeneratorPolCode(X(GF(2))+Z(2)^0, 7, GF(2) );
    a cyclic [7,6,1..2] code defined by generator polynomial over GF(2)
    gap> Display(G);
            Construction:
    A cyclic [7,6,1..2] code defined by generator polynomial over GF(2)
            Generator polynomial:
    x + 1    |

It is possible that {\GUAVA} does not know that an unrestricted code is
linear.  This situation occurs for example when a code is generated from
a list of elements with the function 'ElementsCode'. By calling the
function 'IsLinearCode', {\GUAVA} tests if the code can be represented by
a generator matrix. If so, the code record and the operations are
converted accordingly.

|    gap> L := Z(2)*[ [0,0,0], [1,0,0], [0,1,1], [1,1,1] ];;
    gap> C := ElementsCode( L, GF(2) );
    a (3,4,1..3) user defined unrestricted code over GF(2)
    # so far, {\GUAVA} does not know what kind of code this is
    gap> IsLinearCode( C );
    true                      # it is linear
    gap> Display( C );
            Construction:
    a linear [3,2,1] user defined unrestricted code over GF(2)
            Generator matrix:
    [ 1 0 0 ]
    [ 0 1 1 ]  |

Of course the same holds for unrestricted codes that in fact are
cyclic, or codes, defined by a generator matrix, that in fact are cyclic.

Codes are printed simply by giving a small description of their
parameters, the word length, size or dimension and minimum distance,
followed by a short description and the base field of the code.  Use
'Display' for a more detailed description, showing the construction
history and a generator polynomial (for cyclic codes) or a generator
matrix (for linear codes).

{\GUAVA} doesn\'t place much emphasis on the actual encoding and decoding
processes; some algorithms have been included though. Encoding works
simply by multiplying an information vector with a code, decoding is done
by the function 'Decode'. For more information about encoding and
decoding, see sections "Operations for Codes" and "Decode".

|    gap> R := ReedMullerCode( 3, 1 );
    a linear [8,4,4] Reed-Muller (3,1) code over GF(2)
    gap> w := [ 1, 1, 1, 1 ] * R;
    [ 1 0 0 1 0 1 1 0 ]
    gap> Decode( R, w );
    [ 1 1 1 1 ]
    gap> Decode( R, w + "10000000" ); # One error at the first position
    [ 1 1 1 1 ]                       # Corrected by Guava   |

The first sections describes the functions that test whether an object
is a code and what kind of code it is (see "IsCode", "IsLinearCode" and
"IsCyclicCode").

The next sections describe the operations that are available for codes
(see "Comparisons of Codes" and "Operations for Codes").

The next sections describe functions that generate codes (see "Generating
Unrestricted Codes", "Generating Linear Codes" and "Generating Cyclic
Codes").

The next sections describe functions that manipulate codes (see
"Manipulating Codes").

The next sections describe basic functions for codes,
e.g., 'MinimumDistance' (see "Basic Functions for Codes").

The last part tells more about the implementation of codes. It describes
the format of code records (see "Code Records").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% tests for codes

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsCode}

'IsCode( <obj> )'

'IsCode' returns 'true' if <obj>, which can be an object of arbitrary
type, is a code and 'false' otherwise. Will cause an error if <obj> is an
unbound variable.

|    gap> IsCode( 1 );
    false
    gap> IsCode( ReedMullerCode( 3,2 ) );
    true
    gap> IsCode( This_object_is_unbound );
    Error, Variable: 'This_object_is_unbound' must have a value |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsLinearCode}

'IsLinearCode( <obj> )'

'IsLinearCode' checks if object <obj> (not necessarily a code) is a
linear code. If a code has already been marked as linear or cyclic, the
function automatically returns 'true'.  Otherwise, the function checks if
a basis $G$ of the elements of <obj> exists that generates the elements
of <obj>. If so, $G$ is a generator matrix of <obj> and the function
returns 'true'. If not, the function returns 'false'.

|    gap> C := ElementsCode( [ [0,0,0],[1,1,1] ], GF(2) );
    a (3,2,1..3) user defined unrestricted code over GF(2)
    gap> IsLinearCode( C );
    true
    gap> IsLinearCode( ElementsCode( [ [1,1,1] ], GF(2) ) );
    false
    gap> IsLinearCode( 1 );
    false  |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsCyclicCode}

'IsCyclicCode( <obj> )'

'IsCyclicCode' checks if the object <obj> is a cyclic code. If a code has
already been marked as cyclic, the function automatically returns 'true'.
Otherwise, the function checks if a polynomial $g$ exists that generates
the elements of <obj>. If so, $g$ is a generator polynomial of <obj> and
the function returns 'true'. If not, the function returns 'false'.

|    gap> C := ElementsCode( [ [0,0,0], [1,1,1] ], GF(2) );
    a (3,2,1..3) user defined unrestricted code over GF(2)
    # {\GUAVA} does not know the code is cyclic
    gap> IsCyclicCode( C );      # this command tells {\GUAVA} to find out
    true
    gap> IsCyclicCode( HammingCode( 4, GF(2) ) );
    false
    gap> IsCyclicCode( 1 );
    false  |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% operations for codes

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Comparisons of Codes}

'<$C_1$> = <$C_2$>'\\
'<$C_1$> \<> <$C_2$>'

The equality operator '=' evaluates to 'true' if the codes <$C_1$> and
<$C_2$> are equal, and to 'false' otherwise. The inequality operator
'\<>' evaluates to 'true' if the codes <$C_1$> and <$C_2$> are not equal,
and to 'false' otherwise.

Note that codes are equal if and only if their elements are equal. Codes
can also be compared with objects of other types. Of course they are
never equal.

|    gap> M := [ [0, 0], [1, 0], [0, 1], [1, 1] ];;
    gap> C1 := ElementsCode( M, GF(2) );
    a (2,4,1..2) user defined unrestricted code over GF(2)
    gap> M = C1;
    false
    gap> C2 := GeneratorMatCode( [ [1, 0], [0, 1] ], GF(2) );
    a linear [2,2,1] code defined by generator matrix over GF(2)
    gap> C1 = C2;
    true
    gap> ReedMullerCode( 3, 1 ) = HadamardCode( 8 );
    true
    gap> WholeSpaceCode( 5, GF(4) ) = WholeSpaceCode( 5, GF(2) );
    false  |

Another way of comparing codes is 'IsEquivalent', which checks if
two codes are equi\-valent (see "IsEquivalent").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Operations for Codes}

'<$C_1$> + <$C_2$>'

The operator '+' evaluates to the direct sum of the codes <$C_1$> and
<$C_2$>.  See "DirectSumCode".

'<C> + <c>'\\
'<c> + <C>'

The operator '+' evaluates to the coset code of code <C> after adding <c>
to all elements of <C>. See "CosetCode".

'<$C_1$> \*\ <$C_2$>'

The operator '\*' evaluates to the direct product of the codes <$C_1$>
and <$C_2$>. See "DirectProductCode".

'<x> \*\ <C>'

The operator '\*' evaluates to the element of <C> belonging to
information word <x>. <x> may be a vector, polynomial, string or codeword
or a list of those. This is the way to do encoding in {\GUAVA}. <C> must
be linear, because in {\GUAVA}, encoding by multiplication is only
defined for linear codes.  If <C> is a cyclic code, this multiplication
is the same as multiplying an information polynomial <x> by the generator
polynomial of <C> (except for the result not being a codeword type). If
<C> is a linear code, it is equal to the multiplication of an information
vector <x> by the generator matrix of <C> (again, the result then is not
a codeword type).

To decode, use the function 'Decode' (see "Decode").

'<c> in <C>'

The 'in' operator evaluates to 'true' if <C> contains the codeword or
list of codewords specified by <c>. Of course, <c> and <C> must have the
same word lengths and base fields.

|    gap> C := HammingCode( 2 );; Elements( C );
    [ [ 0 0 0 ], [ 1 1 1 ] ]
    gap> [ [ 0, 0, 0, ], [ 1, 1, 1, ] ] in C;
    true
    gap> [ 0 ] in C;
    false |

'<$C_1$> in <$C_2$>'

The 'in' operator evaluates to 'true' if <$C_1$> is a subcode of <$C_2$>,
i.e.  if <$C_2$> contains at least all the elements of <$C_1$>.

|    gap> RepetitionCode( 7 ) in HammingCode( 3 );
    true
    gap> HammingCode( 3 ) in RepetitionCode( 7 );
    false
    gap> HammingCode( 3 ) in WholeSpaceCode( 7 );
    true
    gap> AreEqualCodes := function(C1, C2)
    > return (C1 in C2) and (C2 in C1);
    > end;    #this is a slow implementation of the function '='
    function ( C1, C2 ) ... end
    gap> AreEqualCodes( HammingCode(2), RepetitionCode(3) );
    true |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% construction of codes

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% construction of unrestricted codes

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Generating Unrestricted Codes}

The following sections start with the description of creating codes from
user defined matrices or special matrices (see "ElementsCode",
"HadamardCode", "ConferenceCode" and "MOLSCode"). These codes are
unrestricted codes; they may later be discovered to be linear or cyclic.

The next section describes a function for generating random codes (see
"RandomCode").

The next section describes the Nordstrom-Robinson code (see
"NordstromRobinsonCode").

The last sections describe two functions for generating Greedy codes.
These are codes that contructed by gathering codewords from a space (see
"GreedyCode" and "LexiCode").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{ElementsCode}

'ElementsCode( <L> [, <Name> ], <F> )'

'ElementsCode' creates an unrestricted code of the list of elements <L>,
in the field <F>.  <L> must be a list of vectors, strings, polynomials or
codewords. <Name> can contain a short description of the code.

|    gap> M := Z(3)^0 * [ [1, 0, 1, 1], [2, 2, 0, 0], [0, 1, 2, 2] ];;
    gap> C := ElementsCode( M, "example code", GF(3) );
    a (4,3,1..4) example code over GF(3)
    gap> MinimumDistance( C );
    4
    gap> Elements( C );
    [ [ 1 0 1 1 ], [ 2 2 0 0 ], [ 0 1 2 2 ] ]
    gap> last = M;
    true    # Note that the elements are of codeword type |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{HadamardCode}

'HadamardCode( <H>, <t> )'\\
'HadamardCode( <H> )'

In the first form 'HadamardCode' returns a Hadamard code from the
Hadamard matrix <H>, of the $<t>^{th}$ kind. In the second form, $<t> =
3$ is used.

A Hadamard matrix is a square matrix <H> with $<H>\*<H>^T = -n\*I_n$,
where $n$ is the size of <H>. The entries of <H> are either 1 or -1.

The matrix <H> is first transformed into a binary matrix $A_n$ (by
replacing the 1\'s by 0\'s and the -1\'s by 1\'s).

The first kind ($t=1$) is created by using the rows of $A_n$ as elements,
after deleting the first column. This is a $(n-1, n, n/2)$ code.  We use
this code for creating the Hadamard code of the second kind ($t=2$), by
adding all the complements of the already existing codewords. This
results in a $(n-1, 2n, n/2 -1)$ code.  The third code ($t=3$) is created
by using the rows of $A_n$ (without cutting a column) and their
complements as elements. This way, we have an $(n, 2n, n/2)$ code.  The
returned code is generally an unrestricted code, but for $n = 2^r$, the
code is linear.

|    gap> H4 := [[1,1,1,1],[1,-1,1,-1],[1,1,-1,-1],[1,-1,-1,1]];;
    gap> HadamardCode( H4, 1 );
    a (3,4,2) Hadamard code of order 4 over GF(2)
    gap> HadamardCode( H4, 2 );
    a (3,8,1) Hadamard code of order 4 over GF(2)
    gap> HadamardCode( H4 );
    a (4,8,2) Hadamard code of order 4 over GF(2)  |

'HadamardCode( <n>, <t> )'\\
'HadamardCode( <n> )'

In the first form 'HadamardCode' returns a Hadamard code with parameter
<n> of the $<t>^{th}$ kind. In the second form, $<t>=3$ is used.

When called in these forms, 'HadamardCode' first creates a Hadamard
matrix (see "HadamardMat"), of size <n> and then follows the same
procedure as described above. Therefore the same restrictions with
respect to <n> as for Hadamard matrices hold.

|    gap> C1 := HadamardCode( 4 );
    a (4,8,2) Hadamard code of order 4 over GF(2)
    gap> C1 = HadamardCode( H4 );
    true |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{ConferenceCode}

'ConferenceCode( <H> )'

'ConferenceCode' returns a code of length $<n>-1$ constructed from a
symmetric *conference matrix* <H>. <H> must be a symmetric matrix of
order $n$, which satisfies $H\*H^T = ((n-1)\*I$. $n = 2\ ($mod $4)$. The
rows of $1/2(H+I+J), 1/2(-H+I+J)$, plus the zero and all-ones vectors
form the elements of a binary non-linear $(n-1, 2\*n, 1/2 \* (n-2))$
code.

|    gap> H6 := [[0,1,1,1,1,1],[1,0,1,-1,-1,1],[1,1,0,1,-1,-1],
    [1,-1,1,0,1,-1],[1,-1,-1,1,0,1],[1,1,-1,-1,1,0]];;
    gap> C1 := ConferenceCode( H6 );
    a (5,12,2) conference code over GF(2)
    gap> IsLinearCode( C1 );
    false |

'ConferenceCode( <n> )'

{\GUAVA} constructs a symmetric conference matrix of order $<n>+1$ ($<n>
= 1\ ($mod $4)$) and uses the rows of that matrix, plus the zero and
all-ones vectors, to construct a binary non-linear $(n, 2\*(n+1), 1/2 \*
(n-1))$ code.

|    gap> C2 := ConferenceCode( 5 );
    a (5,12,2) conference code over GF(2)
    gap> Elements( C2 );
    [ [ 0 0 0 0 0 ], [ 1 1 0 1 0 ], [ 1 1 1 0 0 ], [ 0 1 1 0 1 ],
      [ 1 0 0 1 1 ], [ 0 0 1 1 1 ], [ 1 0 1 0 1 ], [ 0 1 0 1 1 ],
      [ 1 0 1 1 0 ], [ 0 1 1 1 0 ], [ 1 1 0 0 1 ], [ 1 1 1 1 1 ] ] |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{MOLSCode}

'MOLSCode( <n>, <q> )'\\
'MOLSCode( <q> )'

'MOLSCode' returns an $(n, q^2, n-1)$ code over 'GF(<q>)'. The code is
created from $n-2$ *Mutually Orthogonal Latin Squares* (MOLS) of size $q
\* q$. The default for <n> is 4. {\GUAVA} can construct a MOLS code for
$<n>-2 \leq <q>$; <q> must be a prime power, $<q> > 2$.  If there are no
$<n>-2$ MOLS, an error is signalled.

Since each of the $<n>-2$ MOLS is a $q\*q$ matrix, we can create a code
of size $q^2$ by listing in each code element the entries that are in the
same position in each of the MOLS. We precede each of these lists with
the two coordinates that specify this position, making the word length
become $n$.

The MOLS codes are MDS codes (see "IsMDSCode").

|    gap> C1 := MOLSCode( 6, 5 );
    a (6,25,5) code generated by 4 MOLS of order 5 over GF(5)
    gap> mols := List( [1 .. WordLength(C1) - 2 ], function( nr )
    >       local ls, el;
    >       ls := NullMat( Size(Field(C1)), Size(Field(C1)) );
    >       for el in VectorCodeword( Elements( C1 ) ) do
    >          ls[IntFFE(el[1])+1][IntFFE(el[2])+1] := el[nr + 2];
    >       od;
    >       return ls;
    >    end );;
    gap> AreMOLS( mols );
    true
    gap> C2 := MOLSCode( 11 );
    a (4,121,3) code generated by 2 MOLS of order 11 over GF(11) |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{RandomCode}

'RandomCode( <n>, <M>, <F> )'

'RandomCode' returns a random unrestricted code of size <M> with word
length <n> over <F>. <M> must be less than or equal to the number of
elements in the space $GF(q)^n$.

The function 'RandomLinearCode' returns a random linear code (see
"RandomLinearCode").

|    gap> C1 := RandomCode( 6, 10, GF(8) );
    a (6,10,1..6) random unrestricted code over GF(8)
    gap> MinimumDistance(C1);
    3
    gap> C2 := RandomCode( 6, 10, GF(8) );
    a (6,10,1..6) random unrestricted code over GF(8)
    gap> C1 = C2;
    false |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{NordstromRobinsonCode}

'NordstromRobinsonCode()'

'NordstromRobinsonCode' returns a Nordstrom-Robinson code, the best code
with word length $n=16$ and minimum distance $d=6$ over 'GF(2)'. This is
a non-linear $(16, 256, 6)$ code.

|    gap> C := NordstromRobinsonCode();
    a (16,256,6) Nordstrom-Robinson code over GF(2)
    gap> OptimalityCode( C );
    0 |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{GreedyCode}

'GreedyCode( <L>, <d>, <F> )'

'GreedyCode' returns a Greedy code with design distance <d> over <F>. The
code is constructed using the Greedy algorithm on the list of vectors
<L>. This algorithm checks each vector in <L> and adds it to the code if
its distance to the current code is greater than or equal to <d>. It is
obvious that the resulting code has a minimum distance of at least <d>.

Note that Greedy codes are often linear codes.

The function 'LexiCode' creates a Greedy code from a basis instead
of an enumerated list (see "LexiCode").

|    gap> C1 := GreedyCode( Tuples( Elements( GF(2) ), 5 ), 3, GF(2) );
    a (5,4,3..5) Greedy code, user defined basis over GF(2)
    gap> C2 := GreedyCode( Permuted( Tuples( Elements( GF(2) ), 5 ), (1,4) ),
                           3, GF(2) );
    a (5,4,3..5) Greedy code, user defined basis over GF(2)
    gap> C1 = C2;
    false  |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{LexiCode}

'LexiCode( <n>, <d>, <F> )'

In this format, 'Lexicode' returns a Lexicode with word length <n>,
design distance <d> over <F>. The code is constructed using the Greedy
algorithm on the lexicographically ordered list of all vectors of length
<n> over <F>.  Every time a vector is found that has a distance to the
current code of at least <d>, it is added to the code. This results,
obviously, in a code with minimum distance greater than or equal to <d>.

|    gap> C := LexiCode( 4, 3, GF(5) );
    a (4,17,3..4) lexicode over GF(5) |

'LexiCode( <B>, <d>, <F> )'

When called in this format, 'LexiCode' uses the basis <B> instead of
the standard basis. <B> is a matrix of vectors over <F>. The code is
constructed using the Greedy algorithm on the list of vectors spanned
by <B>, ordered lexicographically with respect to <B>.

|    gap> B := [ [Z(2)^0, 0*Z(2), 0*Z(2)], [Z(2)^0, Z(2)^0, 0*Z(2)] ];;
    gap> C := LexiCode( B, 2, GF(2) );
    a linear [3,1,2] lexicode over GF(2) |

Note that binary Lexicodes are always linear.

The function 'GreedyCode' creates a Greedy code that is not
restricted to a lexicographical order (see "GreedyCode").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% construction of linear codes

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Generating Linear Codes}

The following sections describe functions for constructing linear
codes. A linear code always has a generator or check matrix.

The first two sections describe functions that generate linear codes from
the generator matrix ("GeneratorMatCode") or check matrix
("CheckMatCode"). All linear codes can be constructed with these
functions.

The next sections describes some well known codes, like Hamming codes
("HammingCode"), Reed-Muller codes ("ReedMullerCode") and the extended
Golay codes ("ExtendedBinaryGolayCode" and "ExtendedTernaryGolayCode").

A large and powerful family of codes are alternant codes. They are
obtained by a small modification of the parity check matrix of a BCH
code. See sections "AlternantCode", "GoppaCode",
"GeneralizedSrivastavaCode" and "SrivastavaCode".

The next section describes a function for generating random linear codes
(see "RandomLinearCode").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{GeneratorMatCode}

'GeneratorMatCode( <G> [, <Name> ], <F> )'

'GeneratorMatCode' returns a linear code with generator matrix <G>. <G>
must be a matrix over Galois field <F>. <Name> can contain a short
description of the code. The generator matrix is the basis of the
elements of the code. The resulting code has word length $n$, dimension
$k$ if <G> is a $k \* n$-matrix. If $GF(q)$ is the field of the code, the
size of the code will be $q^k$.

If the generator matrix does not have full row rank, the linearly
dependent rows are removed. This is done by the function 'BaseMat' (see
"BaseMat") and results in an equal code. The generator matrix can be
retrieved with the function 'GeneratorMat' (see "GeneratorMat").

|    gap> G := Z(3)^0 * [[1,0,1,2,0],[0,1,2,1,1],[0,0,1,2,1]];;
    gap> C1 := GeneratorMatCode( G, GF(3) );
    a linear [5,3,1..2] code defined by generator matrix over GF(3)
    gap> Display(C1);
            Construction:
    a linear [5,3,1..2] code defined by generator matrix over GF(3)
            Generator matrix:
    [ 1 0 1 2 0 ]
    [ 0 1 2 1 1 ]
    [ 0 0 1 2 1 ]
    gap> C2 := GeneratorMatCode( IdentityMat( 5, GF(2) ), GF(2) );
    a linear [5,5,1] code defined by generator matrix over GF(2) |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{CheckMatCode}

'CheckMatCode( <H> [, <Name> ], <F> )'

'CheckMatCode' returns a linear code with check matrix <H>. <H> must be a
matrix over Galois field <F>. <Name> can contain a short description of
the code. The parity check matrix is the transposed of the nullmatrix of
the generator matrix of the code. Therefore, $c\*<H>^T = 0$ where $c$ is
an element of the code. If <H> is a $r\*n$-matrix, the code has word
length $n$, redundancy $r$ and dimension $n-r$.

If the check matrix does not have full row rank, the linearly dependent
rows are removed. This is done by the function 'BaseMat' (see "BaseMat")
and results in an equal code. The check matrix can be retrieved with the
function 'CheckMat' (see "CheckMat").

|    gap> G := Z(3)^0 * [[1,0,1,2,0],[0,1,2,1,1],[0,0,1,2,1]];;
    gap> C1 := CheckMatCode( G, GF(3) );
    a linear [5,2,1..2] code defined by check matrix over GF(3)
    gap> CheckMat(C1);
    [ [ Z(3)^0, 0*Z(3), Z(3)^0, Z(3), 0*Z(3) ],
      [ 0*Z(3), Z(3)^0, Z(3), Z(3)^0, Z(3)^0 ],
      [ 0*Z(3), 0*Z(3), Z(3)^0, Z(3), Z(3)^0 ] ]
    gap> C2 := CheckMatCode( IdentityMat( 5, GF(2) ), GF(2) );
    a linear [5,0,1..5] code defined by check matrix over GF(2) |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{HammingCode}

'HammingCode( <r>, <F> )'

'HammingCode' returns a Hamming code with redundancy <r> over <F>.
A Hamming code is a single-error-correcting code. The parity check matrix
of a Hamming code has all nonzero vectors of length <r> in its columns,
except for a multiplication factor. The decoding algorithm of the Hamming
code (see "Decode") makes use of this property.

If $q$ is the size of its field <F>, the returned Hamming code is a linear\\
$[(q^<r>-1)/(q-1), (q^<r>-1)/(q-1) - <r>, 3]$ code.

|    gap> C1 := HammingCode( 4, GF(2) );
    a linear [15,11,3] Hamming (4,2) code over GF(2)
    gap> C2 := HammingCode( 3, GF(9) );
    a linear [91,88,3] Hamming (3,9) code over GF(9) |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{ReedMullerCode}

'ReedMullerCode( <k>, <r> )'

'ReedMullerCode' returns a binary *Reed-Muller code* $R(<r>, <k>)$ with
dimension <k> and order <r>. This is a code with length $2^<k>$ and
minimum distance $2^{<k>-<r>}$. By definition, the $<r>^{th}$ order
binary Reed-Muller code of length $n=2^<m>$, for $0 \leq <r> \leq <m>$,
is the set of all vectors $f$, where $f$ is a Boolean function which is a
polynomial of degree at most <r>.

|    gap> Display( ReedMullerCode( 3, 1 ) );
            Construction:
    a linear [8,4,4] Reed-Muller (3,1) code over GF(2)
            Generator matrix:
    [ 1 1 1 1 1 1 1 1 ]
    [ 0 0 0 0 1 1 1 1 ]
    [ 0 0 1 1 0 0 1 1 ]
    [ 0 1 0 1 0 1 0 1 ] |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{ExtendedBinaryGolayCode}

'ExtendedBinaryGolayCode( )'

'ExtendedBinaryGolayCode' returns an extended binary Golay code. This is
a $[24,12,8]$ code. Puncturing in the last position results in a perfect
binary Golay code (see "BinaryGolayCode").  The code is self-dual (see
"IsSelfDualCode").

|    gap> C := ExtendedBinaryGolayCode();
    a linear [24,12,8] extended binary Golay code over GF(2)
    gap> P := PuncturedCode(C);
    a linear [23,12,7] punctured in coordinate 24
    gap> P = BinaryGolayCode();
    true |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{ExtendedTernaryGolayCode}

'ExtendedTernaryGolayCode( )'

'ExtendedTernaryGolayCode' returns an extended ternary Golay code. This
is a $[12,6,6]$ code. Puncturing this code results in a perfect ternary
Golay code (see "TernaryGolayCode").  The code is self-dual (see
"IsSelfDualCode").

|    gap> C := ExtendedTernaryGolayCode();
    a linear [12,6,6] extended ternary Golay code over GF(3)
    gap> P := PuncturedCode(C);
    a linear [11,6,5] punctured in coordinate 12
    gap> P = TernaryGolayCode();
    true |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{AlternantCode}

'AlternantCode( <r>, <Y>, <F> )'\\
'AlternantCode( <r>, <Y>, <alpha>, <F> )'

'AlternantCode' returns an *alternant code*, with parameters <r>, <Y> and
<alpha> (optional). <r> is the design redundancy of the code. <Y> and
<alpha> are both vectors of length <n> from which the parity check matrix
is constructed. The check matrix has entries of the form $a_i^j y_i$.  If
no <alpha> is specified, the vector $[1, a, a^2, .., a^{n-1}]$ is used,
where $a$ is a primitive element of a Galois field <F>.

|    gap> Y := [ 1, 1, 1, 1, 1, 1, 1];; a := PrimitiveUnityRoot( 2, 7 );;
    gap> alpha := List( [0..6], i -> a^i );;
    gap> C := AlternantCode( 2, Y, alpha, GF(8) );
    a linear [7,3,3..4] alternant code over GF(8) |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{GoppaCode}

'GoppaCode( <G>, <L> )'

'GoppaCode' returns a Goppa code from Goppa polynomial <G>, having
coefficients in a Galois Field $GF(q^m)$. <L> must be a list of elements
in $GF(q^m)$, that are not roots of <G>. The word length of the code is
equal to the length of <L>. The parity check matrix contains entries of
the form $a_i^j G(a_i),\ a_i$ in $L$.  The function
'VerticalConversionFieldMat' converts this matrix to a matrix with
entries in $GF(q)$ (see "VerticalConversionFieldMat").

|    gap> x := Indeterminate( GF(2) );; x.name := "x";;
    gap> G := x^2 + x + 1;; L := Elements( GF(8) );;
    gap> C := GoppaCode( G, L );
    a linear [8,2,5] Goppa code over GF(2) |

'GoppaCode( <G>, <n> )'

When called with parameter <n>, {\GUAVA} constructs a list $L$ of length
<n>, such that no element of $L$ is a root of <G>.

|    gap> x := Indeterminate( GF(2) );; x.name := "x";;
    gap> G := x^2 + x + 1;;
    gap> C := GoppaCode( G, 8 );
    a linear [8,2,5] Goppa code over GF(2) |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{GeneralizedSrivastavaCode}

'GeneralizedSrivastavaCode( <a>, <w>, <z>, <F> )'\\
'GeneralizedSrivastavaCode( <a>, <w>, <z>, <t>, <F> )'

'GeneralizedSrivastavaCode' returns a generalized Srivastava code with
parameters <a>, <w>, <z>, <t>. $<a> = a_1, ..., a_n$ and $<w> = w_1, ...,
w_s$ are lists of $n+s$ distinct elements of $<F>=GF(q^m)$, <z> is a list
of length $n$ of nonzero elements of $GF(q^m)$. The parameter <t>
determines the designed distance\:\ $d \geq st + 1$. The parity check
matrix of this code has entries of the form $$z_i \over {(a_i - w_l)^k}
$$ 'VerticalConversionFieldMat' converts this matrix to a matrix with
entries in $GF(q)$ (see "VerticalConversionFieldMat"). The default for
<t> is 1. The original Srivastava codes (see "SrivastavaCode") are a
special case $t=1$, $z_i=a_i^\mu$ for some $\mu$.

|    gap> a := Filtered( Elements( GF(2^6) ), e -> e in GF(2^3) );;
    gap> w := [ Z(2^6) ];; z := List( [1..8], e -> 1 );;
    gap> C := GeneralizedSrivastavaCode( a, w, z, 1, GF(64) );
    a linear [8,2,2..5] generalized Srivastava code over GF(2) |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{SrivastavaCode}

'SrivastavaCode( <a>, <w>, <F> )'\\
'SrivastavaCode( <a>, <w>, <mu>, <F> )'

'SrivastavaCode' returns a Srivastava code with parameters <a>, <w>,
<mu>. $<a> = a_1, ..., a_n$ and $<w> = w_1, ..., w_s$ are lists of $n+s$
distinct elements of $<F>=GF(q^m)$. The default for <mu> is 1. The
Srivastava code is a generalized Srivastava code (see
"GeneralizedSrivastavaCode"), in which $<z_i> = a_i^{<mu>}$ for some <mu>
and $t=1$.

|    gap> a := Elements( GF(11) ){[2..8]};;
    gap> w := Elements( GF(11) ){[9..10]};;
    gap> C := SrivastavaCode( a, w, 2, GF(11) );
    a linear [7,5,3] Srivastava code over GF(11)
    gap> IsMDSCode( C );
    true    # Always true if F is a prime field |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{CordaroWagnerCode}

'CordaroWagnerCode( <n> )'

'CordaroWagnerCode' returns a binary Cordaro-Wagner code. This is a code
of length <n> and dimension $2$ having the best possible minimum distance
<d>. This code is just a little bit less trivial than 'RepetitionCode'
(see "RepetitionCode").

|    gap> C := CordaroWagnerCode( 11 );
    a linear [11,2,7] Cordaro-Wagner code over GF(2)
    gap> Elements(C);
    [ [ 0 0 0 0 0 0 0 0 0 0 0 ], [ 1 1 1 1 1 1 1 0 0 0 0 ],
      [ 0 0 0 0 1 1 1 1 1 1 1 ], [ 1 1 1 1 0 0 0 1 1 1 1 ] ]  |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{RandomLinearCode}

'RandomLinearCode( <n>, <k> , <F> )'

'RandomLinearCode' returns a random linear code with word length <n>,
dimension <k> over field <F>.

To create a random unrestricted code, use 'RandomCode' (see
"RandomCode").

|    gap> C := RandomLinearCode( 15, 4, GF(3) );
    a linear [15,4,1..8] random linear code over GF(3)
    gap> RandomSeed( 13 ); C1 := RandomLinearCode( 12, 5, GF(5) );
    a linear [12,5,1..5] random linear code over GF(5)
    gap> RandomSeed( 13 ); C2 := RandomLinearCode( 12, 5, GF(5) );
    RandomSeed( 13 ); C2 := RandomLinearCode( 12, 5, GF(5) );
    gap> C1 = C2;
    true    # Thanks to RandomSeed |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{BestKnownLinearCode}

'BestKnownLinearCode( <n>, <k> , <F> )'

'BestKnownLinearCode' returns the best known linear code of length <n>,
dimension <k> over field <F>. The function uses the tables described
in section "BoundsMinimumDistance" to construct this code.

|    gap> C1 := BestKnownLinearCode( 23, 12, GF(2) );
    a cyclic [23,12,7] binary Golay code over GF(2)
    gap> C1 = BinaryGolayCode();
    true
    gap> Display( BestKnownLinearCode( 8, 4, GF(4) ) );
            Construction:
    a linear [8,4,4] U!U+V construction code of
    U: a cyclic [4,3,2] dual code of
       a cyclic [4,1,4] repetition code over GF(4)
    V: a cyclic [4,1,4] repetition code over GF(4)
            Generator matrix:
    [ 1 1 0 0 1 1 0 0 ]
    [ 0 1 1 0 0 1 1 0 ]
    [ 0 0 1 1 0 0 1 1 ]
    [ 0 0 0 0 1 1 1 1 ]
    gap> C := BestKnownLinearCode(131,47);
    a linear [131,47,28..32] shortened code (in [ 1, 2, 3 ]) |

'BestKnownLinearCode( <rec> )'

In this form, <rec> must be a record containing the fields 'lowerBound',
'upperBound' and 'construction'. It uses the information in this field to
construct a code. This form is meant to be used together with the
function 'BoundsMinimumDistance' (see "BoundsMinimumDistance"), if the
bounds are already calculated.

|    gap> bounds := BoundsMinimumDistance( 20, 17, GF(4) );
    an optimal linear [20,17,d] code over GF(4) has d=3
    gap> C := BestKnownLinearCode( bounds );
    a linear [20,17,3] shortened code (in [ 1 ])
    gap> C = BestKnownLinearCode( 20, 17, GF(4) );
    true |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% construction of cyclic codes

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Generating Cyclic Codes}

The elements of a cyclic code $C$ are all multiples of a polynomial
$g(x)$, where calculations are carried out modulo $x^n-1$. Therefore, the
elements always have a degree less than $n$. The polynomial $g(x)$ is
called the *generator polynomial* of $C$. This is the unique monic
polynomial of smallest degree that generates $C$. It is a divisor of the
polynomial $x^<n>-1$.

The *check polynomial* is the polynomial $h(x)$ with $g(x)\*h(x)=
x^n-1$. Therefore it is also a divisor of $x^n-1$. The check polynomial
has the property that $c(x)\*h(x) = 0\ ($mod $ (x^n-1))$ for every
codeword $c(x)$.

The first two sections describe functions that generate cyclic codes from
a given generator or check polynomial. All cyclic codes can be
constructed using these functions.

The next sections describe the two cyclic Golay codes (see
"BinaryGolayCode" and "TernaryGolayCode").

The next sections describe functions that generate cyclic codes from a
prescribed set of roots of the generator polynomial, among which the BCH
codes.  See "RootsCode", "BCHCode", "ReedSolomonCode" and "QRCode".

The next sections describe the trivial codes (see "WholeSpaceCode",
"NullCode", "RepetitionCode").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{GeneratorPolCode}

'GeneratorPolCode( <g>, <n> [, <Name> ], <F> )'

'GeneratorPolCode' creates a cyclic code with a generator polynomial <g>,
word length <n>, over <F>. <g> can be entered as a polynomial over <F>,
or as a list of coefficients over <F> or 'Integers'. If <g> is a list of
integers, these are first converted to <F>. <Name> can contain a short
description of the code.

If <g> is not a divisor of $x^<n>-1$, it cannot be a generator
polynomial. In that case, a code is created with generator polynomial
$gcd( <g>, x^<n>-1 )$, i.e. the greatest common divisor of <g> and
$x^<n>-1$. This is a valid generator polynomial that generates the
same elements as <g>. See "Generating Cyclic Codes".

|    gap> P := Polynomial(GF(2), Z(2)*[1,0,1]);
    Z(2)^0*(X(GF(2))^2 + 1)
    gap> G := GeneratorPolCode(P, 7, GF(2));
    a cyclic [7,6,1..2] code defined by generator polynomial over GF(2)
    gap> GeneratorPol(G);
    Z(2)^0*(X(GF(2)) + 1)
    gap> G2 := GeneratorPolCode([1,1], 7, GF(2));
    a cyclic [7,6,1..2] code defined by generator polynomial over GF(2)
    gap> GeneratorPol(G2);
    Z(2)^0*(X(GF(2)) + 1)  |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{CheckPolCode}

'CheckPolCode( <h>, <n> [, <Name> ], <F> )'

'CheckPolCode' creates a cyclic code with a check polynomial <h>, word
length <n>, over <F>. <h> can be entered as a polynomial over <F>, or as
a list of coefficients over <F> or 'Integers'. If <h> is a list of
integers, these are first converted to <F>. <Name> can contain a short
description of the code.

If <h> is not a divisor of $x^<n>-1$, it cannot be a check polynomial. In
that case, a code is created with check polynomial $gcd( <h>, x^<n>-1 )$,
i.e. the greatest common divisor of <h> and $x^<n>-1$. This is a valid
check polynomial that yields the same codewords as <h>. See "Generating
Cyclic Codes".

|    gap> P := Polynomial(GF(3), Z(3)*[1,0,2]);
    Z(3)^0*(X(GF(3))^2 + 2)
    gap> H := CheckPolCode(P, 7, GF(3));
    A cyclic [7,1,d] code over GF(3)
    gap> CheckPol(H);
    Z(3)^0*(X(GF(3)) + 2)
    gap> Gcd(P, X(GF(3))^7-1);
    Z(3)^0*(X(GF(3)) + 2)    |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{BinaryGolayCode}

'BinaryGolayCode()'

'BinaryGolayCode' returns a binary Golay code. This is a perfect
[23,12,7] code. It is also cyclic, and has generator polynomial
$g(x)=1+x^2+x^4+x^5+x^6+x^{10}+x^{11}$. Extending it results in an
extended Golay code (see "ExtendedBinaryGolayCode"). There\'s also
the ternary Golay code (see "TernaryGolayCode").

|    gap> BinaryGolayCode();
    a cyclic [23,12,7] binary Golay code over GF(2)
    gap> ExtendedBinaryGolayCode() = ExtendedCode(BinaryGolayCode());
    true
    gap> IsPerfectCode(BinaryGolayCode());
    true   |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{TernaryGolayCode}

'TernaryGolayCode()'

'TernaryGolayCode' returns a ternary Golay code. This is a perfect
[11,6,5] code. It is also cyclic, and has generator polynomial
$g(x)=2+x^2+2x^3+x^4+x^5$. Extending it results in an extended Golay
code (see "ExtendedTernaryGolayCode"). There\'s also the binary Golay
code (see "BinaryGolayCode").

|    gap> Display(TernaryGolayCode());
    A perfect cyclic [11,6,5] code over GF(3)
    Construction:
            Ternary Golay code
    Generator polynomial:
            x^5 + x^4 + 2x^3 + x^2 + 2
    gap> ExtendedTernaryGolayCode() = ExtendedCode(TernaryGolayCode());
    true |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{RootsCode}

'RootsCode( <n>, <list> )'

This is the generalization of the BCH, Reed-Solomon and quadratic residue
codes (see "BCHCode", "ReedSolomonCode" and "QRCode"). The user can give
a length of the code <n> and a prescribed set of zeros. The argument
<list> must be a valid list of primitive $<n>^{th}$ roots of unity in a
splitting field $GF(q^m)$. The resulting code will be over the field
$GF(q)$. The function will return the largest possible cyclic code for
which the list <list> is a subset of the roots of the code. From this
list, {\GUAVA} calculates the entire set of roots.

|    gap> a := PrimitiveUnityRoot( 3, 14 );
    Z(3^6)^52
    gap> C1 := RootsCode( 14, [ a^0, a, a^3 ] );
    a cyclic [14,7,3..6] code defined by roots over GF(3)
    gap> MinimumDistance( C1 );
    4
    gap> b := PrimitiveUnityRoot( 2, 15 );
    Z(2^4)
    gap> C2 := RootsCode( 15, [ b, b^2, b^3, b^4 ] );
    a cyclic [15,7,5] code defined by roots over GF(2)
    gap> C2 = BCHCode( 15, 5, GF(2) );
    true |

'RootsCode( <n>, <list>, <F> )'

In this second form, the second argument is a list of integers, ranging
from 0 to <n>-1. The resulting code will be over a field <F>. {\GUAVA}
calculates a primitive $<n>^{th}$ root of unity, $\alpha$, in the
extension field of <F>. It uses the set of the powers of $\alpha$ in the
list as a prescribed set of zeros.

|    gap> C := RootsCode( 4, [ 1, 2 ], GF(5) );
    a cyclic [4,2,3] code defined by roots over GF(5)
    gap> RootsOfCode( C );
    [ Z(5), Z(5)^2 ]
    gap> C = ReedSolomonCode( 4, 3 );
    true |


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{BCHCode}

'BCHCode( <n>, <d> , <F> )'\\
'BCHCode( <n>, <b>, <d>, <F> )'

The function 'BCHCode' returns a *Bose-Chaudhuri-Hockenghem code* (or BCH
code for short). This is the largest possible cyclic code of length <n>
over field <F>, whose generator polynomial has zeros
$$a^{<b>},a^{<b>+1}, ..., a^{<b>+<d>-2},$$
where $a$ is a primitive $n^{th}$ root of unity in the splitting field
$GF(q^m)$, <b> is an integer $> 1$ and $m$ is the multiplicative order of
$q$ modulo <n>.  Default value for <b> is $1$. The length <n> of the code
and the size $q$ of the field must be relatively prime. The generator
polynomial is equal to the product of the minimal polynomials of
$X^{<b>}, X^{<b>+1}, ..., X^{<b>+<d>-2}$.

Special cases are $<b>=1$ (resulting codes are called *narrow-sense* BCH
codes), and $<n>=q^m-1$ (known as *primitive* BCH codes).  {\GUAVA}
calculates the largest value of <d>\'\ for which the BCH code with
designed distance <d>\'\ coincides with the BCH code with designed
distance <d>. This distance is called the *Bose distance* of the
code. The true minimum distance of the code is greater than or equal to
the Bose distance.

Printed are the designed distance (to be precise, the Bose distance)
'delta', and the starting power 'b'.

|    gap> C1 := BCHCode( 15, 3, 5, GF(2) );
    a cyclic [15,5,7] BCH code, delta=7, b=1 over GF(2)
    gap> C1.designedDistance;
    7
    gap> C2 := BCHCode( 23, 2, GF(2) );
    a cyclic [23,12,5..7] BCH code, delta=5, b=1 over GF(2)
    gap> C2.designedDistance;
    5
    gap> MinimumDistance(C2);
    7 |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{ReedSolomonCode}

'ReedSolomonCode( <n>, <d> )'

'ReedSolomonCode' returns a *Reed-Solomon code* of length <n>, designed
distance <d>. This code is a primitive narrow-sense BCH code over the
field $GF(q)$, where $q=<n>+1$. The dimension of an RS code is
$<n>-<d>+1$. According to the Singleton bound (see "UpperBoundSingleton")
the dimension cannot be greater than this, so the true minimum distance
of an RS code is equal to <d> and the code is maximum distance separable
(see "IsMDSCode").

|    gap> C1 := ReedSolomonCode( 3, 2 );
    a cyclic [3,2,2] Reed-Solomon code over GF(4)
    gap> C2 := ReedSolomonCode( 4, 3 );
    a cyclic [4,2,3] Reed-Solomon code over GF(5)
    gap> RootsOfCode( C2 );
    [ Z(5), Z(5)^2 ]
    gap> IsMDSCode(C2);
    true |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{QRCode}

'QRCode( <n>, <F> )'

'QRCode' returns a quadratic residue code. If <F> is a field $GF(q)$,
then $q$ must be a quadratic residue modulo <n>. That is, an $x$ exists
with $x^2=<q>\ ($mod $<n>)$. Both <n> and $q$ must be primes.  Its
generator polynomial is the product of the polynomials $x-a^i$. $a$ is a
primitive $<n>^{th}$ root of unity, and $i$ is an integer in the set of
quadratic residues modulo <n>.

|    gap> C1 := QRCode( 7, GF(2) );
    a cyclic [7,4,3] quadratic residue code over GF(2)
    gap> IsEquivalentCode( C1, HammingCode( 3, GF(2) ) );
    true
    gap> C2 := QRCode( 11, GF(3) );
    a cyclic [11,6,4..5] quadratic residue code over GF(3)
    gap> C2 = TernaryGolayCode();
    true |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{FireCode}

'FireCode( <G>, <b> )'

'FireCode' constructs a (binary) Fire code. <G> is a primitive polynomial
of degree $m$, factor of $x^r-1$. <b> an integer $0 \leq <b> \leq m$ not
divisible by $r$, that determines the burst length of a single error
burst that can be corrected. The argument <G> can be a polynomial with
base ring $GF(2)$, or a list of coefficients in $GF(2)$.  The generator
polynomial is defined as the product of <G> and $x^{2b-1}+1$.

|    gap> G := Polynomial( GF(2), Z(2)^0 * [ 1, 0, 1, 1 ] );
    Z(2)^0*(X(GF(2))^3 + X(GF(2))^2 + 1)
    gap> Factors( G );
    [ Z(2)^0*(X(GF(2))^3 + X(GF(2))^2 + 1) ]    # So it is primitive
    gap> C := FireCode( G, 3 );
    a cyclic [35,27,1..4] 3 burst error correcting fire code over GF(2)
    gap> MinimumDistance( C );
    4    # Still it can correct bursts of length 3 |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{WholeSpaceCode}

'WholeSpaceCode( <n>, <F> )'

'WholeSpaceCode' returns the cyclic whole space code of length <n> over
<F>. This code consists of all polynomials of degree less than <n> and
coefficients in <F>.

|    gap> C := WholeSpaceCode( 5, GF(3) );
    a cyclic [5,5,1] whole space code over GF(3)
    gap> CoveringRadius( C );
    0    # all elements of the space are elements of the code |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{NullCode}

'NullCode( <n>, <F> )'

'NullCode' returns the zero-dimensional nullcode with length <n> over
<F>. This code has only one word\:\ the all zero word. It is cyclic
though!

|    gap> C := NullCode( 5, GF(3) );
    a cyclic [5,0,5] nullcode over GF(3)
    gap> Elements( C );
    [ 0 ]                # this is the polynomial 0
    gap> TreatAsVector( Elements( C ) ); Elements( C );
    [ [ 0 0 0 0 0 ] ]    # this is the vector 0 |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{RepetitionCode}

'RepetitionCode( <n>, <F> )'

'RepetitionCode' returns the cyclic repetition code of length <n> over
<F>. The code has as many elements as <F>, because each codeword consists
of a repetition of one of these elements.

|    gap> C := RepetitionCode( 3, GF(5) );
    a cyclic [3,1,3] repetition code over GF(5)
    gap> Elements( C );
    [ 0, x^2 + x + 1, 2x^2 + 2x + 2, 4x^2 + 4x + 4, 3x^2 + 3x + 3 ]
    gap> IsPerfectCode( C );
    false
    gap> IsMDSCode( C );
    true |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{CyclicCodes}

'CyclicCodes( <n>, <F> )'

'CyclicCodes' returns a list of all cyclic codes of length <n> over
<F>. It constructs all possible generator polynomials from the factors of
$x^n-1$. Each combination of these factors yields a generator polynomial
after multiplication.

'NrCyclicCodes( <n>, <F> )'

The function 'NrCyclicCodes' calculates the number of cyclic codes of
length <n> over field <F>.

|    gap> NrCyclicCodes( 23, GF(2) );
    8
    [ a cyclic [23,23,1] enumerated code over GF(2),
      a cyclic [23,22,1..2] enumerated code over GF(2),
      a cyclic [23,11,1..8] enumerated code over GF(2),
      a cyclic [23,0,1..23] enumerated code over GF(2),
      a cyclic [23,11,1..8] enumerated code over GF(2),
      a cyclic [23,12,1..7] enumerated code over GF(2),
      a cyclic [23,1,1..23] enumerated code over GF(2),
      a cyclic [23,12,1..7] enumerated code over GF(2) ]
    gap> BinaryGolayCode() in codelist;
    true
    gap> RepetitionCode( 23, GF(2) ) in codelist;
    true
    gap> CordaroWagnerCode( 23 ) in codelist;
    false    # This code is not cyclic |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% manipulation of codes

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Manipulating Codes}

This section describes several functions {\GUAVA} uses to manipulate
codes. Some of the best codes are obtained by starting with for example a
BCH code, and manipulating it.

In some cases, it is faster to perform calculations with a manipulated
code than to use the original code. For example, if the dimension of the
code is larger than half the word length, it is generally faster to
compute the weight distribution by first calculating the weight
distribution of the dual code than by directly calculating the weight
distribution of the original code. The size of the dual code is smaller
in these cases.

Because {\GUAVA} keeps all information in a code record, in some cases
the information can be preserved after manipulations. Therefore,
computations do not always have to start from scratch.

The next sections describe manipulating function that take a code with
certain parameters, modify it in some way and return a different
code. See "ExtendedCode", "PuncturedCode", "EvenWeightSubcode",
"PermutedCode", "ExpurgatedCode", "AugmentedCode", "RemovedElementsCode",
"AddedElementsCode", "ShortenedCode", "LengthenedCode", "ResidueCode",
"ConstructionBCode", "DualCode", "ConversionFieldCode",
"ConstantWeightSubcode", "StandardFormCode" and "CosetCode".

The next sections describe functions that generate a new code out of two
codes.  See "DirectSumCode", "UUVCode", "DirectProductCode",
"IntersectionCode" and "UnionCode".

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{ExtendedCode}
\index{Parity check}

'ExtendedCode( <C> [, <i> ] )'

'ExtendedCode' *extends* the code <C> <i> times and returns the
result. <i> is equal to $1$ by default. Extending is done by adding a
parity check bit after the last coordinate. The coordinates of all
codewords now add up to zero. In the binary case, each codeword has even
weight.

The word length increases by <i>. The size of the code remains the
same. In the binary case, the minimum distance increases by one if it
was odd. In other cases, that is not always true.

A cyclic code in general is no longer cyclic after extending.

|    gap> C1 := HammingCode( 3, GF(2) );
    a linear [7,4,3] Hamming (3,2) code over GF(2)
    gap> C2 := ExtendedCode( C1 );
    a linear [8,4,4] extended code
    gap> IsEquivalentCode( C2, ReedMullerCode( 3, 1 ) );
    true
    gap> List( Elements( C2 ), Weight );
    [ 0, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 8 ]
    gap> PuncturedCode( C2 ) = C1;
    true
    gap> C3 := EvenWeightSubcode( C1 );
    a linear [7,3,4] even weight subcode |

To undo extending, call 'PuncturedCode' (see "PuncturedCode").  The
function 'EvenWeightSubcode' (see "EvenWeightSubcode") also returns a
related code with only even weights, but without changing its word
length.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{PuncturedCode}

'PuncturedCode( <C> )'

'PuncturedCode' *punctures* <C> in the last column, and returns the
result. Puncturing is done simply by cutting off the last column from
each codeword. This means the word length decreases by one. The minimum
distance in general also decrease by one.

'PuncturedCode( <C>, <L> )'

'PuncturedCode' punctures <C> in the columns specified by <L>, a list of
integers. All columns specified by <L> are omitted from each codeword.
If $l$ is the length of <L> (so the number of removed columns), the word
length decreases by $l$. The minimum distance can also decrease by $l$ or
less.

Puncturing a cyclic code in general results in a non-cyclic code. If the
code is punctured in all the columns where a word of minimal weight is
unequal to zero, the dimension of the resulting code decreases.

|    gap> C1 := BCHCode( 15, 5, GF(2) );
    a cyclic [15,7,5] BCH code, delta=5, b=1 over GF(2)
    gap> C2 := PuncturedCode( C1 );
    a linear [14,7,4] punctured code
    gap> ExtendedCode( C2 ) = C1;
    false
    gap> PuncturedCode( C1, [1,2,3,4,5,6,7] );
    a linear [8,7,1..2] punctured code
    gap> PuncturedCode( WholeSpaceCode( 4, GF(5) ) );
    a linear [3,3,1] punctured code  # The dimension decreased from 4 to 3 |

'ExtendedCode' extends the code again (see "ExtendedCode") although in
general this does not result in the old code.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{EvenWeightSubcode}

'EvenWeightSubcode( <C> )'

'EvenWeightSubcode' returns the *even weight subcode* of <C>,
consisting of all codewords of <C> with even weight. If <C> is a
linear code and contains words of odd weight, the resulting code has
a dimension of one less. The minimum distance always increases with
one if it was odd. If <C> is a binary cyclic code, and $g(x)$ is its
generator polynomial, the even weight subcode either has generator
polynomial $g(x)$ (if $g(x)$ is divisible by $x-1$) or $g(x)\*(x-1)$
(if no factor $x-1$ was present in $g(x)$). So the even weight
subcode is again cyclic.

Of course, if all codewords of <C> are already of even weight, the
returned code is equal to <C>.

|    gap> C1 := EvenWeightSubcode( BCHCode( 8, 4, GF(3) ) );
    an (8,33,4..8) even weight subcode
    gap> List( Elements( C1 ), WeightCodeword );
    [ 0, 4, 4, 4, 4, 4, 6, 4, 4, 4, 6, 4, 4, 4, 8, 6, 8, 4, 6, 4, 4, 6,
      4, 4, 6, 8, 4, 4, 6, 4, 8, 4, 6 ]
    gap> EvenWeightSubcode( ReedMullerCode( 3, 1 ) );
    a linear [8,4,4] Reed-Muller (3,1) code over GF(2) |

'ExtendedCode' also returns a related code of only even weights, but
without reducing its dimension (see "ExtendedCode").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{PermutedCode}

'PermutedCode( <C>, <L> )'

'PermutedCode' returns <C> after column permutations. <L> is the
permutation to be executed on the columns of <C>. If <C> is cyclic,
the result in general is no longer cyclic. If a permutation results
in the same code as <C>, this permutation belongs to the
*automorphism group* of <C> (see "AutomorphismGroup"). In any case, the
returned code is *equivalent* to <C> (see "IsEquivalent").

|    gap> C1 := PuncturedCode( ReedMullerCode( 4, 1 ) );
    a linear [15,5,7] punctured code
    gap> C2 := BCHCode( 15, 7, GF(2) );
    a cyclic [15,5,7] BCH code, delta=7, b=1 over GF(2)
    gap> C2 = C1;
    false
    gap> p := CodeIsomorphism( C1, C2 );
    ( 2, 4,14, 9,13, 7,11,10, 6, 8,12, 5)
    gap> C3 := PermutedCode( C1, p );
    A linear [15,5,7] permuted code
    gap> C2 = C3;
    true |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{ExpurgatedCode}

'ExpurgatedCode( <C>, <L> )'

'ExpurgatedCode' *expurgates* code <C> by throwing away codewords in list
<L>.  <C> must be a linear code. <L> must be a list of codeword
input. The generator matrix of the new code no longer is a basis for the
codewords specified by <L>.  Since the returned code is still linear, it
is very likely that, besides the words of <L>, more codewords of <C> are
no longer in the new code.

|    gap> C1 := HammingCode( 4 );; WeightDistribution( C1 );
    [ 1, 0, 0, 35, 105, 168, 280, 435, 435, 280, 168, 105, 35, 0, 0, 1 ]
    gap> L := Filtered( Elements(C1), i -> WeightCodeword(i) = 3 );;
    gap> C2 := ExpurgatedCode( C1, L );
    a linear [15,4,3..4] code, expurgated with 7 word(s)
    gap> WeightDistribution( C2 );
    [ 1, 0, 0, 0, 14, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 ]   |

This function does not work on non-linear codes. For removing words from
a non-linear code, use 'RemovedElementsCode' (see
"RemovedElementsCode"). For expurgating a code of all words of odd
weight, use 'EvenWeightSubcode' (see "EvenWeightSubcode").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{AugmentedCode}

'AugmentedCode( <C>, <L> )'

'AugmentedCode' returns <C> after augmenting. <C> must be a linear code,
<L> must be a list of codeword input. The generator matrix of the new
code is a basis for the codewords specified by <L> as well as the words
that were already in code <C>. Note that the new code in general will
consist of more words than only the codewords of <C> and the words
<L>. The returned code is also a linear code.

|    gap> C31 := ReedMullerCode( 3, 1 );
    a linear [8,4,4] Reed-Muller (3,1) code over GF(2)
    gap> C32 := AugmentedCode(C31,["00000011","00000101","00010001"]);
    a linear [8,7,1..2] code, augmented with 3 word(s)
    gap> C32 = ReedMullerCode( 3, 2 );
    true   |

'AugmentedCode( <C> )'

When called without a list of codewords, 'AugmentedCode' returns <C>
after adding the all-ones vector to the generator matrix. <C> must be a
linear code.  If the all-ones vector was already in the code, nothing
happens and a copy of the argument is returned. If <C> is a binary code
which does not contain the all-ones vector, the complement of all
codewords is added.

|    gap> C1 := CordaroWagnerCode(6);
    a linear [6,2,4] Cordaro-Wagner code over GF(2)
    gap> [0,0,1,1,1,1] in C1;
    true
    gap> C2 := AugmentedCode( C1 );
    a linear [6,3,1..2] code, augmented with 1 word(s)
    gap> [1,1,0,0,0,0] in C2;    # the complement of [001111]
    true  |

The function 'AddedElementsCode' adds elements to the codewords instead
of adding them to the basis (see "AddedElementsCode").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{RemovedElementsCode}

'RemovedElementsCode( <C>, <L> )'

'RemovedElementsCode' returns code <C> after removing a list of
codewords <L> from its elements. <L> must be a list of codeword input.
The result is an unrestricted code.

|    gap> C1 := HammingCode( 4 );; WeightDistribution( C1 );
    [ 1, 0, 0, 35, 105, 168, 280, 435, 435, 280, 168, 105, 35, 0, 0, 1 ]
    gap> L := Filtered( Elements(C1), i -> WeightCodeword(i) = 3 );;
    gap> C2 := RemovedElementsCode( C1, L );
    A (15,2013,d) code over GF(2)
    gap> WeightDistribution( C2 );
    [ 1, 0, 0, 0, 105, 168, 280, 435, 435, 280, 168, 105, 35, 0, 0, 1 ]
    gap> MinimumDistance( C2 );
    3        # C2 is not linear, so the minimum weight does not have to
             # be equal to the minimum distance |

Adding elements to a code is done by the function 'AddedElementsCode'
(see "AddedElementsCode"). To remove codewords from the base of a
linear code, use 'ExpurgatedCode' (see "ExpurgatedCode").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{AddedElementsCode}

'AddedElementsCode( <C>, <L> )'

'AddedElementsCode' returns code <C> after adding a list of codewords <L>
to its elements. <L> must be a list of codeword input. The result is an
unrestricted code.

|    gap> C1 := NullCode( 6, GF(2) );
    a cyclic [6,0,6] nullcode over GF(2)
    gap> C2 := AddedElementsCode( C1, "111111" );
    a (6,2,1..6) code with 1 word(s) added
    gap> IsCyclicCode( C2 );
    true
    gap> C3 := AddedElementsCode( C2, [ "101010", "010101" ] );
    a (6,4,1..6) code with 2 word(s) added
    gap> IsCyclicCode( C3 );
    true    |

To remove elements from a code, use 'RemovedElementsCode' (see
"RemovedElementsCode"). To add elements to the base of a linear code,
use 'AugmentedCode' (see "AugmentedCode").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{ShortenedCode}

'ShortenedCode( <C> )'

'ShortenedCode' returns code <C> shortened by taking a cross section.
If <C> is a linear code, this is done by removing all codewords that
start with a non-zero entry, after which the first column is cut off.
If <C> was a $[n,k,d]$ code, the shortened code generally is a
$[n-1,k-1,d]$ code. It is possible that the dimension remains the
same; it is also possible that the minimum distance increases.

|    gap> C3 := HammingCode( 4 );
    a linear [15,11,3] Hamming (4,2) code over GF(2)
    gap> C4 := ShortenedCode( C3 );
    a linear [14,10,3] shortened code (in [ 1 ]) |

If <C> is a non-linear code, 'ShortenedCode' first checks which
finite field element occurs most often in the first column of the
codewords. The codewords not starting with this element are removed from
the code, after which the first column is cut off. The resulting
shortened code has at least the same minimum distance as <C>.

|    gap> C1 := ElementsCode( ["1000", "1101", "0011" ] );
    A (4,3,d) code over GF(2)
    gap> MinimumDistance( C1 );
    2
    gap> C2 := ShortenedCode( C1 );
    A linear non-cyclic [3,1,2] code over GF(2)
    gap> Elements( C2 );
    [ [ 0 0 0 ], [ 1 0 1 ] ] |

'ShortenedCode( <C>, <L> )'

When called in this format, 'ShortenedCode' repeats the shortening
process on each of the columns specified by <L>. <L> therefore is a
list of integers. The column numbers in <L> are the numbers as they
are *before* the shortening process. If <L> has $l$ entries, the
returned code has a word length of $l$ positions shorter than <C>.

|    gap> C1 := HammingCode( 5, GF(2) );
    A perfect linear [31,26,3] code over GF(2)
    gap> C2 := ShortenedCode( C1, [ 1, 2, 3 ] );
    A linear non-cyclic [28,23,3] code over GF(2)
    gap> OptimalityLinearCode( C2 );
    0 |

The function 'LengthenedCode' lengthens the code again (only for linear
codes), see "LengthenedCode". In general, this is not exactly the inverse
function.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{LengthenedCode}

'LengthenedCode( <C> [, <i> ] )'

'LengtenedCode' returns code <C> lengthened. <C> must be a linear
code. First, the all-ones vector is added to the generator matrix (see
"AugmentedCode"). If the all-ones vector was already a codeword, nothing
happens to the code. Then, the code is extended <i> times (see
"ExtendedCode"). <i> is equal to $1$ by default. If <C> was an $[n,k]$
code, the new code generally is a $[n+i,k+1]$ code.

|    gap> C1 := CordaroWagnerCode( 5 );
    A linear [5,2,3] code over GF(2)
    gap> C2 := LengthenedCode( C1 );
    A linear non-cyclic [6,3,2] code over GF(2) |

'ShortenedCode' shortens the code, see "ShortenedCode". In general, this
is not exactly the inverse function.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{ResidueCode}

'ResidueCode( <C> [, <w> ] )'

The function 'ResidueCode' takes a codeword $c$ of <C> of weight <w> (if
<w> is omitted, a codeword of minimal weight is used). <C> must be a
linear code and <w> must be greater than zero. It removes this word and
all its linear combinations from the code and then punctures the code in
the coordinates where <c> is unequal to zero.  The resulting code is an
$[n-w, k-1, d-\lfloor w\*(q-1)/q \rfloor ]$ code.

|    gap> C1 := BCHCode( 15, 7 );
    A cyclic [15,5,7] code over GF(2)
    gap> C2 := ResidueCode( C1 );
    A linear [8,4,4] code over GF(2)
    gap> c := Codeword( [ 0,0,0,1,0,0,1,1,0,1,0,1,1,1,1 ], C1);;
    gap> C3 := ResidueCode( C1, c );
    A linear [7,4,3] code over GF(2)   |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{ConstructionBCode}

'ConstructionBCode( <C> )'

The function 'ConstructionBCode' takes a binary linear code <C> and
calculates the minimum distance of the dual of <C> (see "DualCode"). It
then removes the columns of the parity check matrix of <C> where a
codeword of the dual code of minimal weight has coordinates unequal to
zero. the resulting matrix is a parity check matrix for an $[n-dd,
k-dd+1, \geq d]$ code, where $dd$ is the minimum distance of the dual of
<C>.

|    gap> C1 := ReedMullerCode( 5, 2 );
    A selfdual linear [32,16,8] code over GF(2)
    gap> C2 := ConstructionBCode( C1 );
    A linear [24,9,8] code over GF(2)
    gap> BoundsMinimumDistance( 24, 9, GF(2) );
    An optimal linear [24,9,d] code over GF(2) has d=8   # So C2 is optimal |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{DualCode}

'DualCode( <C> )'

'DualCode' returns the dual code of <C>. The dual code consists of
all codewords that are orthogonal to the codewords of <C>. If <C> is
a linear code with generator matrix $G$, the dual code has parity
check matrix $G$ (or if <C> has parity check matrix $H$, the dual
code has generator matrix $H$). So if <C> is a linear [n, k] code,
the dual code of <C> is a linear [n, n-k] code. If <C> is a cyclic
code with generator polynomial $g(x)$, the dual code has the
reciprocal polynomial of $g(x)$ as check polynomial.

The dual code is always a linear code, even if <C> is non-linear.

If a code <C> is equal to its dual code, it is called *self-dual*.

|    gap> R := ReedMullerCode(3,1);
    A selfdual linear [8,4,4] code over GF(2)
    gap> R2 := DualCode(R);
    A selfdual linear [8,4,4] code over GF(2)
    gap> R = R2;
    true
    gap> N := WholeSpaceCode(7, GF(4));
    A perfect cyclic [7,7,1] code over GF(4)
    gap> DualCode(N) = NullCode(7, GF(4));
    true  |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{ConversionFieldCode}

'ConversionFieldCode( <C> )'

'ConversionFieldCode' returns code <C> after converting its field. If
the field of <C> is 'GF($q^m$)', the returned code has field
'GF($q$)'. Each symbol of every codeword is replaced by a
concatenation of $m$ symbols from 'GF($q$)'. If <C> is an $(n, M,
d_1)$ code, the returned code is a $(n\*m, M, d_2)$ code, where $d_2
> d_1$.

See also "HorizontalConversionFieldMat".

|    gap> R := RepetitionCode(4, GF(4));
    A cyclic [4,1,4] code over GF(4)
    gap> R2 := ConversionFieldCode(R);
    A linear [8,2,4] code over GF(2)
    gap> Size(R) = Size(R2);
    true
    gap> GeneratorMat(R);
    [ [ Z(2)^0, Z(2)^0, Z(2)^0, Z(2)^0 ] ]
    gap> GeneratorMat(R2);
    [ [ Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2) ],
      [ 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0 ] ] |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{CosetCode}

'CosetCode( <C>, <w> )'

'CosetCode' returns the coset of a code <C> with respect to word <w>.
<w> must be of the codeword type. Then, <w> is added to each codeword of
<C>, yielding the elements of the new code. If <C> is linear and <w> is
an element of <C>, the new code is equal to <C>, otherwise the new code
is an unrestricted code.

Generating a coset is also possible by simply adding the word <w> to
<C>. See "Operations for Codes".

|    gap> H := HammingCode(3, GF(2));
    A perfect linear [7,4,3] code over GF(2)
    gap> c := Codeword("1011011");; c in H;
    false
    gap> C := CosetCode(H, c);
    A (7,16,3) code over GF(2)
    gap> List(Elements(C), el-> Syndrome(H, el));
    [ [ 1 1 1 ], [ 1 1 1 ], [ 1 1 1 ], [ 1 1 1 ], [ 1 1 1 ], [ 1 1 1 ],
      [ 1 1 1 ], [ 1 1 1 ], [ 1 1 1 ], [ 1 1 1 ], [ 1 1 1 ], [ 1 1 1 ],
      [ 1 1 1 ], [ 1 1 1 ], [ 1 1 1 ], [ 1 1 1 ] ]
                    # All elements of the coset have the same syndrome in H
|

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{ConstantWeightSubcode}

'ConstantWeightSubcode( <C>, <w> )'

'ConstantWeightSubcode' returns the subcode of <C> that only has
codewords of weight <w>. The resulting code is a non-linear code, because
it does not contain the all-zero vector.

|   gap> N := NordstromRobinsonCode();; WeightDistribution(N);
    [ 1, 0, 0, 0, 0, 0, 112, 0, 30, 0, 112, 0, 0, 0, 0, 0, 1 ]
    gap> C := ConstantWeightSubcode(N, 8);
    A non-linear (16,30,d) code over GF(2), d in [6..8]
    gap> WeightDistribution(C);
    [ 0, 0, 0, 0, 0, 0, 0, 0, 30, 0, 0, 0, 0, 0, 0, 0, 0 ]  |

'ConstantWeightSubcode( <C> )'

In this format, 'ConstantWeightSubcode' returns the subcode of <C>
consisting of all minimum weight codewords of <C>.

|    gap> E := ExtendedTernaryGolayCode();; WeightDistribution(E);
    [ 1, 0, 0, 0, 0, 0, 264, 0, 0, 440, 0, 0, 24 ]
    gap> C := ConstantWeightSubcode(E);
    A non-linear (12,264,6) code over GF(3)
    gap> WeightDistribution(C);
    [ 0, 0, 0, 0, 0, 0, 264, 0, 0, 0, 0, 0, 0 ]   |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{StandardFormCode}

'StandardFormCode( <C> )'

'StandardFormCode' returns <C> after putting it in standard form. If
<C> is a non-linear code, this means the elements are organized using
lexicographical order. This means they form a legal {\GAP} 'Set'.

If <C> is a linear code, the generator matrix and parity check matrix are
put in standard form. The generator matrix then has an identity matrix in
its left part, the parity check matrix has an identity matrix in its
right part. Although {\GUAVA} always puts both matrices in a standard
form using 'BaseMat', this never alters the code.  'StandardFormCode'
even applies column permutations if unavoidable, and thereby changes the
code. The column permutations are recorded in the construction history of
the new code (see "Display"). <C> and the new code are of course
equivalent.

If <C> is a cyclic code, its generator matrix cannot be put in the usual
upper triangular form, because then it would be inconsistent with the
generator polynomial. The reason is that generating the elements from the
generator matrix would result in a different order than generating the
elements from the generator polynomial. This is an unwanted effect, and
therefore 'StandardFormCode' just returns a copy of <C> for cyclic codes.

|    gap> G := GeneratorMatCode( Z(2) * [ [0,1,1,0], [0,1,0,1], \
    [0,0,1,1] ], GF(2) );;
    gap> Display(G);
    A linear [4,2,d] code over GF(2)
    Construction:
            User defined linear code (by generator matrix), wordlength 4
    Generator matrix:
            [ 0 1 0 1 ]
            [ 0 0 1 1 ]
    gap> S := StandardFormCode(G);; Display(S);
    A linear [4,2,d] code over GF(2)
    Construction:
            User defined linear code (by generator matrix), wordlength 4
            Put in standard form, permuted with (1,3,2)
    Generator matrix:
            [ 1 0 0 1 ]
            [ 0 1 0 1 ]    |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{DirectSumCode}

'DirectSumCode( <$C_1$>, <$C_2$> )'

'DirectSumCode' returns the direct sum of codes <$C_1$> and <$C_2$>. The
direct sum code consists of every codeword of <$C_1$> concatenated by
every codeword of <$C_2$>. Therefore, if <$C_i$> was a
$(n_i,M_i,d_i)$ code, the result is a $(n_1+n_2,M_1\*M_2,min(d_1,d_2))$
code.

If both <$C_1$> and <$C_2$> are linear codes, the result is also a linear
code. If one of them is non-linear, the direct sum is non-linear
too. In general, a direct sum code is not cyclic.

Performing a direct sum can also be done by adding two codes (see
"Operations for Codes").
Another often used method is the \"u, u+v\"-construction,
described in "UUVCode".

|    gap> E := ElementsCode(Z(7)^0*[[1,0], [4,5]]);;
    gap> E2 := ElementsCode(Z(7)^0*[[0,0,0],[3,3,3]]);;
    gap> D := DirectSumCode(E, E2);;
    gap> Elements(D);
    [ [ 1 0 0 0 0 ], [ 1 0 3 3 3 ], [ 4 5 0 0 0 ], [ 4 5 3 3 3 ] ]
    gap> D = E + E2;   # addition = direct sum
    true   |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{UUVCode}

'UUVCode( <$C_1$>, <$C_2$> )'

'UUVCode' returns the so-called $(u\|u+v)$ construction applied to
<$C_1$> and <$C_2$>. The resulting code consists of every codeword $u$ of
<$C_1$> concatenated by the sum of $u$ and every codeword $v$ of
<$C_2$>. If <$C_1$> and <$C_2$> have different word lengths, sufficient
zeros are added to the shorter code to make this sum possible. If <$C_i$>
is a $(n_i,M_i,d_i)$ code, the result is a
$(n_1+max(n_1,n_2),M_1\*M_2,min(2\*d_1,d_2))$ code.

If both <$C_1$> and <$C_2$> are linear codes, the result is also a linear
code. If one of them is non-linear, the UUV sum is non-linear too. In
general, a UUV sum code is not cyclic.

The function 'DirectSumCode' returns another sum of codes (see
"DirectSumCode").

|    gap> C1 := EvenWeightSubcode(WholeSpaceCode(4, GF(2)));
    A cyclic [4,3,2] code over GF(2)
    gap> C2 := RepetitionCode(4, GF(2));
    A cyclic [4,1,4] code over GF(2)
    gap> R := UUVCode(C1, C2);
    A linear [8,4,4] code over GF(2)
    gap> R = ReedMullerCode(3,1);
    true   |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{DirectProductCode}

'DirectProductCode( <$C_1$>, <$C_2$> )'

'DirectProductCode' returns the direct product of codes <$C_1$> and
<$C_2$>. Both must be linear codes. Suppose <$C_i$> has generator matrix
$G_i$. The direct product of <$C_1$> and <$C_2$> then has the Kronecker
product of $G_1$ and $G_2$ as the generator matrix (see
'KroneckerProduct').

If <$C_i$> is a $[n_i, k_i, d_i]$ code, the direct product then is a
$[n_1\*n_2,k_1\*k_2,d_1\*d_2]$ code.

|    gap> L1 := LexiCode(10, 4, GF(2));
    A linear [10,5,d] code over GF(2), d in [4..10]
    gap> L2 := LexiCode(8, 3, GF(2));
    A linear [8,4,d] code over GF(2), d in [3..8]
    gap> D := DirectProductCode(L1, L2);
    A linear [80,20,d] code over GF(2), d in [12..80]
    gap> MinimumDistance(D);
    12    |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IntersectionCode}

'IntersectionCode( <$C_1$>, <$C_2$> )'

'IntersectionCode' returns the intersection of codes <$C_1$> and <$C_2$>.
This code consists of all codewords that are both in <$C_1$> and <$C_2$>.
If both codes are linear, the result is also linear. If both are
cyclic, the result is also cyclic.

|    gap> C := CyclicCodes(7, GF(2));
    [ A cyclic [7,7,d] code over GF(2), A cyclic [7,6,d] code over GF(2),
      A cyclic [7,3,d] code over GF(2), A cyclic [7,0,7] code over GF(2),
      A cyclic [7,3,d] code over GF(2), A cyclic [7,4,d] code over GF(2),
      A cyclic [7,1,d] code over GF(2), A cyclic [7,4,d] code over GF(2) ]
    gap> IntersectionCode(C[6], C[8]) = C[7];
    true     |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{UnionCode}

'UnionCode( <$C_1$>, <$C_2$> )'

'UnionCode' returns the union of codes <$C_1$> and <$C_2$>. This code
consists of the union of all codewords of <$C_1$> and <$C_2$> and all
linear combinations. Therefore this function works only for linear
codes. The function 'AddedElementsCode' can be used for non-linear codes,
or if the resulting code should not include linear combinations. See
"AddedElementsCode".  If both arguments are cyclic, the result is also
cyclic.

|   gap> G := GeneratorMatCode([[1,0,1],[0,1,1]]*Z(2)^0, GF(2));
    A linear [3,2,d] code over GF(2)
    gap> H := GeneratorMatCode([[1,1,1]]*Z(2)^0, GF(2));
    A linear [3,1,d] code over GF(2)
    gap> U := UnionCode(G, H);
    A cyclic [3,3,1] code over GF(2)
    gap> c := Codeword("010");; c in G;
    false
    gap> c in H;
    false
    gap> c in U;
    true  |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% properties of codes (basic functions)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Basic Functions for Codes}

A few sections now follow that describe {\GUAVA}\'s basic functions on
codes.

The first section describes {\GAP} functions that work on *Domains* (see
'Domains'), but are also applicable for codes (see "Domain Functions for
Codes").

The next section describes three {\GAP} input/output functions (see
"Printing and Saving Codes").

The next sections describe functions that return the matrices and
polynomials that define a code (see "GeneratorMat", "CheckMat",
"GeneratorPol", "CheckPol", "RootsOfCode").

The next sections describe function that return the basic parameters
of codes (see "WordLength", "Redundancy", "MinimumDistance" and
"CoveringRadius").

The next sections describe functions that return distance and weight
distributions (see "WeightDistribution", "InnerDistribution",
"OuterDistribution" and "DistancesDistribution").

The next sections describe boolean functions on codes (see
"IsLinearCode", "IsCyclicCode", "IsPerfectCode", "IsSelfDualCode",
"IsSelfOrthogonalCode", and "IsMDSCode").

The next sections describe functions about equivalence of codes (see
"IsEquivalent", "CodeIsomorphism" and "AutomorphismGroup").

The next sections describe functions related to decoding (see "Decode",
"Syndrome", "SyndromeTable" and "StandardArray").

The next section describes a function that displays a code (see
"Display").

The last section describes the function 'CodewordNr' (see "CodewordNr").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% general functions for codes

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Domain Functions for Codes}

These are some {\GAP} functions that work on 'Domains' in general. Their
specific effect on 'Codes' is explained here.

'IsFinite( <C> )'

'IsFinite' is an implementation of the {\GAP} domain function
'IsFinite'. It returns true for a code <C>.

|    gap> IsFinite( RepetitionCode( 1000, GF(11) ) );
    true |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
'Size( <C> )'

'Size' returns the size of <C>, the number of elements of the code. If
the code is linear, the size of the code is equal to $q^k$, where $q$ is
the size of the base field of <C> and $k$ is the dimension.

|    gap> Size( RepetitionCode( 1000, GF(11) ) );
    11
    gap> Size( NordstromRobinsonCode() );
    256 |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
'Field( <C> )'

'Field' returns the base field of a code <C>. Each element of <C>
consists of elements of this base field. If the base field is $F$, and
the word length of the code is $n$, then the codewords are elements of
$F^n$.  If <C> is a cyclic code, its elements are interpreted as
polynomials with coefficients over $F$.

|    gap> C1 := ElementsCode([[0,0,0], [1,0,1], [0,1,0]], GF(4));
    a (3,3,1..3) user defined unrestricted code over GF(4)
    gap> Field( C1 );
    GF(2^2)
    gap> Field( HammingCode( 3, GF(9) ) );
    GF(3^2) |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
'Dimension( <C> )'

'Dimension' returns the parameter $k$ of <C>, the dimension of the code,
or the number of information symbols in each codeword. The dimension is
not defined for non-linear codes; 'Dimension' then returns an error.

|    gap> Dimension( NordstromRobinsonCode() );
    Error, dimension is only defined for linear codes in
    struct.operations.Dimension( struct ) called from
    Dimension( NordstromRobinsonCode(  ) ) called from
    main loop
    brk>
    gap> Dimension( NullCode( 5, GF(5) ) );
    0
    gap> C := BCHCode( 15, 4, GF(4) );
    a cyclic [15,7,5] BCH code, delta=5, b=1 over GF(4)
    gap> Dimension( C );
    7
    gap> Size( C ) = Size( Field( C ) ) ^ Dimension( C );
    true |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
'Elements( <C> )'

'Elements' returns a list of the elements of <C>. These elements are of
the codeword type (see "Codewords"). Note that for large codes,
generating the elements may be very time- and memory-consuming. For
generating a specific element or a subset of the elements, use
'CodewordNr' (see "CodewordNr"), 'MinimumWeightWords' (see ...).

|    gap> C := ConferenceCode( 5 );
    a (5,12,2) conference code over GF(2)
    gap> Elements( C );
    [ [ 0 0 0 0 0 ], [ 1 1 0 1 0 ], [ 1 1 1 0 0 ], [ 0 1 1 0 1 ],
      [ 1 0 0 1 1 ], [ 0 0 1 1 1 ], [ 1 0 1 0 1 ], [ 0 1 0 1 1 ],
      [ 1 0 1 1 0 ], [ 0 1 1 1 0 ], [ 1 1 0 0 1 ], [ 1 1 1 1 1 ] ]
    gap> CodewordNr( C, [ 1, 2 ] );
    [ [ 0 0 0 0 0 ], [ 1 1 0 1 0 ] ] |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Printing and Saving Codes}

'Print( <C> )'

'Print' prints information about <C>. This is the same as typing the
identifier <C> at the {\GAP}-prompt.

If the argument is an unrestricted code, information in the form\\
|    a (n, M, d) ... code over GF(q)|\\
is printed, where $n$ is the word length, $M$ the number of elements of
the code and $d$ the minimum distance.

If the argument is a linear code, information in the form\\
|    A linear [n, k, d] code over GF(q)|\\
is printed, where $n$ is the word length, $k$ the dimension of the code
and $d$ the minimum distance.

In all cases, if $d$ is not yet known, it is displayed in the form
|<lowerbound> .. <upperbound>|.

The function 'Display' gives more information. See "Display".

|    gap> C1 := ExtendedCode( HammingCode( 3, GF(2) ) );
    a linear [8,4,4] extended code
    gap> Print( "This is ", NordstromRobinsonCode(), ". \n");
    This is a (16,256,6) Norstrom-Robinson code over GF(2). |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
'String( <C> )'

'String' returns information about <C> in a string. This function is used
by 'Print' (see 'Print').

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
'Save( <filename>, <C>, <varname> )'

'Save' appends the code <C> to a file with file name <filename>. If the
file does not exist, it is created. The code is saved with variable name
<varname>.  The code can be read back by calling 'Read(filename)'. The
code then has name <varname>. Note that <filename> and <varname> are
strings.

|    gap> C1 := HammingCode( 4, GF(3) );
    a linear [40,36,3] Hamming (4,3) code over GF(3)
    gap> Save( "mycodes.lib", C1, "Ham_4_3");
    gap> Read( "mycodes.lib" ); Ham_4_3;
    a linear [40,36,3] Hamming (4,3) code over GF(3)
    gap> Ham_4_3 = C1;
    true |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{GeneratorMat}

'GeneratorMat( <C> )'

'GeneratorMat' returns a generator matrix of <C>. The code consists of
all linear combinations of the rows of this matrix.

If until now no generator matrix of <C> was determined, it is computed
from either the parity check matrix, the generator or check polynomial or
the elements (if possible), whichever is available.

If <C> is a non-linear code, the function returns an error.

The function 'Display' displays the generator matrix of <C>. See
"Display".

|    gap> GeneratorMat( HammingCode( 3, GF(2) ) );
    [ [ Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0, Z(2)^0 ],
    [ 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0 ],
    [ 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0, Z(2)^0, 0*Z(2) ],
    [ 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0, Z(2)^0, Z(2)^0, Z(2)^0 ] ]
    gap> GeneratorMat( RepetitionCode( 5, GF(25) ) );
    [ [ Z(5)^0, Z(5)^0, Z(5)^0, Z(5)^0, Z(5)^0 ] ]
    gap> GeneratorMat( NullCode( 14, GF(4) ) );
    [  ]
    gap> GeneratorMat( ElementsCode( [[0, 0, 1 ], [1, 1, 0 ]], GF(2) ));
    Error, non-linear codes don't have a generator matrix in
    C.operations.GeneratorMat( C ) called from
    GeneratorMat( ElementsCode( [ [ 0, 0, 1 ], [ 1, 1, 0 ] ], GF( 2 ) )
     ) called from
    main loop
    brk>   |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{CheckMat}

'CheckMat( <C> )'

'CheckMat' returns a parity check matrix of <C>. The code consists of all
words orthogonal to each of the rows of this matrix. The transpose of the
matrix is a right inverse of the generator matrix. The parity check
matrix is computed from either the generator matrix, the generator or
check polynomial or the elements of <C> (if possible), whichever is
available.

If <C> is a non-linear code, the function returns an error.

|    gap> CheckMat( HammingCode(3, GF(2) ) );
    [ [ 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0, Z(2)^0, Z(2)^0, Z(2)^0 ],
      [ 0*Z(2), Z(2)^0, Z(2)^0, 0*Z(2), 0*Z(2), Z(2)^0, Z(2)^0 ],
      [ Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0 ] ]
    gap> CheckMat( RepetitionCode( 5, GF(25) ) );
    [ [ Z(5)^0, Z(5)^2, 0*Z(5), 0*Z(5), 0*Z(5) ],
      [ 0*Z(5), Z(5)^0, Z(5)^2, 0*Z(5), 0*Z(5) ],
      [ 0*Z(5), 0*Z(5), Z(5)^0, Z(5)^2, 0*Z(5) ],
      [ 0*Z(5), 0*Z(5), 0*Z(5), Z(5)^0, Z(5)^2 ] ]
    gap> CheckMat( WholeSpaceCode( 12, GF(4) ) );
    [  ]    |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{GeneratorPol}

'GeneratorPol( <C> )'

'GeneratorPol' returns the generator polynomial of <C>. The code consists
of all multiples of the generator polynomial modulo $x^{n}-1$ where $n$
is the word length of <C>. The generator polynomial is determined from
either the check polynomial, the generator or check matrix or the
elements of <C> (if possible), whichever is available.

If <C> is not a cyclic code, the function returns 'false'.

|    gap> GeneratorPol(GeneratorMatCode([[1, 1, 0], [0, 1, 1]], GF(2)));
    Z(2)^0*(X(GF(2)) + 1)
    gap> GeneratorPol( WholeSpaceCode( 4, GF(2) ) );
    X(GF(2))^0
    gap> GeneratorPol( NullCode( 7, GF(3) ) );
    Z(3)^0*(X(GF(3))^7 + 2) |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{CheckPol}

'CheckPol( <C> )'

'CheckPol' returns the check polynomial of <C>. The code consists of all
polynomials $f$ with $f\*h = 0\ ($mod $x^n-1)$, where $h$ is the check
polynomial, and $n$ is the word length of <C>. The check polynomial is
computed from the generator polynomial, the generator or parity check
matrix or the elements of <C> (if possible), whichever is available.

If <C> if not a cyclic code, the function returns an error.

|    gap> CheckPol(GeneratorMatCode([[1, 1, 0], [0, 1, 1]], GF(2)));
    Z(2)^0*(X(GF(2))^2 + X(GF(2)) + 1)
    gap> CheckPol(WholeSpaceCode(4, GF(2)));
    Z(2)^0*(X(GF(2))^4 + 1)
    gap> CheckPol(NullCode(7,GF(3)));
    X(GF(3))^0
    gap> CheckPol(ElementsCode( [ [0, 0, 1 ], [1, 1, 0 ] ], GF(2) ) );
    false  |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{RootsOfCode}

'RootsOfCode( <C> )'

'RootsOfCode' returns a list of all zeros of the generator polynomial of
a cyclic code <C>. These are finite field elements in the splitting field
of the generator polynomial, $GF(q^m)$, $m$ is the multiplicative order
of the size of the base field of the code, modulo the word length.

The reverse proces, constructing a code from a set of roots, can be
carried out by the function 'RootsCode' (see "RootsCode").

|    gap> C1 := ReedSolomonCode( 16, 5 );
    a cyclic [16,12,5] Reed-Solomon code over GF(17)
    gap> RootsOfCode( C1 );
    [ Z(17), Z(17)^2, Z(17)^3, Z(17)^4 ]
    gap> C2 := RootsCode( 16, last );
    a cyclic [16,12,5] code defined by roots over GF(17)
    gap> C1 = C2;
    true |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{WordLength}

'WordLength( <C> )'

'WordLength' returns the parameter $n$ of <C>, the word length of the
elements. Elements of cyclic codes are polynomials of maximum degree
$n-1$, as calculations are carried out modulo $x^{n}-1$.

|    gap> WordLength( NordstromRobinsonCode() );
    16
    gap> WordLength( PuncturedCode( WholeSpaceCode(7) ) );
    6
    gap> WordLength( UUVCode( WholeSpaceCode(7), RepetitionCode(7) ) );
    14    |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Redundancy}

'Redundancy( <C> )'

'Redundancy' returns the redundancy $r$ of <C>, which is equal to the
number of check symbols in each element. If <C> is not a linear code the
redundancy is not defined and 'Redundancy' returns an error.

If a linear code <C> has dimension $k$ and word length $n$, it has
redundancy $r=n-k$.

|    gap> C := TernaryGolayCode();
    a cyclic [11,6,5] ternary Golay code over GF(3)
    gap> Redundancy(C);
    5
    gap> Redundancy( DualCode(C) );
    6  |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{MinimumDistance}

'MinimumDistance( <C> )'

'MinimumDistance' returns the minimum distance of <C>, the largest
integer $d$ with the property that every element of <C> has at least a
Hamming distance $d$ (see "Distance") to any other element of <C>. For
linear codes, the minimum distance is equal to the minimum weight. This
means that $d$ is also the smallest positive value with $w[d+1] \neq 0$,
where $w$ is the weight distribution of <C> (see
"WeightDistribution"). For unrestricted codes, $d$ is the smallest
positive value with $w[d+1] \neq 0$, where $w$ is the inner distribution
of <C> (see "InnerDistribution").

For codes with only one element, the minimum distance is defined to be
equal to the word length.

|    gap> C := MOLSCode(7);; MinimumDistance(C);
    3
    gap> WeightDistribution(C);
    [ 1, 0, 0, 24, 24 ]
    gap> MinimumDistance( WholeSpaceCode( 5, GF(3) ) );
    1
    gap> MinimumDistance( NullCode( 4, GF(2) ) );
    4
    gap> C := ConferenceCode(9);; MinimumDistance(C);
    4
    gap> InnerDistribution(C);
    [ 1, 0, 0, 0, 63/5, 9/5, 18/5, 0, 9/10, 1/10 ]  |

'MinimumDistance( <C>, <w> )'

In this form, 'MinimumDistance' returns the minimum distance of a
codeword <w> to the code <C>, also called the *distance to <C>*. This is
the smallest value $d$ for which there is an element <c> of the code <C>
which is at distance $d$ from <w>. So $d$ is also the minimum value for
which $D[d+1] \neq 0$, where $D$ is the distance distribution of <w> to
<C> (see "DistancesDistribution").

Note that <w> must be an element of the same vector space as the elements
of <C>. <w> does not necessarily belong to the code (if it does, the
minimum distance is zero).

|    gap> C := MOLSCode(7);; w := CodewordNr( C, 17 );
    [ 2 2 4 6 ]
    gap> MinimumDistance( C, w );
    0
    gap> C := RemovedElementsCode( C, w );; MinimumDistance( C, w );
    3                           # so w no longer belongs to C |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{CoveringRadius}

'CoveringRadius( <C> )'

'CoveringRadius' returns the covering radius of <C>. This is the
smallest number $r$ with the property that each element $v$ of the
vector space of <C> has at most a distance $r$ to the code <C>. So
for each vector $v$ there must be an element $c$ of <C> with
$d(v,c) \<= r$.

If <C> is a perfect code (see "IsPerfectCode"), the covering radius is
equal to $t$, the number of errors the code can correct, where $d =
2\*t+1$, with $d$ the minimum distance of <C> (see "MinimumDistance").

|    gap> H := HammingCode(4, GF(2));; IsPerfectCode(H);
    true
    gap> CoveringRadius(H);
    1                       # Hamming codes have minimum distance 3
    gap> CoveringRadius(ReedSolomonCode(7,4));
    3   |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{WeightDistribution}

'WeightDistribution( <C> )'

'WeightDistribution' returns the weight distribution of <C>, as a
vector. The $i^{th}$ element of this vector contains the number of
elements of <C> with weight $i-1$. For linear codes, the weight
distribution is equal to the inner distribution (see
"InnerDistribution").

Suppose $w$ is the weight distribution of <C>. If <C> is linear, it
must have the zero codeword, so $w[1] = 1$ (one word of weight 0).

|    gap> WeightDistribution( ConferenceCode(9) );
    [ 1, 0, 0, 0, 0, 18, 0, 0, 0, 1 ]
    gap> WeightDistribution( RepetitionCode( 7, GF(4) ) );
    [ 1, 0, 0, 0, 0, 0, 0, 3 ]
    gap> WeightDistribution( WholeSpaceCode( 5, GF(2) ) );
    [ 1, 5, 10, 10, 5, 1 ]  |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{InnerDistribution}

'InnerDistribution( <C> )'

'InnerDistribution' returns the inner distribution of <C>. The $i^{th}$
element of the vector contains the average number of elements of <C> at
distance $i-1$ to an element of <C>. For linear codes, the inner
distribution is equal to the weight distribution (see
"WeightDistribution").

Suppose $w$ is the inner distribution of <C>. Then $w[1] = 1$,
because each element of <C> has exactly one element at distance zero
(the element itself). The minimum distance of <C> is the smallest
value $d > 0$ with $w[d+1] \neq 0$, because a distance between zero
and $d$ never occurs. See "MinimumDistance".

|    gap> InnerDistribution( ConferenceCode(9) );
    [ 1, 0, 0, 0, 63/5, 9/5, 18/5, 0, 9/10, 1/10 ]
    gap> InnerDistribution( RepetitionCode( 7, GF(4) ) );
    [ 1, 0, 0, 0, 0, 0, 0, 3 ]  |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{OuterDistribution}

'OuterDistribution( <C> )'

The function 'OuterDistribution' returns a list of length $q^n$, where
$q$ is the size of the base field of <C> and $n$ is the word length. The
elements of the list consist of an element of $(GF(q))^n$ (this is a
codeword type) and the distribution of distances to the code (a list of
integers).  This table is *very* large, and for $n > 20$ it will not fit
in the memory of most computers. The function 'DistancesDistribution'
(see "DistancesDistribution") can be used to calculate one entry of the
list.

|    gap> C := RepetitionCode( 3, GF(2) );
    a cyclic [3,1,3] repetition code over GF(2)
    gap> OD := OuterDistribution(C);
    [ [ [ 0 0 0 ], [ 1, 0, 0, 1 ] ], [ [ 1 1 1 ], [ 1, 0, 0, 1 ] ],
      [ [ 0 0 1 ], [ 0, 1, 1, 0 ] ], [ [ 1 1 0 ], [ 0, 1, 1, 0 ] ],
      [ [ 1 0 0 ], [ 0, 1, 1, 0 ] ], [ [ 0 1 1 ], [ 0, 1, 1, 0 ] ],
      [ [ 0 1 0 ], [ 0, 1, 1, 0 ] ], [ [ 1 0 1 ], [ 0, 1, 1, 0 ] ] ]
    gap> WeightDistribution(C) = OD[1][2];
    true
    gap> DistancesDistribution( C, Codeword("110") ) = OD[4][2];
    true  |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{DistancesDistribution}

'DistancesDistribution( <C>, <w> )'

'DistancesDistribution' returns a distribution of the distances of all
elements of <C> to a codeword <w> in the same vector space. The $i^{th}$
element of the distance distribution is the number of codewords of <C>
that have distance $i-1$ to <w>. The smallest value $d$ with $w[d+1] \neq
0$ is defined as the *distance to <C>* (see "MinimumDistance").

|    gap> H := HadamardCode(20);
    a (20,40,10) Hadamard code of order 20 over GF(2)
    gap> c := Codeword("10110101101010010101", H);
    [ 1 0 1 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 ]
    gap> DistancesDistribution(H, c);
    [ 0, 0, 0, 0, 0, 1, 0, 7, 0, 12, 0, 12, 0, 7, 0, 1, 0, 0, 0, 0, 0 ]
    gap> MinimumDistance(H, c);
    5                           # distance to H  |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsPerfectCode}

'IsPerfectCode( <C> )'

'IsPerfectCode' returns 'true' if <C> is a perfect code. For a code with
odd minimum distance $d = 2t+1$, this is the case when every word of the
vector space of <C> is at distance at most $t$ from exactly one element
of <C>. Codes with even minimum distance are never perfect.

In fact, a code that is not *trivial perfect* (the binary repetition
codes of odd length, the codes consisting of one word, and the codes
consisting of the whole vector space), and does not have the parameters
of a Hamming- or Golay-code, cannot be perfect.

|    gap> H := HammingCode(2);
    a linear [3,1,3] Hamming (2,2) code over GF(2)
    gap> IsPerfectCode( H );
    true
    gap> IsPerfectCode( ElementsCode( [ [1,1,0], [0,0,1] ], GF(2) ) );
    true
    gap> IsPerfectCode( ReedSolomonCode( 6, 3 ) );
    false
    gap> IsPerfectCode(BinaryGolayCode());
    true  |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsMDSCode}

'IsMDSCode( <C> )'

'IsMDSCode' returns true if <C> is a *Maximum Distance Seperable code*,
or MDS code for short. A linear $[n, k, d]$-code of length $n$, dimension
$k$ and minimum distance $d$ is an MDS code if $k=n-d+1$, in other words
if <C> meets the Singleton bound (see "UpperBoundSingleton"). An
unrestricted $(n, M, d)$ code is called MDS if $k=n-d+1$, with $k$ equal
to the largest integer less than or equal to the logarithm of M with base
$q$, the size of the base field of <C>.

Well known MDS codes include the repetition codes, the whole space codes,
the even weight codes (these are the only *binary* MDS Codes) and the
Reed-Solomon codes.

|    gap> C1 := ReedSolomonCode( 6, 3 );
    a cyclic [6,4,3] Reed-Solomon code over GF(7)
    gap> IsMDSCode( C1 );
    true    # 6-3+1 = 4
    gap> IsMDSCode( QRCode( 23, GF(2) ) );
    false |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsSelfDualCode}

'IsSelfDualCode( <C> )'

'IsSelfDualCode' returns 'true' if <C> is self-dual, i.e. when <C> is
equal to its dual code (see also "DualCode"). If a code is self-dual, it
is automatically self-orthogonal (see "IsSelfOrthogonalCode").

If <C> is a non-linear code, it cannot be self-dual, so 'false' is
returned.  A linear code can only be self-dual when its dimension $k$ is
equal to the redundancy $r$.

|    gap> IsSelfDualCode( ExtendedBinaryGolayCode() );
    true
    gap> C := ReedMullerCode( 3, 1 );
    a linear [8,4,4] Reed-Muller (3,1) code over GF(2)
    gap> DualCode( C ) = C;
    true |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsSelfOrthogonalCode}

'IsSelfOrthogonalCode( <C> )'

'IsSelfOrthogonalCode' returns 'true' if <C> is *self-orthogonal*.  A
code is self-orthogonal if every element of <C> is orthogonal to all
elements of <C>, including itself. In the linear case, this simply means
that the generator matrix of <C> multiplied with its transpose yields a
null matrix.

In addition, a code is *self-dual* if it contains all vectors that its
elements are orthogonal to (see "IsSelfDualCode").

|    gap> R := ReedMullerCode(4,1);
    a linear [16,5,8] Reed-Muller (4,1) code over GF(2)
    gap> IsSelfOrthogonalCode(R);
    true
    gap> IsSelfDualCode(R);
    false   |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsEquivalent}

'IsEquivalent( <$C_1$>, <$C_2$> )'

'IsEquivalent' returns true if <$C_1$> and <$C_2$> are equi\-valent
codes.  This is the case if <$C_1$> can be obtained from <$C_2$> by
carrying out column permutations. {\GUAVA} only handles binary codes. The
external program 'desauto' from *J.S. Leon* is used to compute the
isomorphism between the codes.  If <$C_1$> and <$C_2$> are equal, they
are also equivalent.

Note that the algorithm is *very* slow for non-linear codes.

|    gap> H := GeneratorPolCode([1,1,0,1]*Z(2), 7, GF(2));
    a cyclic [7,4,1..3] code defined by generator polynomial over GF(2)
    gap> H = HammingCode(3, GF(2));
    false
    gap> IsEquivalent(H, HammingCode(3, GF(2)));
    true                        # H is equivalent to a Hamming code
    gap> CodeIsomorphism(H, HammingCode(3, GF(2)));
    (3,4)(5,6,7)     |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{CodeIsomorphism}

'CodeIsomorphism( <$C_1$>, <$C_2$> )'

If the two codes <$C_1$> and <$C_2$> are equivalent codes (see
"IsEquivalent"), 'CodeIsomorphism' returns the permutation that
transforms <$C_1$> into <$C_2$>. If the codes are not equivalent, it
returns 'false'.

|    gap> H := GeneratorPolCode([1,1,0,1]*Z(2), 7, GF(2));
    a cyclic [7,4,1..3] code defined by generator polynomial over GF(2)
    gap> CodeIsomorphism(H, HammingCode(3, GF(2)));
    (3,4)(5,6,7)
    gap> PermutedCode(H, (3,4)(5,6,7)) = HammingCode(3, GF(2));
    true      |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{AutomorphismGroup}

'AutomorphismGroup( <C> )'

'AutomorphismGroup' returns the *automorphism group* of a binary code
<C>. This is the largest permutation group of degree $n$ such that each
permutation applied to the columns of <C> again yields <C>. {\GUAVA} uses
the external program 'desauto' from *J.S. Leon* to compute the
automorphism group. The function 'PermutedCode' permutes the columns of a
code (see "PermutedCode").

|    gap> R := RepetitionCode(7,GF(2));
    a cyclic [7,1,7] repetition code over GF(2)
    gap> AutomorphismGroup(R);
    Group( (1,2), (2,3), (3,4), (4,5), (5,6), (6,7) )
                            # every permutation keeps R identical
    gap> C := CordaroWagnerCode(7);
    a linear [7,2,4] Cordaro-Wagner code over GF(2)
    gap> Elements(C);
    [ [ 0 0 0 0 0 0 0 ], [ 1 1 1 1 1 0 0 ], [ 0 0 1 1 1 1 1 ],
      [ 1 1 0 0 0 1 1 ] ]
    gap> AutomorphismGroup(C);
    Group( (3,4), (4,5), (1,6)(2,7), (1,2), (6,7) )
    gap> C2 :=  PermutedCode(C, (1,6)(2,7));
    a linear [7,2,4] column permutation with (1,6)(2,7)
    gap> Elements(C2);
    [ [ 0 0 0 0 0 0 0 ], [ 0 0 1 1 1 1 1 ], [ 1 1 1 1 1 0 0 ],
      [ 1 1 0 0 0 1 1 ] ]
    gap> C2 = C;
    true   |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Decode}

'Decode( <C>, <c> )'

'Decode' decodes <c> with respect to code <C>. <c> is a codeword or a
list of codewords. First, possible errors in <c> are corrected, then the
codeword is decoded to an information codeword $x$. If the code record
has a field 'specialDecoder', this special algorithm is used to decode
the vector.  Hamming codes and BCH codes have such a special algorithm.
Otherwise, syndrome decoding is used. Encoding is done by multiplying the
information vector with the code (see "Operations for Codes").

A special decoder can be created by defining a function\\
|C.specialDecoder := function(C, c)|.

The function uses the arguments <C>, the code record itself, and <c>, a
vector of the codeword type, to decode <c> to an information word. A
normal decoder would take a codeword <c> of the same word length and
field as <C>, and would return a information word of length $k$, the
dimension of <C>. The user is not restricted to these normal demands
though, and can for instance define a decoder for non-linear codes.

|    gap> C := HammingCode(3);
    a linear [7,4,3] Hamming (3,2) code over GF(2)
    gap> c := "1010"*C;                    # encoding
    [ 1 0 1 0 1 0 1 ]
    gap> Decode(C, c);                     # decoding
    [ 1 0 1 0 ]
    gap> Decode(C, Codeword("0010101"));
    [ 1 0 1 0 ]                            # one error corrected
    gap> C.specialDecoder := function(C, c)
    > return NullWord(Dimension(C));
    > end;
    function ( C, c ) ... end
    gap> Decode(C, c);
    [ 0 0 0 0 ]           # new decoder always returns null word |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Syndrome}

'Syndrome( <C>, <c> )'

'Syndrome' returns the syndrome of word <c> with respect to a code
<C>. <c> is a word of the vector space of <C>. If <c> is an element of
<C>, the syndrome is a zero vector. The syndrome can be used for looking
up an error vector in the syndrome table (see "SyndromeTable") that is
needed to correct an error in <c>.

A syndrome is not defined for non-linear codes. 'Syndrome' then returns
an error.

|    gap> C := HammingCode(4);
    a linear [15,11,3] Hamming (4,2) code over GF(2)
    gap> v := CodewordNr( C, 7 );
    [ 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 ]
    gap> Syndrome( C, v );
    [ 0 0 0 0 ]
    gap> Syndrome( C, "000000001100111" );
    [ 1 1 1 1 ]
    gap> Syndrome( C, "000000000000001" );
    [ 1 1 1 1 ]    # the same syndrome: both codewords are in the same
                   # coset of C |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{SyndromeTable}

'SyndromeTable( <C> )'

'SyndromeTable' returns a *syndrome table* of a linear code <C>,
consisting of two columns. The first column consists of the error vectors
that correspond to the syndrome vectors in the second column. These
vectors both are of the codeword type. After calculating the syndrome of
a word <c> with 'Syndrome' (see "Syndrome"), the error vector needed to
correct <c> can be found in the syndrome table. Subtracting this vector
from <c> yields an element of <C>.  The syndrome table must be sorted
according to the syndrome vectors.

|    gap> H := HammingCode(2);
    a linear [3,1,3] Hamming (2,2) rcode over GF(2)
    gap> SyndromeTable(H);
    [ [ [ 0 0 0 ], [ 0 0 ] ], [ [ 1 0 0 ], [ 0 1 ] ],
      [ [ 0 1 0 ], [ 1 0 ] ], [ [ 0 0 1 ], [ 1 1 ] ] ]
    gap> c := Codeword("101");
    [ 1 0 1 ]
    gap> c in H;
    false          # c is not an element of H
    gap> Syndrome(H,c);
    [ 1 0 ]        # according to the syndrome table,
                   # the error vector [ 0 1 0 ] belongs to this syndrome
    gap> c - Codeword("010") in H;
    true           # so the corrected codeword is
                   # [ 1 0 1 ] - [ 0 1 0 ] = [ 1 1 1 ],
                   # this is an element of H    |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{StandardArray}

'StandardArray( <C> )'

'StandardArray' returns the standard array of a code <C>. This is a
matrix with elements of the codeword type. It has $q^r$ rows and $q^k$
columns, where $q$ is the size of the base field of <C>, $r$ is the
redundancy of <C>, and $k$ is the dimension of <C>. The first row
contains all the elements of <C>. Each other row contains words that do
not belong to the code, with in the first column their syndrome vector
(see "Syndrome").

A non-linear code does not have a standard array. 'StandardArray' then
returns an error.

Note that calculating a standard array can be very time- and memory-
consuming.

|    gap> StandardArray(RepetitionCode(3,GF(3)));
    [ [ [ 0 0 0 ], [ 1 1 1 ], [ 2 2 2 ] ],
      [ [ 0 0 1 ], [ 1 1 2 ], [ 2 2 0 ] ],
      [ [ 0 0 2 ], [ 1 1 0 ], [ 2 2 1 ] ],
      [ [ 0 1 0 ], [ 1 2 1 ], [ 2 0 2 ] ],
      [ [ 0 2 0 ], [ 1 0 1 ], [ 2 1 2 ] ],
      [ [ 1 0 0 ], [ 2 1 1 ], [ 0 2 2 ] ],
      [ [ 2 0 0 ], [ 0 1 1 ], [ 1 2 2 ] ],
      [ [ 0 1 2 ], [ 1 2 0 ], [ 2 0 1 ] ],
      [ [ 0 2 1 ], [ 1 0 2 ], [ 2 1 0 ] ] ]   |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Display}

'Display( <C> )'

'Display' prints the method of construction of code <C> and, if <C> is
cyclic, its generator polynomial, or generator matrix if <C> is linear
and not cyclic.

|    gap> Display( RepetitionCode( 6, GF(3) ) );
            Construction:
    a cyclic [6,1,6] repetition code over GF(3)
            Generator polynomial:
    x^5 + x^4 + x^3 + x^2 + x + 1
    gap> C1 := ExtendedCode( HammingCode(2) );;
    gap> C2 := PuncturedCode( ReedMullerCode( 3, 2 ) );;
    gap> Display( StandardFormCode( UUVCode( C1, C2 ) ) );
            Construction:
    a linear [11,8,1] standard form, permuted with (2,11,8,5)(3,9,6)(4,10,7) \
    of
    a linear [11,8,1] U!U+V construction code of
    U: a linear [4,1,4] extended code of
       a cyclic [3,1,3] Hamming (2,2) code over GF(2)
    V: a linear [7,7,1] punctured in coordinate 8 of
       a cyclic [8,7,2] Reed-Muller (3,2) code over GF(2)
            Generator matrix:
    [ 1 0 0 0 0 0 0 0 1 1 1 ]
    [ 0 1 0 0 0 0 0 0 0 0 0 ]
    [ 0 0 1 0 0 0 0 0 0 0 0 ]
    [ 0 0 0 1 0 0 0 0 0 0 0 ]
    [ 0 0 0 0 1 0 0 0 0 0 0 ]
    [ 0 0 0 0 0 1 0 0 0 0 0 ]
    [ 0 0 0 0 0 0 1 0 0 0 0 ]
    [ 0 0 0 0 0 0 0 1 0 0 0 ] |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{CodewordNr}

'CodewordNr( <C>, <list> )'

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

So 'CodewordNr(<C>, <i>)' is equal to 'Elements(<C>)[<i>]'.  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> R := ReedSolomonCode(2,2);
    a cyclic [2,1,2] Reed-Solomon code over GF(3)
    gap> Elements(R);
    [ 0, x + 1, 2x + 2 ]
    gap> CodewordNr(R, [1,3]);
    [ 0, 2x + 2 ]
    gap> C := HadamardCode( 16 );
    a (16,32,8) Hadamard code of order 16 over GF(2)
    gap> Elements(C)[17] = CodewordNr( C, 17 );
    true                      |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% implementation of codes

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Code Records}

Like other {\GAP} structures, codes are represented by records that
contain important information about them. Creating such a code record is
done by the code generating functions described in "Generating
Unrestricted Codes", "Generating Linear Codes" and "Generating Cyclic
Codes". It is possible to create one by hand, though this is not
recommended.

Once a code record is created you may add record components to it but
it is not advisable to alter information already present, because
that may make the code record inconsistent.

Code records must always contain the components 'isCode', 'isDomain',
'operations' and one of the identification components 'elements',
'generatorMat', 'checkMat', 'generatorPol', 'checkPol'. The contents of
all components of a code $C$ are described below.

The following two components are the so-called *category components* used
to identify the category this domain belongs to.

'isDomain': \\
        is always 'true' as a code is a domain.

'isCode': \\
        is always 'true' as a code is a code is a code...

The following components determine a code domain. These are the so-called
*identification components*.

'elements': \\
        a list of elements of the code of type codeword. The field must
        be present for non-linear codes.

'generatorMat' and 'checkMat': \\
        a matrix of full rank over a finite field. Neither can exist for
        non-linear codes. Either one or both must be present for linear
        codes.

'generatorPol' and 'checkPol': \\
        a polynomial with coefficients in a finite field. Neither can
        exist for non-cyclic codes. Either one or both must be present
        for cyclic codes.

The following components contain *basic information* about the code.

'name': \\
        contains a short description of the code. See "Print" and
        "String".

'history': \\
        is a list of strings, containing the history of the code. The
        current name of the code is excluded in the list, so that if
        the minimum distance is calculated, it can be included in the
        history.  Each time the code is altered by a manipulating
        function, one or more strings are added to this list.
        See "Display".

'baseField': \\
        the finite field of the codewords of $C$. See "Field".

'wordLength': \\
        is an integer specifying the word length of each codeword of $C$.
        See "WordLength".

'size': \\
        is an integer specifying the size of $C$, being the number of
        codewords that $C$ has. See "Size".

The following components contain *knowledge* about the code $C$.

'dimension': \\
        is an integer specifying the dimension of $C$. The dimension is
        equal to the number of rows of the generator matrix. The field is
        invalid for unrestricted codes. See "Dimension".

'redundancy': \\
        is an integer specifying the redundancy of $C$. The redundancy is
        equal to the number of rows of the parity check matrix. The field
        is invalid for unrestricted codes. See "Redundancy".

'lowerBoundMinimumDistance' and 'upperBoundMinimumDistance': \\
        contains a lower and upper bound on the minimum distance of the
        code.  The exact minimum distance is known if the two values are
        equal. See "MinimumDistance".

'upperBoundOptimalMinimumDistance': \\
        contains an upper bound for the minimum distance of an optimal
        code with the same parameters.

'minimumWeightOfGenerator': \\
        contains the minimum weight of the words in the generator matrix
        (if the code is linear) or in the generator polynomial (if the
        code is cyclic). The field is invalid for unrestricted codes.

'designedDistance': \\
        is an integer specifying the designed distance of a BCH code.
        See "BCHCode".

'weightDistribution': \\
        is a list of integers containing the weight distribution of $C$.
        See "WeightDistribution".

'innerDistribution': \\
        is a list of integers containing the inner distribution of $C$.
        This component may only be present if $C$ is an unrestricted
        code.  See "InnerDistribution".

'outerDistribution': \\
        is a matrix containing the outer distribution, in which the first
        element of each row is an element of type codeword, and the
        second a list of integers. See "OuterDistribution".

'syndromeTable': \\
        is a matrix containing the syndrome table, in which the first
        element of each row consists of two elements of type codeword.
        This component is invalid for unrestricted codes.
        See "SyndromeTable".

'coveringRadius': \\
        is an integer specifying the covering radius.
        See "CoveringRadius".

The following components are 'true' if the code $C$ has the property,
'false' if not, and are not present if it is unknown whether the code has
the property or not.

'isLinearCode': \\
        is 'true' if the code is linear. See "IsLinearCode".

'isCyclicCode': \\
        is 'true' if the code is cyclic. See "IsCyclicCode".

'isPerfectCode': \\
        is 'true' if $C$ is a perfect code. See "IsPerfectCode".

'isSelfDualCode': \\
        is 'true' if $C$ is equal to its dual code. See "IsSelfDualCode".

The component 'specialDecoder' contains a function that implements a for
$C$ specific algorithm for decoding. See "Decode".

The component 'operations' contains  the *operations record* (see 'Domain
Records' and 'Dispatchers').

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% bounds for codes

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Bounds on codes}

These sections describe the functions that calculate estimates for upper
bounds on the size and minimum distance of codes. Several algorithms are
known to compute a largest number of words a code can have with given
length and minimum distance. It is important however to understand that
in some cases the true upper bound is unknown. A code which has a size
equal to the calculated upper bound may not have been found.  However,
codes that have a larger size do not exist.

A second way to obtain bounds is a table. In {\GUAVA}, an extensive table
is implemented for linear codes over GF(2), GF(3) and GF(4). It contains
bounds on the minimum distance for given word length and dimension.  For
binary codes, it contains entries for word length less than or equal to
257. For codes over $GF(3)$ and $GF(4)$, it contains entries for word
length less than or equal to 130.

The first sections describe functions that compute specific upper bounds
on the code size (see "UpperBoundSingleton", "UpperBoundHamming",
"UpperBoundJohnson", "UpperBoundPlotkin", "UpperBoundElias" and
"UpperBoundGriesmer").

The next section describes a function that computes {\GUAVA}\'s best
upper bound on the code size (see "UpperBound").

The next sections describe two functions that compute the difference
between {\GUAVA}\'s best upper bound and the actual size of a code (see
"OptimalityCode" and "OptimalityLinearCode").

The next sections describe two function that compute a lower and upper
bound on the minimum distance of a code (see "LowerBoundMinimumDistance"
and "UpperBoundMinimumDistance").

The last section describes a function that returns a lower and upper
bound on the minimum distance with given parameters and a description how
the bounds were obtained (see "BoundsMinimumDistance").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{UpperBoundSingleton}
\index{Bounds!Singleton}

'UpperBoundSingleton( <n>, <d>, <q> )'

'UpperBoundSingleton' returns the Singleton bound for a code of length
<n>, minimum distance <d> over a field of size <q>. This bound is based
on the shortening of codes. By shortening an $(n, M, d)$ code $d-1$
times, an $(n-d+1,M,1)$ code results, with $M \leq q^{n-d+1}$ (see
"ShortenedCode"). Thus $$M \leq <q>^{<n>-<d>+1}$$

Codes that meet this bound are called *maximum distance separable* (see
"IsMDSCode").

|    gap> UpperBoundSingleton(4, 3, 5);
    25
    gap> C := ReedSolomonCode(4,3);; Size(C);
    25
    gap> IsMDSCode(C);
    true |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{UpperBoundHamming}
\index{Bounds!Hamming}
\index{Bounds!Sphere packing bound}

'UpperBoundHamming( <n>, <d>, <q> )'

The Hamming bound (also known as *sphere packing bound*) returns an upper
bound on the size of a code of length <n>, minimum distance <d>, over a
field of size <q>. The Hamming bound is obtained by dividing the contents
of the entire space $GF(<q>) ^<n>$ by the contents of a ball with radius
$\lfloor(<d>-1) / 2\rfloor$.  As all these balls are disjoint, they can
never contain more than the whole vector space.  $$M \leq {<q>^<n> \over
V(<n>,e)}$$ where $M$ is the maxmimum number of codewords and $V(<n>,e)$
is equal to the contents of a ball of radius $e$ (see
"SphereContent"). This bound is useful for small values of <d>.  Codes
for which equality holds are called *perfect* (see "IsPerfectCode").

|    gap> UpperBoundHamming( 15, 3, 2 );
    2048
    gap> C := HammingCode( 4, GF(2) );
    A perfect linear [15,11,3] code over GF(2)
    gap> Size( C );
    2048 |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{UpperBoundJohnson}
\index{Bounds!Johnson}

'UpperBoundJohnson( <n>, <d> )'

The Johnson bound is an improved version of the Hamming bound (see
"UpperBoundHamming"). In addition to the Hamming bound, it takes into
account the elements of the space outside the balls of radius $e$ around
the elements of the code. The Johnson bound only works for binary codes.

|    gap> UpperBoundJohnson( 13, 5 );
    77
    gap> UpperBoundHamming( 13, 5, 2);
    89   # in this case the Johnson bound is better |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{UpperBoundPlotkin}
\index{Bounds!Plotkin}

'UpperBoundPlotkin( <n>, <d>, <q> )'

The function 'UpperBoundPlotkin' calculates the sum of the distances of
all ordered pairs of different codewords. It is based on the fact that
the minimum distance is at most equal to the average distance. It is a
good bound if the weights of the codewords do not differ much. It results
in\: $$M \leq {<d> \over {<d>-(1-1/<q>)<n>}}$$ $M$ is the maximum number
of codewords. In this case, <d> must be larger than $(1-1/<q>)<n>$, but
by shortening the code, the case $<d> \< (1-1/<q>)<n>$ is covered.

|    gap> UpperBoundPlotkin( 15, 7, 2 );
    32
    gap> C := BCHCode( 15, 7, GF(2) );
    A cyclic [15,5,7] code over GF(2)
    gap> Size(C);
    32
    gap> WeightDistribution(C);
    [ 1, 0, 0, 0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0, 1 ]  |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{UpperBoundElias}
\index{Bounds!Elias}

'UpperBoundElias( <n>, <d>, <q> )'

The Elias bound is an improvement of the Plotkin bound (see
"UpperBoundPlotkin") for large codes. Subcodes are used to decrease the
size of the code, in this case the subcode of all codewords within a
certain ball. This bound is useful for large codes with relatively small
minimum distances.

|    gap> UpperBoundPlotkin( 16, 3, 2 );
    12288
    gap> UpperBoundElias( 16, 3, 2 );
    10280 |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{UpperBoundGriesmer}
\index{Bounds!Griesmer}

'UpperBoundGriesmer( <n>, <d>, <q> )'

The Griesmer bound is valid only for linear codes. It is obtained by
counting the number of equal symbols in each row of the generator matrix
of the code. By omitting the coordinates in which all rows have a zero, a
smaller code results.  The Griesmer bound is obtained by repeating this
proces until a trivial code is left in the end.

|    gap> UpperBoundGriesmer( 13, 5, 2 );
    64
    gap> UpperBoundGriesmer( 18, 9, 2 );
    8        # the maximum number of words for a linear code is 8
    gap> Size( PuncturedCode( HadamardCode( 20, 1 ) ) );
    20       # this non-linear code has 20 elements |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{UpperBound}
\index{Bounds!UpperBound}

'UpperBound( <n>, <d>, <q> )'

'UpperBound' returns the best known upper bound $A(<n>,<d>)$ for the size
of a code of length <n>, minimum distance <d> over a field of size <q>.
The function 'UpperBound' first checks for trivial cases (like $<d>=1$ or
$<n>=<d>$) and if the value is in the built-in table. Then it calculates
the minimum value of the upper bound using the methods of Singleton (see
"UpperBoundSingleton"), Hamming (see "UpperBoundHamming"), Johnson (see
"UpperBoundJohnson"), Plotkin (see "UpperBoundPlotkin") and Elias (see
"UpperBoundElias").  If the code is binary, $A(<n>, 2\*l-1) = A(<n>+1,
2\*l)$, so the 'UpperBound' takes the minimum of the values obtained from
all methods for the parameters $(<n>, 2\*l-1)$ and $(<n>+1, 2\*l)$.

|    gap> UpperBound( 10, 3, 2 );
    79    # From the built-in table
    gap> UpperBound( 25, 9, 8 );
    1211778792827540 |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{OptimalityCode}

'OptimalityCode( <C> )'

'OptimalityCode' returns the difference between the best known upper
bound found by \mbox{{\GUAVA}} for the number of codewords of <C> (see
"UpperBound") and the actual size of <C>. This function is meant as an
indication for the optimality of a code. The result for *perfect* codes
(see "UpperBoundHamming") and *MDS* codes (see "UpperBoundSingleton") is
$0$.

|    gap> C1 := NordstromRobinsonCode();
    A non-linear (16,256,6) code over GF(2)
    gap> OptimalityCode( C1 );
    0
    gap> C2 := BCHCode( 17, 3, GF(2) );
    A cyclic [17,9,d] code over GF(2), d in [3..5]
    gap> OptimalityCode( C2 );
    168    # It is possible that a code with 168 more words exists |


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{OptimalityLinearCode}

'OptimalityLinearCode( <C> )'

'OptimalityLinearCode' returns the difference between the best known
upper bound found by {\GUAVA} for the number of codewords of a *linear*
code <C> and the actual size of <C>. This function is meant as an
indication for the optimality of a linear code.

|    gap> C1 := BCHCode( 17, 3 );
    A cyclic [17,9,d] code over GF(2), d in [3..5]
    gap> OptimalityLinearCode( C1 );
    0
    gap> C2 := BCHCode( 15, 4, 3, GF(2) );
    A cyclic [15,9,3] code over GF(2)
    gap> OptimalityLinearCode( C2 );
    1536
    gap> C3 := HammingCode( 4 );
    A perfect linear [15,11,3] code over GF(2)
    gap> OptimalityLinearCode( C3 );
    0    # So C3 is \'better\'\ than C2
|

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{LowerBoundMinimumDistance}

'LowerBoundMinimumDistance( <C> )'

In this form, 'LowerBoundMinimumDistance' returns a lower bound for the
minimum distance of code <C>.

|    gap> C := BCHCode( 45, 7 );
    A cyclic [45,23,d] code over GF(2) with d in [7..9]
    gap> LowerBoundMinimumDistance( C );
    7     # designed distance is lower bound for minimum distance |

'LowerBoundMinimumDistance( <n>, <k>, <F> )'

In this form, 'LowerBoundMinimumDistance' returns a lower bound for the
minimum distance of the best known linear code. It uses the mechanism
explained in section "BoundsMinimumDistance".

|    gap> LowerBoundMinimumDistance( 45, 23, GF(2) );
    10  |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{UpperBoundMinimumDistance}

'UpperBoundMinimumDistance( <C> )'

In this form, 'UpperBoundMinimumDistance' returns an upper bound for the
minimum distance of code <C>. For unrestricted codes, it just returns the
word length. For linear codes, it takes the minimum of the possibly known
value from the method of construction, the weight of the generators, and
the value from the table (see "BoundsMinimumDistance").

|    gap> C := BCHCode( 45, 7 );
    A cyclic [45,23,d] code over GF(2) with d in [7..9]
    gap> UpperBoundMinimumDistance( C );
    9  |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{BoundsMinimumDistance}

'BoundsMinimumDistance( <n>, <k>, <F> )'

The function 'BoundsMinimumDistance' calculates a lower and upper bound
for the minimum distance of an optimal linear code with word length <n>,
dimension <k> over field <F>. The function returns a record with the two
bounds and an explenation for each bound. The function 'Display' can be
used to show the explanations.

The values for the lower and upper bound are obtained from a
table. {\GUAVA} has tables containing lower and upper bounds for $q=2\ (n
\leq 257),\ 3$ and $4\ (n \leq 130)$. These tables were derived from the
table of Brouwer \& Verhoeff. For codes over other fields and for larger
word lengths, trivial bounds are used.

The resulting record can be used in the function 'BestKnownLinearCode'
(see "BestKnownLinearCode") to construct a code with minimum distance
equal to the lower bound.
%R~ (in rare cases, it can be larger).

|    gap> bounds := BoundsMinimumDistance( 7, 3 );; Display( bounds );
    Lb(7,3)=4, by shortening of:
    Lb(8,4)=4, u ! u+v Construction of U and V:
    V: Lb(4,1)=4, Repetition code
    U: Lb(4,3)=2, Dual of the repetition code
    --------------------------------------------------------------------
    Ub(7,3)=4, Griesmer bound
    --------------------------------------------------------------------
    # The lower bound is equal to the upper bound, so a code with
    # these parameters is optimal.
    gap> C := BestKnownLinearCode( bounds );; Display( C );
    A linear [7,3,4] code over GF(2)
            Construction:
    [7,3,4] is shortened in coordinate 1 of
    [8,4,4] is u ! u + v Construction of C1 and C2
    C1: [4,3,2] is dual code of
        [4,1,4] is repetition code
    C2: [4,1,4] is repetition code
            Generator matrix:
    [ 1 0 1 0 1 0 1 ]
    [ 0 1 1 0 0 1 1 ]
    [ 0 0 0 1 1 1 1 ]   |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% matrices

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Matrices for Codes}

This chapter explains functions that work with special matrices {\GUAVA}
needs for several codes.


The first sections describe some matrix generating functions (see
"KrawtchoukMat", "GrayMat", "SylvesterMat", "HadamardMat" and "MOLS").

The next sections describe two functions about a standard form of
matrices (see "PutStandardForm" and "IsInStandardForm").

The next sections describe functions that return a matrix after a
manipulation (see "PermutedCols", "VerticalConversionFieldMat" and
"HorizontalConversionFieldMat").

The last sections describe functions that do some tests on matrices
(see "IsLatinSquare" and "AreMOLS").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% construction of matrices

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{KrawtchoukMat}

'KrawtchoukMat( <n> , <q> )'

'KrawtchoukMat' returns the $<n>+1$ by $<n>+1$ matrix $K=(k_{ij})$
defined by $k_{ij}=K_i(j)$ for $i,j=0,...,n$. $K_i(j)$ is the Krawtchouk
number (see "Krawtchouk"). <n> must be a positive integer and <q> a prime
power.  The Krawtchouk matrix is used in the *MacWilliams identities*,
defining the relation between the weight distribution of a code of length
<n> over a field of size <q>, and its dual code.  Each call to
'KrawtchoukMat' returns a new matrix, so it is safe to modify the result.

|    gap> PrintArray( KrawtchoukMat( 3, 2 ) );
    [ [   1,   1,   1,   1 ],
      [   3,   1,  -1,  -3 ],
      [   3,  -1,  -1,   3 ],
      [   1,  -1,   1,  -1 ] ]
    gap> C := HammingCode( 3 );; a := WeightDistribution( C );
    [ 1, 0, 0, 7, 7, 0, 0, 1 ]
    gap> n := WordLength( C );; q := Size( Field( C ) );;
    gap> k := Dimension( C );;
    gap> q^( -k ) * KrawtchoukMat( n, q ) * a;
    [ 1, 0, 0, 0, 7, 0, 0, 0 ]
    gap> WeightDistribution( DualCode( C ) );
    [ 1, 0, 0, 0, 7, 0, 0, 0 ] |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{GrayMat}

'GrayMat( <n>, <F> )'

'GrayMat' returns a list of all different vectors (see 'Vectors') of
length <n> over the field <F>, using Gray ordening. <n> must be a
positive integer.  This order has the property that subsequent vectors
differ in exactly one coordinate. The first vector is always the null
vector. Each call to 'GrayMat' returns a new matrix, so it is safe to
modify the result.

|    gap> GrayMat(3);
    [ [ 0*Z(2), 0*Z(2), 0*Z(2) ], [ 0*Z(2), 0*Z(2), Z(2)^0 ],
      [ 0*Z(2), Z(2)^0, Z(2)^0 ], [ 0*Z(2), Z(2)^0, 0*Z(2) ],
      [ Z(2)^0, Z(2)^0, 0*Z(2) ], [ Z(2)^0, Z(2)^0, Z(2)^0 ],
      [ Z(2)^0, 0*Z(2), Z(2)^0 ], [ Z(2)^0, 0*Z(2), 0*Z(2) ] ]
    gap> G := GrayMat( 4, GF(4) );; Length(G);
    256          # the length of a GrayMat is always $q^n$
    gap> G[101] - G[100];
    [ 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2) ]  |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{SylvesterMat}

'SylvesterMat( <n> )'

'SylvesterMat' returns the <n> by <n> Sylvester matrix of order <n>. This
is a special case of the Hadamard matrices (see "HadamardMat"). For this
construction, <n> must be a power of $2$. Each call to 'SylvesterMat'
returns a new matrix, so it is safe to modify the result.

|    gap>  PrintArray(SylvesterMat(2));
    [ [   1,   1 ],
      [   1,  -1 ] ]
    gap> PrintArray( SylvesterMat(4) );
    [ [   1,   1,   1,   1 ],
      [   1,  -1,   1,  -1 ],
      [   1,   1,  -1,  -1 ],
      [   1,  -1,  -1,   1 ] ]  |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{HadamardMat}

'HadamardMat( <n> )'

'HadamardMat' returns a Hadamard matrix of order <n>. This is an <n> by
<n> matrix with the property that the matrix multiplied by its transpose
returns <n> times the identity matrix. This is only possible for $<n>=1,
<n>=2$ or in cases where <n> is a multiple of $4$. If the matrix does not
exist or is not known, 'HadamardMat' returns an error. A large number of
construction methods is known to create these matrices for different
orders. 'HadamardMat' makes use of two construction methods (among which
the Sylvester construction (see "SylvesterMat")). These methods cover
most of the possible Hadamard matrices, although some special algorithms
have not been implemented yet. The following orders less than 100 do not
have an implementation for a Hadamard matrix in {\GUAVA}\:$\ 28, 36, 52,
76, 92.$

|    gap> C := HadamardMat(8);; PrintArray(C);
    [ [   1,   1,   1,   1,   1,   1,   1,   1 ],
      [   1,  -1,   1,  -1,   1,  -1,   1,  -1 ],
      [   1,   1,  -1,  -1,   1,   1,  -1,  -1 ],
      [   1,  -1,  -1,   1,   1,  -1,  -1,   1 ],
      [   1,   1,   1,   1,  -1,  -1,  -1,  -1 ],
      [   1,  -1,   1,  -1,  -1,   1,  -1,   1 ],
      [   1,   1,  -1,  -1,  -1,  -1,   1,   1 ],
      [   1,  -1,  -1,   1,  -1,   1,   1,  -1 ] ]
    gap> C * TransposedMat(C) = 8 * IdentityMat( 8, 8 );
    true  |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{MOLS}

'MOLS( <q> )'\\
'MOLS( <q>, <n> )'

'MOLS' returns a list of <n> *Mutually Orthogonal Latin Squares*
(*MOLS*). A *Latin square* of order <q> is a <q> by <q> matrix whose
entries are from a set $F_{<q>}$ of <q> distinct symbols ({\GUAVA} uses
the integers from 0 to <q>) such that each row and each column of the
matrix contains each symbol exactly once.

A set of Latin squares is a set of MOLS if and only if for each pair of
Latin squares in this set, every ordered pair of elements that are in the
same position in these matrices occurs exactly once.

<n> must be less than <q>. If <n> is omitted, two MOLS are returned. If
<q> is not a prime power, at most 2 MOLS can be created. For all values
of <q> with $<q> > 2$ and $<q> \neq 6$, a list of MOLS can be
constructed. {\GUAVA} however does not yet construct MOLS for $<q>$ mod
$4 = 2$.  If it is not possible to construct <n> MOLS, the function
returns 'false'.

MOLS are used to create <q>-ary codes (see "MOLSCode").

|    gap> M := MOLS( 4, 3 );;PrintArray( M[1] );
    [ [  0,  1,  2,  3 ],
      [  1,  0,  3,  2 ],
      [  2,  3,  0,  1 ],
      [  3,  2,  1,  0 ] ]
    gap> PrintArray( M[2] );
    [ [  0,  2,  3,  1 ],
      [  1,  3,  2,  0 ],
      [  2,  0,  1,  3 ],
      [  3,  1,  0,  2 ] ]
    gap> PrintArray( M[3] );
    [ [  0,  3,  1,  2 ],
      [  1,  2,  0,  3 ],
      [  2,  1,  3,  0 ],
      [  3,  0,  2,  1 ] ]
    gap> MOLS( 12, 3 );
    false  |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% function that interpret a matrix as a system of linear equations

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{PutStandardForm}

'PutStandardForm( <M> )'\\
'PutStandardForm( <M>, <idleft> )'

'PutStandardForm' puts a matrix <M> in standard form, and returns the
permutation needed to do so. <idleft> is a boolean that sets the position
of the identity matrix in <M>. If <idleft> is set to 'true', the identity
matrix is put in the left side of <M>. Otherwise, it is put at the right
side. The default for <idleft> is 'true'.

The function 'BaseMat' also returns a similar standard form, but does not
apply column permutations. The rows of the matrix still span the same
vector space after 'BaseMat', but after calling 'PutStandardForm', this
is not necessarily true.

|   gap> M := Z(2)*[[1,0,0,1],[0,0,1,1]];; PrintArray(M);
   [ [  Z(2)^0,  0*Z(2),  0*Z(2),  Z(2)^0 ],
     [  0*Z(2),  0*Z(2),  Z(2)^0,  Z(2)^0 ] ]
   gap> PutStandardForm(M);                   # identity at the left side
   (2,3)
   gap> PrintArray(M);
   [ [  Z(2)^0,  0*Z(2),  0*Z(2),  Z(2)^0 ],
     [  0*Z(2),  Z(2)^0,  0*Z(2),  Z(2)^0 ] ]
   gap> PutStandardForm(M, false);            # identity at the right side
   (1,4,3)
   gap> PrintArray(M);
   [ [  0*Z(2),  Z(2)^0,  Z(2)^0,  0*Z(2) ],
     [  0*Z(2),  Z(2)^0,  0*Z(2),  Z(2)^0 ] ]  |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsInStandardForm}

'IsInStandardForm( <M> )'\\
'IsInStandardForm( <M>, <idleft> )'

'IsInStandardForm' determines if <M> is in standard form. <idleft> is a
boolean that indicates the position of the identity matrix in <M>. If
<idleft> is 'true', 'IsInStandardForm' checks if the identity matrix is
at the left side of <M>, otherwise if it is at the right side. The
default for <idleft> is 'true'. The elements of <M> may be elements of
any field. To put a matrix in standard form, use 'PutStandardForm' (see
"PutStandardForm").

|    gap> IsInStandardForm(IdentityMat(7, GF(2)));
    true
    gap> IsInStandardForm([[1, 1, 0], [1, 0, 1]], false);
    true
    gap> IsInStandardForm([[1, 3, 2, 7]]);
    true
    gap> IsInStandardForm(HadamardMat(4));
    false   |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% more creations

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{PermutedCols}

'PermutedCols( <M>, <P> )'

'PermutedCols' returns a matrix <M> with a permutation <P> applied to
its columns.

|   gap> M := [[1,2,3,4],[1,2,3,4]];; PrintArray(M);
    [ [  1,  2,  3,  4 ],
      [  1,  2,  3,  4 ] ]
    gap> PrintArray(PermutedCols(M, (1,2,3)));
    [ [  3,  1,  2,  4 ],
      [  3,  1,  2,  4 ] ]  |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{VerticalConversionFieldMat}

'VerticalConversionFieldMat( <M>, <F> )'

'VerticalConversionFieldMat' returns the matrix <M> with its elements
converted from a field $<F>=GF(q^m)$, $q$ prime, to a field $GF(q)$. Each
element is replaced by its representation over the latter field, placed
vertically in the matrix.

If <M> is a $k$ by $n$ matrix, the result is a $k\*m$ by $n$ matrix,
since each element of $GF(q^m)$ can be represented in $GF(q)$ using $m$
elements.

|    gap> M := Z(9)*[[1,2],[2,1]];; PrintArray(M);
    [ [    Z(3^2),  Z(3^2)^5 ],
    [  Z(3^2)^5,    Z(3^2) ] ]
    gap> DefaultField( Flat(M) );
    GF(3^2)
    gap> VCFM := VerticalConversionFieldMat( M, GF(9) );; PrintArray(VCFM);
    [ [  0*Z(3),  0*Z(3) ],
      [  Z(3)^0,    Z(3) ],
      [  0*Z(3),  0*Z(3) ],
      [    Z(3),  Z(3)^0 ] ]
    gap> DefaultField( Flat(VCFM) );
    GF(3)  |

A similar function is 'HorizontalConversionFieldMat' (see
"HorizontalConversionFieldMat").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{HorizontalConversionFieldMat}

'HorizontalConversionFieldMat( <M>, <F> )'

'HorizontalConversionFieldMat' returns the matrix <M> with its elements
converted from a field $<F>=GF(q^m)$, $q$ prime, to a field $GF(q)$. Each
element is replaced by its representation over the latter field, placed
horizontally in the matrix.

If <M> is a $k$ by $n$ matrix, the result is a $k\*m$ by $n\*m$
matrix. The new word length of the resulting code is equal to $n\*m$,
because each element of $GF(q^m)$ can be represented in $GF(q)$ using $m$
elements. The new dimension is equal to $k\*m$ because the new matrix
should be a basis for the same number of vectors as the old one.

'ConversionFieldCode' uses horizontal conversion to convert a code (see
"ConversionFieldCode").

|    gap> M := Z(9)*[[1,2],[2,1]];; PrintArray(M);
    [ [    Z(3^2),  Z(3^2)^5 ],
      [  Z(3^2)^5,    Z(3^2) ] ]
    gap> DefaultField( Flat(M) );
    GF(3^2)
    gap> HCFM := HorizontalConversionFieldMat(M, GF(9));; PrintArray(HCFM);
    [ [  0*Z(3),  Z(3)^0,  0*Z(3),    Z(3) ],
      [  Z(3)^0,  Z(3)^0,    Z(3),    Z(3) ],
      [  0*Z(3),    Z(3),  0*Z(3),  Z(3)^0 ],
      [    Z(3),    Z(3),  Z(3)^0,  Z(3)^0 ] ]
    gap> DefaultField( Flat(HCFM) );
    GF(3)    |

A similar function is 'VerticalConversionFieldMat' (see
"VerticalConversionFieldMat").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% property tests for matrices

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsLatinSquare}

'IsLatinSquare( <M> )'

'IsLatinSquare' determines if a matrix <M> is a latin square. For a latin
square of size $n$ by $n$, each row and each column contains all the
integers $1..n$ exactly once.

|    gap> IsLatinSquare([[1,2],[2,1]]);
    true
    gap> IsLatinSquare([[1,2,3],[2,3,1],[1,3,2]]);
    false  |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{AreMOLS}

'AreMOLS( <L> )'

'AreMOLS' determines if <L> is a list of mutually orthogonal latin
squares (MOLS). For each pair of latin squares in this list, the function
checks if each ordered pair of elements that are in the same position in
these matrices occurs exactly once. The function 'MOLS' creates MOLS (see
"MOLS").

|    gap> M := MOLS(4,2);
    [ [ [ 0, 1, 2, 3 ], [ 1, 0, 3, 2 ], [ 2, 3, 0, 1 ], [ 3, 2, 1, 0 ] ],
      [ [ 0, 2, 3, 1 ], [ 1, 3, 2, 0 ], [ 2, 0, 1, 3 ], [ 3, 1, 0, 2 ] ] ]
    gap> AreMOLS(M);
    true   |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% miscellaneous functions

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Miscellaneous functions}

This chapter describes several functions {\GUAVA} uses for constructing
codes or performing calculations with codes.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{SphereContent}

'SphereContent( <n>, <t>, <F> )'  

'SphereContent' returns the content of a ball of radius <t> around an
arbitrary element of the vectorspace $<F>^<n>$. This is the cardinality
of the set of all elements of $<F>^<n>$ that are at distance (see
"Distance") less than or equal to <t> from an element of $<F>^<n>$.

In the context of codes, the function is used to determine if a code is
perfect. A code is perfect if spheres of radius $t$ around all codewords
contain exactly the whole vectorspace, where $t$ is the number of errors
the code can correct.

|    gap> SphereContent( 15, 0, GF(2) );
    1    # Only one word with distance 0, which is the word itself
    gap> SphereContent( 11, 3, GF(4) )
    4984
    gap> C := HammingCode(5);
    A perfect linear [31,26,3] code over GF(2)
    #the minimum distance is 3, so the code can correct one error
    gap> ( SphereContent( 31, 1, GF(2) ) * Size(C) ) = 2 ^ 31;
    true |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Krawtchouk}

'Krawtchouk( <k>, <i>, <n>, <q> )'

'Krawtchouk' returns the Krawtchouk number $K_{<k>}(<i>)$. <q> must be a
primepower, <n> must be a positive integer, <k> must be a non-negative
integer less then or equal to <n> and <i> can be any integer. (See
"KrawtchoukMat").

|    gap> Krawtchouk( 2, 0, 3, 2);
    3 |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{PrimitiveUnityRoot}

'PrimitiveUnityRoot( <F>, <n> )'

'PrimitiveUnityRoot' returns a *primitive n\'th root of unity* in an
extension field of <F>. This is a finite field element <a> with the
property $<a>^<n>=1\ $mod $ n$, and <n> is the smallest integer such that
this equality holds.

|    gap> PrimitiveUnityRoot( GF(2), 15 );
    Z(2^4)
    gap> last^15;
    Z(2)^0
    gap> PrimitiveUnityRoot( GF(8), 21 );
    Z(2^6)^3 |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{ReciprocalPolynomial}

'ReciprocalPolynomial( <P> )'

'ReciprocalPolynomial' returns the *reciprocal* of polynomial <P>. This
is a polynomial with coefficients of <P> in the reverse order. So if
$<P>=a_0 + a_1 X + ... + a_{<n>} X^{<n>}$, the reciprocal polynomial is
$<P>$\'$=a_{<n>} + a_{<n>-1} X + ... + a_0 X^{<n>}$.

|    gap> P := Polynomial( GF(3), Z(3)^0 * [1,0,1,2] );
    Z(3)^0*(2*X(GF(3))^3 + X(GF(3))^2 + 1)
    gap> RecP := ReciprocalPolynomial( P );
    Z(3)^0*(X(GF(3))^3 + X(GF(3)) + 2)
    gap> ReciprocalPolynomial( RecP ) = P;
    true  |

'ReciprocalPolynomial( <P> , <n> )'

In this form, the number of coefficients of <P> is considered to be at
least <n> (possibly with zero coefficients at the highest
degrees). Therefore, the reciprocal polynomial $<P>$\'\ also has degree
at least <n>.

|    gap> P := Polynomial( GF(3), Z(3)^0 * [1,0,1,2] );
    Z(3)^0*(2*X(GF(3))^3 + X(GF(3))^2 + 1)
    gap> ReciprocalPolynomial( P, 6 );
    Z(3)^0*(X(GF(3))^6 + X(GF(3))^4 + 2*X(GF(3))^3) |
    
In this form, the degree of <P> is considered to be at least <n> (if not,
zero coefficients are added). Therefore, the reciprocal polynomial
$<P>$\'\ also has degree at least <n>.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{CyclotomicCosets}

'CyclotomicCosets( <q>, <n> )'

'CyclotomicCosets' returns the cyclotomic cosets of <q> modulo <n>. <q>
and <n> must be relatively prime. Each of the elements of the returned
list is a list of integers that belong to one cyclotomic coset. Each
coset contains all multiplications of the *coset representative* by <q>,
modulo <n>. The coset representative is the smallest integer that isn\'t
in the previous cosets.

|    gap> CyclotomicCosets( 2, 15 );
    [ [ 0 ], [ 1, 2, 4, 8 ], [ 3, 6, 12, 9 ], [ 5, 10 ],
      [ 7, 14, 13, 11 ] ]
    gap> CyclotomicCosets( 7, 6 );
    [ [ 0 ], [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ] ] |
    
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{WeightHistogram}

'WeightHistogram( <C> )'\\
'WeightHistogram( <C>, <h> )'

The function 'WeightHistogram' plots a histogram of weights in code
<C>. The maximum length of a column is <h>. Default value for <h> is
$1/3$ of the size of the screen. The number that appears at the top of
the histogram is the maximum value of the list of weights.

|    gap> H := HammingCode(2, GF(5));
    A perfect linear [6,4,3] code over GF(5)
    gap> WeightDistribution(H);
    [ 1, 0, 0, 80, 120, 264, 160 ]
    gap> WeightHistogram(H);
    264----------------
                   *
                   *
                   *
                   *
                   *  *
                *  *  *
             *  *  *  *
             *  *  *  *
    -------------------
    0  1  2  3  4  5  6  |
    
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%