%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%A  codegen.tex              GUAVA documentation                Reinald Baart
%A                                                       & Jasper Cramwinckel
%A                                                          & Erik Roijackers
%
%
%Y  Copyright (C)  1995,  Vakgroep Algemene Wiskunde,  T.U. Delft,  Nederland
%
\Chapter{Generating Codes}

In this chapter we describe functions for generating codes.

Section~"Generating Unrestricted Codes" describes function for generating
unrestricted codes.

Section~"Generating  Linear  Codes" describes function for generating linear
codes.

Finally,  Section~"Generating  Cyclic  Codes"  describes  functions   for
generating cyclic codes.

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

In this section we start with functions  that  creating  code  from  user
defined matrices or special matrices (see "ElementsCode", "HadamardCode",
"ConferenceCode!from  a  matrix"  and  "MOLSCode").   These   codes   are
unrestricted codes; they may later be discovered to be linear or cyclic.

The next functions generate  random  codes  (see  "RandomCode")  and  the
Nordstrom-Robinson code (see "NordstromRobinsonCode"), respectively.

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

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

If <L>  contains a codeword more than  once, it is  removed from the list
and a {\GAP} set is returned.

\beginexample
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)2 example code over GF(3)
gap> MinimumDistance( C );
4
gap> AsSSortedList( C );
[ [ 0 1 2 2 ], [ 1 0 1 1 ], [ 2 2 0 0 ] ]
\endexample

\>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 1s by 0s and the -1s by 1s).

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.

\beginexample
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)1 Hadamard code of order 4 over GF(2)
gap> HadamardCode( H4, 2 );
a (3,8,1)0 Hadamard code of order 4 over GF(2)
gap> HadamardCode( H4 );
a (4,8,2)1 Hadamard code of order 4 over GF(2) 
\endexample

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

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

\>ConferenceCode( <H> )!{from a matrix}

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

\beginexample
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)1..4 conference code over GF(2)
gap> IsLinearCode( C1 );
false 
\endexample

\>ConferenceCode( <n> )!{from an integer}

{\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.

\beginexample
gap> C2 := ConferenceCode( 5 );
a (5,12,2)1..4 conference code over GF(2)
gap> AsSSortedList( C2 );
[ [ 0 0 0 0 0 ], [ 0 0 1 1 1 ], [ 0 1 0 1 1 ], [ 0 1 1 0 1 ], [ 0 1 1 1 0 ], 
  [ 1 0 0 1 1 ], [ 1 0 1 0 1 ], [ 1 0 1 1 0 ], [ 1 1 0 0 1 ], [ 1 1 0 1 0 ], 
  [ 1 1 1 0 0 ], [ 1 1 1 1 1 ] ]
\endexample

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

\beginexample
gap> C1 := MOLSCode( 6, 5 );
a (6,25,5)3..4 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(LeftActingDomain(C1)), Size(LeftActingDomain(C1)) );
>       for el in VectorCodeword( AsSSortedList( 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)2 code generated by 2 MOLS of order 11 over GF(11) 
\endexample

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

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

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

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

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

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

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

\beginexample
gap> C := LexiCode( 4, 3, GF(5) );
a (4,17,3..4)2..4 lexicode over GF(5) 
\endexample

\>LexiCode( <B>, <d>, <F> )!{using a basis}

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

\beginexample
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]1..2 lexicode over GF(2) 
\endexample

Note that binary Lexicodes are always linear.

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

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

In this section we describe functions for constructing  linear  codes.  A
linear code always has a generator or check matrix.

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

The next functions we describe  generate  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 "AlternantCode", "GoppaCode!with list of field elements  parameter",
"GeneralizedSrivastavaCode" and "SrivastavaCode").

Finally, we describe a function for generating random linear  codes  (see
"RandomLinearCode").

\>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
"ref:BaseMat")  and results  in an equal  code. The  generator  matrix can be
retrieved with the function `GeneratorMat' (see "GeneratorMat").

\beginexample
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]1..2 code defined by generator matrix over GF(3)
gap> C2 := GeneratorMatCode( IdentityMat( 5, GF(2) ), GF(2) );
a linear [5,5,1]0 code defined by generator matrix over GF(2)
gap> GeneratorMatCode( List( AsSSortedList( NordstromRobinsonCode() ),
> x -> VectorCodeword( x ) ), GF( 2 ) );
a linear [16,11,1..4]2 code defined by generator matrix over GF(2)
# This is the smallest linear code that contains the N-R code 
\endexample

\>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 "ref:BaseMat")
and results in an equal code. The check matrix  can be retrieved with the
function `CheckMat' (see "CheckMat").

\beginexample
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]2..3 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 cyclic [5,0,5]5 code defined by check matrix over GF(2)
\endexample

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

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

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

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

\beginexample
gap> ReedMullerCode( 1, 3 );
a linear [8,4,4]2 Reed-Muller (1,3) code over GF(2) 
\endexample

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

\beginexample
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]3..4 alternant code over GF(8) 
\endexample

\>GoppaCode( <G>, <L> )!{with list of field elements parameter}

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

\beginexample
gap> x := Indeterminate( GF(2), "x" );; 
gap> G := x^2 + x + 1;; L := AsSSortedList( GF(8) );;
gap> C := GoppaCode( G, L );
a linear [8,2,5]3 Goppa code over GF(2) 
\endexample

\>GoppaCode( <G>, <n> )!{with integer parameter}

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

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

\>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$.

\beginexample
gap> a := Filtered( AsSSortedList( 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]3..4 generalized Srivastava code over GF(2) 
\endexample

\>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$.

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

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

\beginexample
gap> C := CordaroWagnerCode( 11 );
a linear [11,2,7]5 Cordaro-Wagner code over GF(2)
gap> AsSSortedList(C);                 
[ [ 0 0 0 0 0 0 0 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 ], [ 1 1 1 1 1 1 1 0 0 0 0 ] ]
\endexample

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

\beginexample
gap> C := RandomLinearCode( 15, 4, GF(3) );
a linear [15,4,1..6]6..10 random linear code over GF(3)
\endexample

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

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

\>BestKnownLinearCode( <rec> )!{of a record}

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.

\beginexample
gap> bounds := BoundsMinimumDistance( 20, 17, GF(4) );
rec( n := 20, k := 17, q := 4, 
  references := rec( HM := [ "%T this reference is unknown, for more info", 
          "%T contact A.E. Brouwer (aeb@cwi.nl)" ] ), 
  construction := [ <Operation "ShortenedCode">, 
      [ [ <Operation "HammingCode">, [ 3, 4 ] ], [ 1 ] ] ], lowerBound := 3, 
  lowerBoundExplanation := [ "Lb(20,17)=3, by shortening of:", 
      "Lb(21,18)=3, reference: HM" ], upperBound := 3, 
  upperBoundExplanation := 
    [ "Ub(20,17)=3, otherwise construction B would contradict:", 
      "Ub(3,1)=3, repetition code" ] )
gap> C := BestKnownLinearCode( bounds );
a linear [20,17,3]2 shortened code
gap> C = BestKnownLinearCode( 20, 17, GF(4) );
true 
\endexample

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

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

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

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

\beginexample
gap> C := ExtendedBinaryGolayCode();
a linear [24,12,8]4 extended binary Golay code over GF(2)
gap> P := PuncturedCode(C);
a linear [23,12,7]3 punctured code
gap> P = BinaryGolayCode();
true 
\endexample

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

\beginexample
gap> TernaryGolayCode();
a cyclic [11,6,5]2 ternary Golay code over GF(3)
gap> ExtendedTernaryGolayCode() = ExtendedCode(TernaryGolayCode());
true 
\endexample

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

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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$. A cyclic code is an ideal in
the ring  of polynomials  modulo $x^<n>  - 1$. The  polynomial $g(x)$  is
called the  *generator polynomial*  of  $C$. This   is the  unique  monic
polynomial  of least degree that generates  $C$. It is  a  divisor of the
polynomial $x^<n>-1$.

\index{check polynomial}
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 functions described generate  cyclic  codes  from  a  given
generator or check polynomial. All cyclic codes can be constructed  using
these functions.

Next are described the two cyclic Golay codes (see "BinaryGolayCode"  and
"TernaryGolayCode").

Then functions that generate cyclic codes from a prescribed set of  roots
of the generator polynomial are described, including the BCH  codes  (see
"RootsCode", "BCHCode", "ReedSolomonCode" and "QRCode").

Finally we describe the trivial codes (see "WholeSpaceCode",  "NullCode",
"RepetitionCode"), and `CyclicCodes' ("CyclicCodes").

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

`GeneratorPolCode' creates a cyclic code with a generator polynomial <g>,
word length <n>,  over <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 ideal
$(g)$. See "Generating Cyclic Codes".

\beginexample
gap> x:= Indeterminate( GF(2) );; P:= x^2+1;
Z(2)^0+x^2
gap> G := GeneratorPolCode(P, 7, GF(2));
a cyclic [7,6,1..2]1 code defined by generator polynomial over GF(2)
gap> GeneratorPol( G );
Z(2)^0+x
gap> G2 := GeneratorPolCode( x+1, 7, GF(2)); 
a cyclic [7,6,1..2]1 code defined by generator polynomial over GF(2)
gap> GeneratorPol( G2 );
Z(2)^0+x
\endexample

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

`CheckPolCode' creates  a cyclic code  with a  check polynomial <h>, word
length <n>, over <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  elements as the ideal $(h)$. See
"Generating Cyclic Codes".

\beginexample
gap>  x:= Indeterminate( GF(3) );; P:= x^2+2;
-Z(3)^0+x_1^2
gap> H := CheckPolCode(P, 7, GF(3));
a cyclic [7,1,7]4 code defined by check polynomial over GF(3)
gap> CheckPol(H);
-Z(3)^0+x_1
gap> Gcd(P, X(GF(3))^7-1);
-Z(3)^0+x_1
\endexample

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

\beginexample
gap> a := PrimitiveUnityRoot( 3, 14 );
Z(3^6)^52
gap> C1 := RootsCode( 14, [ a^0, a, a^3 ] );
a cyclic [14,7,3..6]3..7 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]3..5 code defined by roots over GF(2)
gap> C2 = BCHCode( 15, 5, GF(2) );
true 
\endexample

\>RootsCode( <n>, <list>, <F> )!{with field}

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.

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

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

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

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

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

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

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

\>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$.

\beginexample
gap> x:= Indeterminate( GF(2) );; G:= x^3+x^2+1;
Z(2)^0+x^2+x^3
gap> Factors( G );
[ Z(2)^0+x^2+x^3 ]
gap> C := FireCode( G, 3 );
a cyclic [35,27,1..4]2..6 3 burst error correcting fire code over GF(2)
gap> MinimumDistance( C );
4     # Still it can correct bursts of length 3 
\endexample

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

\beginexample
gap> C := WholeSpaceCode( 5, GF(3) );
a cyclic [5,5,1]0 whole space code over GF(3)
\endexample

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

\beginexample
gap> C := NullCode( 5, GF(3) );
a cyclic [5,0,5]5 nullcode over GF(3)
gap> AsSSortedList( C );
[ [ 0 0 0 0 0 ] ]
\endexample

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

\beginexample
gap> C := RepetitionCode( 3, GF(5) );
a cyclic [3,1,3]2 repetition code over GF(5)
gap> AsSSortedList( C );
[ [ 0 0 0 ], [ 1 1 1 ], [ 2 2 2 ], [ 4 4 4 ], [ 3 3 3 ] ]
gap> IsPerfectCode( C );
false
gap> IsMDSCode( C );
true 
\endexample

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

\beginexample
gap> NrCyclicCodes( 23, GF(2) );
8
gap> codelist := CyclicCodes( 23, GF(2) );
[ a cyclic [23,23,1]0 enumerated code over GF(2), 
  a cyclic [23,22,1..2]1 enumerated code over GF(2), 
  a cyclic [23,11,1..8]4..7 enumerated code over GF(2), 
  a cyclic [23,0,23]23 enumerated code over GF(2), 
  a cyclic [23,11,1..8]4..7 enumerated code over GF(2), 
  a cyclic [23,12,1..7]3 enumerated code over GF(2), 
  a cyclic [23,1,23]11 enumerated code over GF(2), 
  a cyclic [23,12,1..7]3 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 
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%E
