4. Codes
  
  A  code  is  a  set  of  codewords  (recall  a codeword in GUAVA is simply a
  sequence  of elements of a finite field GF(q), where q is a prime power). We
  call  these  the  elements  of  the  code.  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 Chapter 3..
  
  In  GUAVA, codes can be a set specified by its elements (this will be called
  an unrestricted code), by a generator matrix listing a set of basis elements
  (for a linear code) or by a generator polynomial (for a cyclic code).
  
  Any  code can be defined by its elements. If you like, you can give the code
  a name.
  
  ---------------------------  Example  ----------------------------
    gap> C := ElementsCode(["1100", "1010", "0001"], "example code", GF(2) );
    a (4,3,1..4)2..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  (except  in  the case where the code is a random
  linear codes, where these are not printed for efficiency reasons). So
  
  
  a (4,3,1..4)2..4 code over GF(2)
  means  a  binary  unrestricted  code  of  length  4, with 3 elements and the
  minimum  distance  is greater than or equal to 1 and less than or equal to 4
  and the covering radius is greater than or equal to 2 and less than or equal
  to 4.
  
  ---------------------------  Example  ----------------------------
    gap> C := ElementsCode(["1100", "1010", "0001"], "example code", GF(2) );
    a (4,3,1..4)2..4 example code over GF(2) 
    gap> MinimumDistance(C);
    2
    gap> C;
    a (4,3,2)2..4 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.  By definition, the rows of the generator matrix is a
  basis  for  the code (as a vector space over GF(q)). By definition, the rows
  of the parity check matrix is a basis for the dual space of the code,
  
  
       C^* = \{ v \in GF(q)^n\ |\ v\cdot c = 0,\ for \ all\ c \in C \}.
  
  
  ---------------------------  Example  ----------------------------
    gap> G := GeneratorMatCode([[1,0,1],[0,1,2]], "demo code", GF(3) );
    a linear [3,2,1..2]1 demo code over GF(3) 
  ------------------------------------------------------------------
  
  So  a  linear  [n,  k,  d]r  code is a code with word length n, dimension k,
  minimum distance d and covering radius r.
  
  If  the  code  is linear and all cyclic shifts of its codewords (regarded as
  n-tuples)  are again codewords, the code is called cyclic. All elements of a
  cyclic  code  are  multiples of the monic polynomial modulo a polynomial x^n
  -1,  where  n  is the word length of the code. Such a polynomial is called a
  generator  polynomial  The  generator  polynomial  must divide x^n-1 and its
  quotient  is  called  a check polynomial. Multiplying a codeword in a cyclic
  code  by the check polynomial yields zero (modulo the polynomial x^n -1). In
  GUAVA,  a  cyclic  code can be defined by either its generator polynomial or
  check polynomial.
  
  ---------------------------  Example  ----------------------------
    gap> G := GeneratorPolCode(Indeterminate(GF(2))+Z(2)^0, 7, GF(2) );
    a cyclic [7,6,1..2]1 code defined by generator polynomial over GF(2)
  ------------------------------------------------------------------
  
  It is possible that GUAVA does not know that an unrestricted code is in fact
  linear.  This  situation  occurs for example when a code is generated from a
  list  of elements with the function ElementsCode (see ElementsCode (5.1-1)).
  By calling the function IsLinearCode (see IsLinearCode (4.3-4)), GUAVA tests
  if the code can be represented by a generator matrix. If so, the code record
  and the operations are converted accordingly.
  
  ---------------------------  Example  ----------------------------
    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)1 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> C;
    a linear [3,2,1]1 user defined unrestricted code over GF(2) 
  ------------------------------------------------------------------
  
  Of  course the same holds for unrestricted codes that in fact are cyclic, or
  codes, defined by a generator matrix, that actually are cyclic.
  
  Codes  are printed simply by giving a small description of their parameters,
  the  word  length,  size  or  dimension  and  perhaps  the minimum distance,
  followed by a short description and the base field of the code. The function
  Display  gives a more detailed description, showing the construction history
  of the code.
  
  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
  functions  Decode  or  Decodeword.  For  more information about encoding and
  decoding, see sections 4.2 and 4.10-1.
  
  ---------------------------  Example  ----------------------------
    gap> R := ReedMullerCode( 1, 3 );
    a linear [8,4,4]2 Reed-Muller (1,3) code over GF(2)
    gap> w := [ 1, 0, 1, 1 ] * R;
    [ 1 0 0 1 1 0 0 1 ]
    gap> Decode( R, w );
    [ 1 0 1 1 ]
    gap> Decode( R, w + "10000000" ); # One error at the first position
    [ 1 0 1 1 ]                       # Corrected by Guava 
  ------------------------------------------------------------------
  
  Sections  4.1  and 4.2 describe the operations that are available for codes.
  Section  4.3  describe  the functions that tests whether an object is a code
  and  what  kind  of  code  it  is  (see  IsCode,  IsLinearCode  (4.3-4)  and
  IsCyclicCode)  and  various  other  boolean functions for codes. Section 4.4
  describe   functions   about  equivalence  and  isomorphism  of  codes  (see
  IsEquivalent   (4.4-1),   CodeIsomorphism   (4.4-2)   and  AutomorphismGroup
  (4.4-3)).  Section 4.5 describes functions that work on domains (see Chapter
  "Domains  and  their  Elements"  in  the  GAP Reference Manual). Section 4.6
  describes functions for printing and displaying codes. Section 4.7 describes
  functions  that  return the matrices and polynomials that define a code (see
  GeneratorMat  (4.7-1),  CheckMat  (4.7-2),  GeneratorPol  (4.7-3),  CheckPol
  (4.7-4),  RootsOfCode  (4.7-5)). Section 4.8 describes functions that return
  the  basic  parameters  of codes (see WordLength (4.8-1), Redundancy (4.8-2)
  and  MinimumDistance  (4.8-3)).  Section 4.9 describes functions that return
  distance   and   weight   distributions   (see  WeightDistribution  (4.9-2),
  InnerDistribution      (4.9-3),      OuterDistribution      (4.9-5)      and
  DistancesDistribution  (4.9-4)).  Section  4.10 describes functions that are
  related  to  decoding  (see  Decode  (4.10-1), Decodeword (4.10-2), Syndrome
  (4.10-8),  SyndromeTable  (4.10-9) and StandardArray (4.10-10)). In Chapters
  5.  and  6. which follow, we describe functions that generate and manipulate
  codes.
  
  
  4.1 Comparisons of Codes
  
  4.1-1 =
  
  > =( C1, C2 ) ______________________________________________________function
  
  The equality operator C1 = C2 evaluates to `true' if the codes C1 and C2 are
  equal, and to `false' otherwise.
  
  The  equality operator is also denoted EQ, and Eq(C1,C2) is the same as C1 =
  C2. There is also an inequality operator, < >, or not EQ.
  
  Note  that  codes  are equal if and only if their set of elements are equal.
  Codes  can  also be compared with objects of other types. Of course they are
  never equal.
  
  ---------------------------  Example  ----------------------------
    gap> M := [ [0, 0], [1, 0], [0, 1], [1, 1] ];;
    gap> C1 := ElementsCode( M, GF(2) );
    a (2,4,1..2)0 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]0 code defined by generator matrix over GF(2)
    gap> C1 = C2;
    true
    gap> ReedMullerCode( 1, 3 ) = 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   equivalent  (see  IsEquivalent  (4.4-1)).  By  the  way,  this  called
  CodeIsomorphism.  For  the current version of GUAVA, unless one of the codes
  is  unrestricted,  this  calls Leon's C program (which only works for binary
  linear codes and only on a unix/linux computer).
  
  
  4.2 Operations for Codes
  
  4.2-1 +
  
  > +( C1, C2 ) ______________________________________________________function
  
  The  operator  `+'  evaluates  to the direct sum of the codes C1 and C2. See
  DirectSumCode (6.2-1).
  
  ---------------------------  Example  ----------------------------
    gap> C1:=RandomLinearCode(10,5);
    a  [10,5,?] randomly generated code over GF(2)
    gap> C2:=RandomLinearCode(9,4);
    a  [9,4,?] randomly generated code over GF(2)
    gap> C1+C2;
    a linear [10,9,1]0..10 unknown linear code over GF(2)
  ------------------------------------------------------------------
  
  4.2-2 *
  
  > *( C1, C2 ) ______________________________________________________function
  
  The operator `*' evaluates to the direct product of the codes C1 and C2. See
  DirectProductCode (6.2-3).
  
  ---------------------------  Example  ----------------------------
    gap> C1 := GeneratorMatCode( [ [1, 0,0,0], [0, 1,0,0] ], GF(2) );
    a linear [4,2,1]1 code defined by generator matrix over GF(2)
    gap> C2 := GeneratorMatCode( [ [0,0,1, 1], [0,0,0, 1] ], GF(2) );
    a linear [4,2,1]1 code defined by generator matrix over GF(2)
    gap> C1*C2;
    a linear [16,4,1]4..12 direct product code
  ------------------------------------------------------------------
  
  4.2-3 *
  
  > *( m, C ) ________________________________________________________function
  
  The operator m*C evaluates to the element of C belonging to information word
  ('message')  m.  Here m 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  m  by  the generator polynomial of C. If C is a
  linear code, it is equal to the multiplication of an information vector m by
  a generator matrix of C.
  
  To  invert  this,  use  the  function  InformationWord  (see InformationWord
  (4.2-4), which simply calls the function Decode).
  
  ---------------------------  Example  ----------------------------
    gap> C := GeneratorMatCode( [ [1, 0,0,0], [0, 1,0,0] ], GF(2) );
    a linear [4,2,1]1 code defined by generator matrix over GF(2)
    gap> m:=Codeword("11");
    [ 1 1 ]
    gap> m*C;
    [ 1 1 0 0 ]
  ------------------------------------------------------------------
  
  4.2-4 InformationWord
  
  > InformationWord( C, c ) __________________________________________function
  
  Here  C  is  a  linear  code  and  c  is  a  codeword  in  it.  The  command
  InformationWord  returns  the  message  word  (or  'information  digits')  m
  satisfying c=m*C. This command simply calls Decode, provided c in C is true.
  Otherwise, it returns an error.
  
  To invert this, use the encoding function * (see * (4.2-3)).
  
  ---------------------------  Example  ----------------------------
    gap> C:=HammingCode(3);
    a linear [7,4,3]1 Hamming (3,2) code over GF(2)
    gap> c:=Random(C);
    [ 0 0 0 1 1 1 1 ]
    gap> InformationWord(C,c);
    [ 0 1 1 1 ]
    gap> c:=Codeword("1111100");
    [ 1 1 1 1 1 0 0 ]
    gap> InformationWord(C,c);
    "ERROR: codeword must belong to code"
    gap> C:=NordstromRobinsonCode();
    a (16,256,6)4 Nordstrom-Robinson code over GF(2)
    gap> c:=Random(C);
    [ 0 0 0 1 0 0 0 1 0 0 1 0 1 1 0 1 ]
    gap> InformationWord(C,c);
    "ERROR: code must be linear"
  ------------------------------------------------------------------
  
  
  4.3 Boolean Functions for Codes
  
  4.3-1 in
  
  > in( c, C ) _______________________________________________________function
  
  The command c in C 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.
  
  ---------------------------  Example  ----------------------------
    gap> C:= HammingCode( 2 );; eC:= AsSSortedList( C );
    [ [ 0 0 0 ], [ 1 1 1 ] ]
    gap> eC[2] in C;
    true
    gap> [ 0 ] in C;
    false 
  ------------------------------------------------------------------
  
  4.3-2 IsSubset
  
  > IsSubset( C1, C2 ) _______________________________________________function
  
  The command IsSubset(C1,C2) returns `true' if C2 is a subcode of C1, i.e. if
  C1 contains all the elements of C2.
  
  ---------------------------  Example  ----------------------------
    gap> IsSubset( HammingCode(3), RepetitionCode( 7 ) );
    true
    gap> IsSubset( RepetitionCode( 7 ), HammingCode( 3 ) );
    false
    gap> IsSubset( WholeSpaceCode( 7 ), HammingCode( 3 ) );
    true
  ------------------------------------------------------------------
  
  4.3-3 IsCode
  
  > IsCode( obj ) ____________________________________________________function
  
  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.
  
  ---------------------------  Example  ----------------------------
    gap> IsCode( 1 );
    false
    gap> IsCode( ReedMullerCode( 2,3 ) );
    true
  ------------------------------------------------------------------
  
  4.3-4 IsLinearCode
  
  > IsLinearCode( obj ) ______________________________________________function
  
  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
  recorded  as  a  generator matrix of obj and the function returns `true'. If
  not, the function returns `false'.
  
  ---------------------------  Example  ----------------------------
    gap> C := ElementsCode( [ [0,0,0],[1,1,1] ], GF(2) );
    a (3,2,1..3)1 user defined unrestricted code over GF(2)
    gap> IsLinearCode( C );
    true
    gap> IsLinearCode( ElementsCode( [ [1,1,1] ], GF(2) ) );
    false
    gap> IsLinearCode( 1 );
    false 
  ------------------------------------------------------------------
  
  4.3-5 IsCyclicCode
  
  > IsCyclicCode( obj ) ______________________________________________function
  
  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 recorded as a generator polynomial of obj and
  the function returns `true'. If not, the function returns `false'.
  
  ---------------------------  Example  ----------------------------
    gap> C := ElementsCode( [ [0,0,0], [1,1,1] ], GF(2) );
    a (3,2,1..3)1 user defined unrestricted code over GF(2)
    gap> # 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 
  ------------------------------------------------------------------
  
  4.3-6 IsPerfectCode
  
  > IsPerfectCode( C ) _______________________________________________function
  
  IsPerfectCode(C)  returns  `true' if C is a perfect code. If Csubset GF(q)^n
  then,  by definition, this means that for some positive integer t, the space
  GF(q)^n is covered by non-overlapping spheres of (Hamming) radius t centered
  at  the  codewords in C. 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 "trivially 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 (see section 1.12 in [HP03]).
  
  ---------------------------  Example  ----------------------------
    gap> H := HammingCode(2);
    a linear [3,1,3]1 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 
  ------------------------------------------------------------------
  
  4.3-7 IsMDSCode
  
  > IsMDSCode( C ) ___________________________________________________function
  
  IsMDSCode(C) returns true if C is a maximum distance separable (MDS) code. 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  (7.1-1)).  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.
  
  ---------------------------  Example  ----------------------------
    gap> C1 := ReedSolomonCode( 6, 3 );
    a cyclic [6,4,3]2 Reed-Solomon code over GF(7)
    gap> IsMDSCode( C1 );
    true    # 6-3+1 = 4
    gap> IsMDSCode( QRCode( 23, GF(2) ) );
    false 
  ------------------------------------------------------------------
  
  4.3-8 IsSelfDualCode
  
  > IsSelfDualCode( C ) ______________________________________________function
  
  IsSelfDualCode(C)  returns `true' if C is self-dual, i.e. when C is equal to
  its  dual  code  (see  also  DualCode  (6.1-14)).  A code is self-dual if it
  contains  all  vectors  that  its  elements  are orthogonal to. If a code is
  self-dual,  it  automatically  is  self-orthogonal (see IsSelfOrthogonalCode
  (4.3-9)).
  
  If  C  is a non-linear code, it cannot be self-dual (the dual code is always
  linear),  so  `false'  is returned. A linear code can only be self-dual when
  its dimension k is equal to the redundancy r.
  
  ---------------------------  Example  ----------------------------
    gap> IsSelfDualCode( ExtendedBinaryGolayCode() );
    true
    gap> C := ReedMullerCode( 1, 3 );
    a linear [8,4,4]2 Reed-Muller (1,3) code over GF(2)
    gap> DualCode( C ) = C;
    true 
  ------------------------------------------------------------------
  
  4.3-9 IsSelfOrthogonalCode
  
  > IsSelfOrthogonalCode( C ) ________________________________________function
  
  IsSelfOrthogonalCode(C)  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.)
  
  ---------------------------  Example  ----------------------------
    gap> R := ReedMullerCode(1,4);
    a linear [16,5,8]6 Reed-Muller (1,4) code over GF(2)
    gap> IsSelfOrthogonalCode(R);
    true
    gap> IsSelfDualCode(R);
    false 
  ------------------------------------------------------------------
  
  4.3-10 IsDoublyEvenCode
  
  > IsDoublyEvenCode( C ) ____________________________________________function
  
  IsDoublyEvenCode(C)  returns  `true'  if C is a binary linear code which has
  codewords  of weight divisible by 4 only. According to [HP03], a doubly-even
  code  is  self-orthogonal  and  every row in its generator matrix has weight
  that is divisible by 4.
  
  ---------------------------  Example  ----------------------------
    gap> C:=BinaryGolayCode();
    a cyclic [23,12,7]3 binary Golay code over GF(2)
    gap> WeightDistribution(C);
    [ 1, 0, 0, 0, 0, 0, 0, 253, 506, 0, 0, 1288, 1288, 0, 0, 506, 253, 0, 0, 0, 0, 0, 0, 1 ]
    gap> IsDoublyEvenCode(C);  
    false
    gap> C:=ExtendedCode(C);  
    a linear [24,12,8]4 extended code
    gap> WeightDistribution(C);
    [ 1, 0, 0, 0, 0, 0, 0, 0, 759, 0, 0, 0, 2576, 0, 0, 0, 759, 0, 0, 0, 0, 0, 0, 0, 1 ]
    gap> IsDoublyEvenCode(C);  
    true
  ------------------------------------------------------------------
  
  4.3-11 IsSinglyEvenCode
  
  > IsSinglyEvenCode( C ) ____________________________________________function
  
  IsSinglyEvenCode(C)  returns  `true' if C is a binary self-orthogonal linear
  code which is not doubly-even. In other words, C is a binary self-orthogonal
  code which has codewords of even weight.
  
  ---------------------------  Example  ----------------------------
    gap> x:=Indeterminate(GF(2));                     
    x_1
    gap> C:=QuasiCyclicCode( [x^0, 1+x^3+x^5+x^6+x^7], 11, GF(2) );
    a linear [22,11,1..6]4..7 quasi-cyclic code over GF(2)
    gap> IsSelfDualCode(C);  # self-dual is a restriction of self-orthogonal
    true
    gap> IsDoublyEvenCode(C);
    false
    gap> IsSinglyEvenCode(C);
    true
  ------------------------------------------------------------------
  
  4.3-12 IsEvenCode
  
  > IsEvenCode( C ) __________________________________________________function
  
  IsEvenCode(C)  returns  `true'  if  C  is  a  binary  linear  code which has
  codewords of even weight--regardless whether or not it is self-orthogonal.
  
  ---------------------------  Example  ----------------------------
    gap> C:=BinaryGolayCode();
    a cyclic [23,12,7]3 binary Golay code over GF(2)
    gap> IsSelfOrthogonalCode(C);
    false
    gap> IsEvenCode(C);
    false
    gap> C:=ExtendedCode(C);
    a linear [24,12,8]4 extended code
    gap> IsSelfOrthogonalCode(C);
    true
    gap> IsEvenCode(C);
    true
    gap> C:=ExtendedCode(QRCode(17,GF(2)));
    a linear [18,9,6]3..5 extended code
    gap> IsSelfOrthogonalCode(C);
    false
    gap> IsEvenCode(C);
    true
  ------------------------------------------------------------------
  
  4.3-13 IsSelfComplementaryCode
  
  > IsSelfComplementaryCode( C ) _____________________________________function
  
  IsSelfComplementaryCode returns `true' if
  
  
       v \in C \Rightarrow 1 - v \in C,
  
  
  where 1 is the all-one word of length n.
  
  ---------------------------  Example  ----------------------------
    gap> IsSelfComplementaryCode( HammingCode( 3, GF(2) ) );
    true
    gap> IsSelfComplementaryCode( EvenWeightSubcode(
    > HammingCode( 3, GF(2) ) ) );
    false 
  ------------------------------------------------------------------
  
  4.3-14 IsAffineCode
  
  > IsAffineCode( C ) ________________________________________________function
  
  IsAffineCode  returns `true' if C is an affine code. A code is called affine
  if  it is an affine space. In other words, a code is affine if it is a coset
  of a linear code.
  
  ---------------------------  Example  ----------------------------
    gap> IsAffineCode( HammingCode( 3, GF(2) ) );
    true
    gap> IsAffineCode( CosetCode( HammingCode( 3, GF(2) ),
    > [ 1, 0, 0, 0, 0, 0, 0 ] ) );
    true
    gap> IsAffineCode( NordstromRobinsonCode() );
    false 
  ------------------------------------------------------------------
  
  4.3-15 IsAlmostAffineCode
  
  > IsAlmostAffineCode( C ) __________________________________________function
  
  IsAlmostAffineCode  returns  `true' if C is an almost affine code. A code is
  called  almost affine if the size of any punctured code of C is q^r for some
  r,  where  q  is  the size of the alphabet of the code. Every affine code is
  also  almost  affine,  and  every  code  over GF(2) and GF(3) that is almost
  affine is also affine.
  
  ---------------------------  Example  ----------------------------
    gap> code := ElementsCode( [ [0,0,0], [0,1,1], [0,2,2], [0,3,3],
    >                             [1,0,1], [1,1,0], [1,2,3], [1,3,2],
    >                             [2,0,2], [2,1,3], [2,2,0], [2,3,1],
    >                             [3,0,3], [3,1,2], [3,2,1], [3,3,0] ],
    >                             GF(4) );;
    gap> IsAlmostAffineCode( code );
    true
    gap> IsAlmostAffineCode( NordstromRobinsonCode() );
    false 
  ------------------------------------------------------------------
  
  
  4.4 Equivalence and Isomorphism of Codes
  
  4.4-1 IsEquivalent
  
  > IsEquivalent( C1, C2 ) ___________________________________________function
  
  We say that C1 is permutation equivalent to C2 if C1 can be obtained from C2
  by  carrying out column permutations. IsEquivalent returns true if C1 and C2
  are  equivalent codes. At this time, IsEquivalent only handles binary codes.
  (The  external  unix/linux  program  desauto  from  J.  S. Leon is called by
  IsEquivalent.) Of course, if C1 and C2 are equal, they are also equivalent.
  
  Note that the algorithm is very slow for non-linear codes.
  
  More  generally,  we  say  that C1 is equivalent to C2 if C1 can be obtained
  from  C2  by  carrying  out  column  permutations  and  a permutation of the
  alphabet.
  
  ---------------------------  Example  ----------------------------
    gap> x:= Indeterminate( GF(2) );; pol:= x^3+x+1; 
    Z(2)^0+x_1+x_1^3
    gap> H := GeneratorPolCode( pol, 7, GF(2));          
    a cyclic [7,4,1..3]1 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) 
  ------------------------------------------------------------------
  
  4.4-2 CodeIsomorphism
  
  > CodeIsomorphism( C1, C2 ) ________________________________________function
  
  If   the  two  codes  C1  and  C2  are  permutation  equivalent  codes  (see
  IsEquivalent   (4.4-1)),   CodeIsomorphism   returns  the  permutation  that
  transforms C1 into C2. If the codes are not equivalent, it returns `false'.
  
  At  this  time, IsEquivalent only computes isomorphisms between binary codes
  on a linux/unix computer (since it calls Leon's C program desauto).
  
  ---------------------------  Example  ----------------------------
    gap> x:= Indeterminate( GF(2) );; pol:= x^3+x+1; 
    Z(2)^0+x_1+x_1^3
    gap> H := GeneratorPolCode( pol, 7, GF(2));          
    a cyclic [7,4,1..3]1 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 
  ------------------------------------------------------------------
  
  4.4-3 AutomorphismGroup
  
  > AutomorphismGroup( C ) ___________________________________________function
  
  AutomorphismGroup  returns  the automorphism group of a linear code C. For a
  binary  code,  the  automorphism  group  is the largest permutation group of
  degree n such that each permutation applied to the columns of C again yields
  C.  GUAVA  calls  the  external program desauto written by J. S. Leon, if it
  exists, to compute the automorphism group. If Leon's program is not compiled
  on  the system (and in the default directory) then it calls instead the much
  slower program PermutationAutomorphismGroup.
  
  See  Leon  [Leo82]  for  a  more  precise description of the method, and the
  guava/src/leon/doc subdirectory for for details about Leon's C programs.
  
  The  function  PermutedCode permutes the columns of a code (see PermutedCode
  (6.1-4)).
  
  ---------------------------  Example  ----------------------------
    gap> R := RepetitionCode(7,GF(2));
    a cyclic [7,1,7]3 repetition code over GF(2)
    gap> AutomorphismGroup(R);
    Sym( [ 1 .. 7 ] )
                            # every permutation keeps R identical
    gap> C := CordaroWagnerCode(7);
    a linear [7,2,4]3 Cordaro-Wagner code over GF(2)
    gap> AsSSortedList(C);
    [ [ 0 0 0 0 0 0 0 ], [ 0 0 1 1 1 1 1 ], [ 1 1 0 0 0 1 1 ], [ 1 1 1 1 1 0 0 ] ]
    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]3 permuted code
    gap> AsSSortedList(C2);
    [ [ 0 0 0 0 0 0 0 ], [ 0 0 1 1 1 1 1 ], [ 1 1 0 0 0 1 1 ], [ 1 1 1 1 1 0 0 ] ]
    gap> C2 = C;
    true 
  ------------------------------------------------------------------
  
  4.4-4 PermutationAutomorphismGroup
  
  > PermutationAutomorphismGroup( C ) ________________________________function
  
  PermutationAutomorphismGroup returns the permutation automorphism group of a
  linear  code  C. This is the largest permutation group of degree n such that
  each  permutation  applied to the columns of C again yields C. It is written
  in GAP, so is much slower than AutomorphismGroup.
  
  When    C    is    binary   PermutationAutomorphismGroup   does   not   call
  AutomorphismGroup,  even though they agree mathematically in that case. This
  way  PermutationAutomorphismGroup  can  be called on any platform which runs
  GAP.
  
  The  older  name for this command, PermutationGroup, will become obsolete in
  the next version of GAP.
  
  ---------------------------  Example  ----------------------------
    gap> R := RepetitionCode(3,GF(3));
    a cyclic [3,1,3]2 repetition code over GF(3)
    gap> G:=PermutationAutomorphismGroup(R);
    Group([ (), (1,3), (1,2,3), (2,3), (1,3,2), (1,2) ])
    gap> G=SymmetricGroup(3);
    true
  ------------------------------------------------------------------
  
  
  4.5 Domain Functions for Codes
  
  These  are  some  GAP  functions  that  work  on `Domains' in general. Their
  specific effect on `Codes' is explained here.
  
  4.5-1 IsFinite
  
  > IsFinite( C ) ____________________________________________________function
  
  IsFinite  is  an  implementation  of  the  GAP  domain function IsFinite. It
  returns true for a code C.
  
  ---------------------------  Example  ----------------------------
    gap> IsFinite( RepetitionCode( 1000, GF(11) ) );
    true 
  ------------------------------------------------------------------
  
  4.5-2 Size
  
  > Size( C ) ________________________________________________________function
  
  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.
  
  ---------------------------  Example  ----------------------------
    gap> Size( RepetitionCode( 1000, GF(11) ) );
    11
    gap> Size( NordstromRobinsonCode() );
    256 
  ------------------------------------------------------------------
  
  4.5-3 LeftActingDomain
  
  > LeftActingDomain( C ) ____________________________________________function
  
  LeftActingDomain  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.
  
  ---------------------------  Example  ----------------------------
    gap> C1 := ElementsCode([[0,0,0], [1,0,1], [0,1,0]], GF(4));
    a (3,3,1..3)2..3 user defined unrestricted code over GF(4)
    gap> LeftActingDomain( C1 );
    GF(2^2)
    gap> LeftActingDomain( HammingCode( 3, GF(9) ) );
    GF(3^2) 
  ------------------------------------------------------------------
  
  4.5-4 Dimension
  
  > Dimension( C ) ___________________________________________________function
  
  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.
  
  ---------------------------  Example  ----------------------------
    gap> Dimension( NullCode( 5, GF(5) ) );
    0
    gap> C := BCHCode( 15, 4, GF(4) );
    a cyclic [15,9,5]3..4 BCH code, delta=5, b=1 over GF(4)
    gap> Dimension( C );
    9
    gap> Size( C ) = Size( LeftActingDomain( C ) ) ^ Dimension( C );
    true 
  ------------------------------------------------------------------
  
  4.5-5 AsSSortedList
  
  > AsSSortedList( C ) _______________________________________________function
  
  AsSSortedList (as strictly sorted list) returns an immutable, duplicate free
  list  of  the elements of C. For a finite field GF(q) generated by powers of
  Z(q), the ordering on
  
  
       GF(q)=\{ 0 , Z(q)^0, Z(q), Z(q)^2, ...Z(q)^{q-2} \}
  
  
  is  that  determined  by  the  exponents  i.  These elements are of the type
  codeword  (see  Codeword (3.1-1)). 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
  (3.1-2)).
  
  ---------------------------  Example  ----------------------------
    gap> C := ConferenceCode( 5 );
    a (5,12,2)1..4 conference code over GF(2)
    gap> AsSSortedList( C );
    [ [ 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 ] ]
    gap> CodewordNr( C, [ 1, 2 ] );
    [ [ 0 0 0 0 0 ], [ 0 0 1 1 1 ] ]
  ------------------------------------------------------------------
  
  
  4.6 Printing and Displaying Codes
  
  4.6-1 Print
  
  > Print( C ) _______________________________________________________function
  
  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)r ... code over GF(q)
  is  printed,  where  n  is  the word length, M the number of elements of the
  code, d the minimum distance and r the covering radius.
  
  If the argument is a linear code, information in the form
  
  
  a linear [n,k,d]r ... code over GF(q)
  is  printed,  where n is the word length, k the dimension of the code, d the
  minimum distance and r the covering radius.
  
  Except  for codes produced by RandomLinearCode, if d is not yet known, it is
  displayed in the form
  
  
  lowerbound..upperbound
  and  if  r  is  not  yet known, it is displayed in the same way. For certain
  ranges  of  n,  the  values  of  lowerbound and upperbound are obtained from
  tables.
  
  The function Display gives more information. See Display (4.6-3).
  
  ---------------------------  Example  ----------------------------
    gap> C1 := ExtendedCode( HammingCode( 3, GF(2) ) );
    a linear [8,4,4]2 extended code
    gap> Print( "This is ", NordstromRobinsonCode(), ". \n");
    This is a (16,256,6)4 Nordstrom-Robinson code over GF(2). 
  ------------------------------------------------------------------
  
  4.6-2 String
  
  > String( C ) ______________________________________________________function
  
  String  returns  information  about  C in a string. This function is used by
  Print.
  
  ---------------------------  Example  ----------------------------
    gap> x:= Indeterminate( GF(3) );; pol:= x^2+1;
    x_1^2+Z(3)^0
    gap> Factors(pol);
    [ x_1^2+Z(3)^0 ]
    gap> H := GeneratorPolCode( pol, 8, GF(3));
    a cyclic [8,6,1..2]1..2 code defined by generator polynomial over GF(3)
    gap> String(H);
    "a cyclic [8,6,1..2]1..2 code defined by generator polynomial over GF(3)"
  ------------------------------------------------------------------
  
  4.6-3 Display
  
  > Display( C ) _____________________________________________________function
  
  Display  prints  the method of construction of code C. With this history, in
  most  cases  an  equal  or  equivalent code can be reconstructed. If C is an
  unmanipulated code, the result is equal to output of the function Print (see
  Print (4.6-1)).
  
  ---------------------------  Example  ----------------------------
    gap> Display( RepetitionCode( 6, GF(3) ) );
    a cyclic [6,1,6]4 repetition code over GF(3)
    gap> C1 := ExtendedCode( HammingCode(2) );;
    gap> C2 := PuncturedCode( ReedMullerCode( 2, 3 ) );;
    gap> Display( LengthenedCode( UUVCode( C1, C2 ) ) );
    a linear [12,8,2]2..4 code, lengthened with 1 column(s) of
    a linear [11,8,1]1..2 U U+V construction code of
    U: a linear [4,1,4]2 extended code of
       a linear [3,1,3]1 Hamming (2,2) code over GF(2)
    V: a linear [7,7,1]0 punctured code of
       a cyclic [8,7,2]1 Reed-Muller (2,3) code over GF(2)
  ------------------------------------------------------------------
  
  4.6-4 DisplayBoundsInfo
  
  > DisplayBoundsInfo( bds ) _________________________________________function
  
  DisplayBoundsInfo  prints the method of construction of the code C indicated
  in bds:= BoundsMinimumDistance( n, k, GF(q) ).
  
  ---------------------------  Example  ----------------------------
    gap> bounds := BoundsMinimumDistance( 20, 17, GF(4) );
    gap> DisplayBoundsInfo(bounds);
    an optimal linear [20,17,d] code over GF(4) has d=3
    --------------------------------------------------------------------------------------------------
    Lb(20,17)=3, by shortening of:
    Lb(21,18)=3, by applying contruction B to a [81,77,3] code
    Lb(81,77)=3, by shortening of:
    Lb(85,81)=3, reference: Ham
    --------------------------------------------------------------------------------------------------
    Ub(20,17)=3, by considering shortening to:
    Ub(7,4)=3, by considering puncturing to:
    Ub(6,4)=2, by construction B applied to:
    Ub(2,1)=2, repetition code
    --------------------------------------------------------------------------------------------------
    Reference Ham:
    %T this reference is unknown, for more info
    %T contact A.E. Brouwer (aeb@cwi.nl)
  ------------------------------------------------------------------
  
  
  4.7 Generating (Check) Matrices and Polynomials
  
  4.7-1 GeneratorMat
  
  > GeneratorMat( C ) ________________________________________________function
  
  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  polynomial,  the  check
  polynomial or the elements (if possible), whichever is available.
  
  If C is a non-linear code, the function returns an error.
  
  ---------------------------  Example  ----------------------------
    gap> GeneratorMat( HammingCode( 3, GF(2) ) );
    [ [ an immutable GF2 vector of length 7], 
      [ an immutable GF2 vector of length 7], 
      [ an immutable GF2 vector of length 7], 
      [ an immutable GF2 vector of length 7] ]
    gap> Display(last);
     1 1 1 . . . .
     1 . . 1 1 . .
     . 1 . 1 . 1 .
     1 1 . 1 . . 1
    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) ) );
    [  ]
  ------------------------------------------------------------------
  
  4.7-2 CheckMat
  
  > CheckMat( C ) ____________________________________________________function
  
  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 polynomial, the
  check polynomial or the elements of C (if possible), whichever is available.
  
  If C is a non-linear code, the function returns an error.
  
  ---------------------------  Example  ----------------------------
    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> Display(last);
     . . . 1 1 1 1
     . 1 1 . . 1 1
     1 . 1 . 1 . 1
    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) ) );
    [  ] 
  ------------------------------------------------------------------
  
  4.7-3 GeneratorPol
  
  > GeneratorPol( C ) ________________________________________________function
  
  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'.
  
  ---------------------------  Example  ----------------------------
    gap> GeneratorPol(GeneratorMatCode([[1, 1, 0], [0, 1, 1]], GF(2)));
    Z(2)^0+x_1
    gap> GeneratorPol( WholeSpaceCode( 4, GF(2) ) );
    Z(2)^0
    gap> GeneratorPol( NullCode( 7, GF(3) ) );
    -Z(3)^0+x_1^7
  ------------------------------------------------------------------
  
  4.7-4 CheckPol
  
  > CheckPol( C ) ____________________________________________________function
  
  CheckPol  returns  the  check  polynomial  of  C.  The  code consists of all
  polynomials f with
  
  
       f\cdot h \equiv 0 \ ({\rm 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.
  
  ---------------------------  Example  ----------------------------
    gap> CheckPol(GeneratorMatCode([[1, 1, 0], [0, 1, 1]], GF(2)));
    Z(2)^0+x_1+x_1^2
    gap> CheckPol(WholeSpaceCode(4, GF(2)));
    Z(2)^0+x_1^4
    gap> CheckPol(NullCode(7,GF(3)));
    Z(3)^0
  ------------------------------------------------------------------
  
  4.7-5 RootsOfCode
  
  > RootsOfCode( C ) _________________________________________________function
  
  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 process, constructing a code from a set of roots, can be carried
  out by the function RootsCode (see RootsCode (5.5-3)).
  
  ---------------------------  Example  ----------------------------
    gap> C1 := ReedSolomonCode( 16, 5 );
    a cyclic [16,12,5]3..4 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]3..4 code defined by roots over GF(17)
    gap> C1 = C2;
    true 
  ------------------------------------------------------------------
  
  
  4.8 Parameters of Codes
  
  4.8-1 WordLength
  
  > WordLength( C ) __________________________________________________function
  
  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.
  
  ---------------------------  Example  ----------------------------
    gap> WordLength( NordstromRobinsonCode() );
    16
    gap> WordLength( PuncturedCode( WholeSpaceCode(7) ) );
    6
    gap> WordLength( UUVCode( WholeSpaceCode(7), RepetitionCode(7) ) );
    14 
  ------------------------------------------------------------------
  
  4.8-2 Redundancy
  
  > Redundancy( C ) __________________________________________________function
  
  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.
  
  ---------------------------  Example  ----------------------------
    gap> C := TernaryGolayCode();
    a cyclic [11,6,5]2 ternary Golay code over GF(3)
    gap> Redundancy(C);
    5
    gap> Redundancy( DualCode(C) );
    6 
  ------------------------------------------------------------------
  
  4.8-3 MinimumDistance
  
  > MinimumDistance( C ) _____________________________________________function
  
  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  DistanceCodeword (3.6-2)) 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]   <>   0,   where
  w=(w[1],w[2],...,w[n])    is    the    weight   distribution   of   C   (see
  WeightDistribution  (4.9-2)).  For  unrestricted  codes,  d  is the smallest
  positive value with w[d+1] <> 0, where w is the inner distribution of C (see
  InnerDistribution (4.9-3)).
  
  For codes with only one element, the minimum distance is defined to be equal
  to the word length.
  
  For  linear  codes C, the algorithm used is the following: After replacing C
  by  a permutation equivalent C', one may assume the generator matrix has the
  following  form  G=(I_k  ,  |  , A), for some kx (n-k) matrix A. If A=0 then
  return  d(C)=1.  Next,  find the minimum distance of the code spanned by the
  rows  of  A.  Call  this  distance  d(A). Note that d(A) is equal to the the
  Hamming  distance  d(v,0)  where  v  is  some proper linear combination of i
  distinct rows of A. Return d(C)=d(A)+i, where i is as in the previous step.
  
  This  command  may also be called using the syntax MinimumDistance(C, w). In
  this  form,  MinimumDistance returns the minimum distance of a codeword w to
  the code C, also called the distance from w 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] <> 0, where D is the
  distance distribution of w to C (see DistancesDistribution (4.9-4)).
  
  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).
  
  ---------------------------  Example  ----------------------------
    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 ] 
    gap> C := MOLSCode(7);; w := CodewordNr( C, 17 );
    [ 3 3 6 2 ]
    gap> MinimumDistance( C, w );
    0
    gap> C := RemovedElementsCode( C, w );; MinimumDistance( C, w );
    3                           # so w no longer belongs to C 
  ------------------------------------------------------------------
  
  See  also  the  GUAVA commands relating to bounds on the minimum distance in
  section 7.1.
  
  4.8-4 MinimumDistanceLeon
  
  > MinimumDistanceLeon( C ) _________________________________________function
  
  MinimumDistanceLeon  returns  the  ``probable'' minimum distance d_Leon of a
  linear  binary  code  C,  using  an  implementation  of Leon's probabilistic
  polynomial  time  algorithm.  Briefly: Let C be a linear code of dimension k
  over  GF(q)  as above. The algorithm has input parameters s and rho, where s
  is an integer between 2 and n-k, and rho is an integer between 2 and k.
  
  --    Find a generator matrix G of C.
  
  --    Randomly permute the columns of G.
  
  --    Perform  Gaussian  elimination  on the permuted matrix to obtain a new
        matrix of the following form:
  
  
             G=(I_{k} \, | \, Z \, | \, B)
  
  
        with  Z  a  kx s matrix. If (Z,B) is the zero matrix then return 1 for
        the  minimum  distance.  If  Z=0  but not B then either choose another
        permutation of the rows of C or return `method fails'.
  
  --    Search  Z  for  at most rho rows that lead to codewords of weight less
        than rho.
  
  --    For these codewords, compute the weight of the whole word in C. Return
        this weight.
  
  (See for example J. S. Leon, [Leo88] for more details.) Sometimes (as is the
  case  in  GUAVA)  this probabilistic algorithm is repeated several times and
  the  most commonly occurring value is taken. (This function actually has two
  optional  arguments:  p  and  num.  The command MinimumDistanceLeon(C,p,num)
  allows  a bit more flexibility for the user - see the GAP code in codeops.gi
  for details.)
  
  ---------------------------  Example  ----------------------------
    gap> C:=RandomLinearCode(50,22,GF(2));
    a  [50,22,?] randomly generated code over GF(2)
    gap> MinimumDistanceLeon(C); time;
    6
    211
    gap> MinimumDistance(C); time;
    6
    1204
  ------------------------------------------------------------------
  
  4.8-5 MinimumWeight
  
  > MinimumWeight( C ) _______________________________________________function
  
  MinimumWeight  returns the minimum Hamming weight of a linear code C. At the
  moment,  this  function  works  for  binary  and  ternary  codes  only.  The
  MinimumWeight  function  relies  on  an external executable program which is
  written in C language. As a consequence, the execution time of MinimumWeight
  function is faster than that of MinimumDistance (4.8-3) function.
  
  The  MinimumWeight  function  implements  Chen's  [Che69]  algorithm if C is
  cyclic,  and  Zimmermann's  [Zim96] algorithm if C is a general linear code.
  This  function has a built-in check on the constraints of the minimum weight
  codewords.  For  example, for a self-orthogonal code over GF(3), the minimum
  weight  codewords  have  weight  that  is  divisible  by  3,  i.e.  0  mod 3
  congruence. Similary, self-orthogonal codes over GF(2) have codeword weights
  that  are  divisible  by  4 and even codes over GF(2) have codewords weights
  that  are  divisible by 2. By taking these constraints into account, in many
  cases, the execution time may be significantly reduced. Consider the minimum
  Hamming  weight  enumeration  of  the  [151,45]  binary  cyclic code (second
  example  below).  This  cyclic code is self-orthogonal, so the weight of all
  codewords  is  divisible  by  4.  Without  considering  this constraint, the
  computation  will finish at information weight 10, rather than 9. We can see
  that,  this  0  mod  4 constraint on the codeword weights, has allowed us to
  avoid  enumeration  of  b(45,10) = 3,190,187,286 additional codewords, where
  b(n,k)=n!/((n-k)!k!) is the binomial coefficient of integers n and k.
  
  Note  that the C source code for this minimum weight computation has not yet
  been  optimised,  especially  the  code  for GF(3), and there are chances to
  improve the speed of this function. Your contributions are most welcomed.
  
  If   you   find   any   bugs   on   this   function,  please  report  it  to
  ctjhai@plymouth.ac.uk.
  
  ---------------------------  Example  ----------------------------
    gap> # Extended ternary quadratic residue code of length 48
    gap> n := 47;;
    gap> x := Indeterminate(GF(3));;
    gap> F := Factors(x^n-1);;
    gap> v := List([1..n], i->Zero(GF(3)));;
    gap> v := v + MutableCopyMat(VectorCodeword( Codeword(F[2]) ));;
    gap> G := CirculantMatrix(24, v);;
    gap> for i in [1..Size(G)] do; s:=Zero(GF(3));
    > for j in [1..Size(G[i])] do; s:=s+G[i][j]; od; Append(G[i], [ s ]);
    > od;;
    gap> C := GeneratorMatCodeNC(G, GF(3));
    a  [48,24,?] randomly generated code over GF(3)
    gap> MinimumWeight(C);
    [48,24] linear code over GF(3) - minimum weight evaluation
    Known lower-bound: 1
    There are 2 generator matrices, ranks : 24 24 
    The weight of the minimum weight codeword satisfies 0 mod 3 congruence
    Enumerating codewords with information weight 1 (w=1)
        Found new minimum weight 15
    Number of matrices required for codeword enumeration 2
    Completed w= 1, 48 codewords enumerated, lower-bound 6, upper-bound 15
    Termination expected with information weight 6 at matrix 1
    -----------------------------------------------------------------------------
    Enumerating codewords with information weight 2 (w=2) using 2 matrices
    Completed w= 2, 1104 codewords enumerated, lower-bound 6, upper-bound 15
    Termination expected with information weight 6 at matrix 1
    -----------------------------------------------------------------------------
    Enumerating codewords with information weight 3 (w=3) using 2 matrices
    Completed w= 3, 16192 codewords enumerated, lower-bound 9, upper-bound 15
    Termination expected with information weight 6 at matrix 1
    -----------------------------------------------------------------------------
    Enumerating codewords with information weight 4 (w=4) using 2 matrices
    Completed w= 4, 170016 codewords enumerated, lower-bound 12, upper-bound 15
    Termination expected with information weight 6 at matrix 1
    -----------------------------------------------------------------------------
    Enumerating codewords with information weight 5 (w=5) using 2 matrices
    Completed w= 5, 1360128 codewords enumerated, lower-bound 12, upper-bound 15
    Termination expected with information weight 6 at matrix 1
    -----------------------------------------------------------------------------
    Enumerating codewords with information weight 6 (w=6) using 1 matrices
    Completed w= 6, 4307072 codewords enumerated, lower-bound 15, upper-bound 15
    -----------------------------------------------------------------------------
    Minimum weight: 15
    15
    gap> 
    
    gap> # Binary cyclic code [151,45,36]
    gap> n := 151;;
    gap> x := Indeterminate(GF(2));;
    gap> F := Factors(x^n-1);;
    gap> C := CheckPolCode(F[2]*F[3]*F[3]*F[4], n, GF(2));
    a cyclic [151,45,1..50]31..75 code defined by check polynomial over GF(2)
    gap> MinimumWeight(C);
    [151,45] cyclic code over GF(2) - minimum weight evaluation
    Known lower-bound: 1
    The weight of the minimum weight codeword satisfies 0 mod 4 congruence
    Enumerating codewords with information weight 1 (w=1)
        Found new minimum weight 56
        Found new minimum weight 44
    Number of matrices required for codeword enumeration 1
    Completed w= 1, 45 codewords enumerated, lower-bound 8, upper-bound 44
    Termination expected with information weight 11
    -----------------------------------------------------------------------------
    Enumerating codewords with information weight 2 (w=2) using 1 matrix
    Completed w= 2, 990 codewords enumerated, lower-bound 12, upper-bound 44
    Termination expected with information weight 11
    -----------------------------------------------------------------------------
    Enumerating codewords with information weight 3 (w=3) using 1 matrix
       Found new minimum weight 40
       Found new minimum weight 36
    Completed w= 3, 14190 codewords enumerated, lower-bound 16, upper-bound 36
    Termination expected with information weight 9
    -----------------------------------------------------------------------------
    Enumerating codewords with information weight 4 (w=4) using 1 matrix
    Completed w= 4, 148995 codewords enumerated, lower-bound 20, upper-bound 36
    Termination expected with information weight 9
    -----------------------------------------------------------------------------
    Enumerating codewords with information weight 5 (w=5) using 1 matrix
    Completed w= 5, 1221759 codewords enumerated, lower-bound 24, upper-bound 36
    Termination expected with information weight 9
    -----------------------------------------------------------------------------
    Enumerating codewords with information weight 6 (w=6) using 1 matrix
    Completed w= 6, 8145060 codewords enumerated, lower-bound 24, upper-bound 36
    Termination expected with information weight 9
    -----------------------------------------------------------------------------
    Enumerating codewords with information weight 7 (w=7) using 1 matrix
    Completed w= 7, 45379620 codewords enumerated, lower-bound 28, upper-bound 36
    Termination expected with information weight 9
    -----------------------------------------------------------------------------
    Enumerating codewords with information weight 8 (w=8) using 1 matrix
    Completed w= 8, 215553195 codewords enumerated, lower-bound 32, upper-bound 36
    Termination expected with information weight 9
    -----------------------------------------------------------------------------
    Enumerating codewords with information weight 9 (w=9) using 1 matrix
    Completed w= 9, 886163135 codewords enumerated, lower-bound 36, upper-bound 36
    -----------------------------------------------------------------------------
    Minimum weight: 36
    36
  ------------------------------------------------------------------
  
  4.8-6 DecreaseMinimumDistanceUpperBound
  
  > DecreaseMinimumDistanceUpperBound( C, t, m ) _____________________function
  
  DecreaseMinimumDistanceUpperBound  is an implementation of the algorithm for
  the  minimum  distance  of  a  linear  binary  code  C by Leon [Leo88]. This
  algorithm  tries to find codewords with small minimum weights. The parameter
  t  is  at  least  1  and  less than the dimension of C. The best results are
  obtained  if it is close to the dimension of the code. The parameter m gives
  the number of runs that the algorithm will perform.
  
  The  result  returned is a record with two fields; the first, mindist, gives
  the  lowest  weight  found, and word gives the corresponding codeword. (This
  was  implemented  before  MinimumDistanceLeon  but  independently. The older
  manual  had  given  the  command  incorrectly, so the command was only found
  after  reading  all  the  *.gi  files  in  the  GUAVA  library.  Though both
  MinimumDistance   and   MinimumDistanceLeon   often  run  much  faster  than
  DecreaseMinimumDistanceUpperBound, DecreaseMinimumDistanceUpperBound appears
  to be more accurate than MinimumDistanceLeon.)
  
  ---------------------------  Example  ----------------------------
    gap> C:=RandomLinearCode(5,2,GF(2));
    a  [5,2,?] randomly generated code over GF(2)
    gap> DecreaseMinimumDistanceUpperBound(C,1,4);
    rec( mindist := 3, word := [ 0*Z(2), Z(2)^0, Z(2)^0, 0*Z(2), Z(2)^0 ] )
    gap> MinimumDistance(C);
    3
    gap> C:=RandomLinearCode(8,4,GF(2));
    a  [8,4,?] randomly generated code over GF(2)
    gap> DecreaseMinimumDistanceUpperBound(C,3,4);
    rec( mindist := 2,
      word := [ Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0 ] )
    gap> MinimumDistance(C);
    2
  ------------------------------------------------------------------
  
  4.8-7 MinimumDistanceRandom
  
  > MinimumDistanceRandom( C, num, s ) _______________________________function
  
  MinimumDistanceRandom  returns  an  upper  bound  for  the  minimum distance
  d_random  of  a  linear binary code C, using a probabilistic polynomial time
  algorithm.  Briefly:  Let  C  be  a linear code of dimension k over GF(q) as
  above.  The  algorithm has input parameters num and s, where s is an integer
  between 2 and n-1, and num is an integer greater than or equal to 1.
  
  --    Find a generator matrix G of C.
  
  --    Randomly permute the columns of G, written G_p..
  
  --          G=(A, B)
  
  
        with  A  a  kx  s  matrix. If A is the zero matrix then return `method
        fails'.
  
  --    Search  A  for  at most 5 rows that lead to codewords, in the code C_A
        with generator matrix A, of minimum weight.
  
  --    For  these codewords, use the associated linear combination to compute
        the weight of the whole word in C. Return this weight and codeword.
  
  This  probabilistic  algorithm  is repeated num times (with different random
  permutations  of the rows of G each time) and the weight and codeword of the
  lowest occurring weight is taken.
  
  ---------------------------  Example  ----------------------------
    gap> C:=RandomLinearCode(60,20,GF(2));
    a  [60,20,?] randomly generated code over GF(2)
    gap> #mindist(C);time;
    gap> #mindistleon(C,10,30);time; #doesn't work well
    gap> a:=MinimumDistanceRandom(C,10,30);time; # done 10 times -with fastest time!!
    
     This is a probabilistic algorithm which may return the wrong answer.
    [ 12, [ 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 
            1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 ] ]
    130
    gap> a[2] in C;
    true
    gap> b:=DecreaseMinimumDistanceUpperBound(C,10,1); time; #only done once!
    rec( mindist := 12, word := [ 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 
          Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 
          0*Z(2), Z(2)^0, Z(2)^0, 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2), 
          Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 
          0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 
          0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), 
          0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2) ] )
    649
    gap> Codeword(b!.word) in C;
    true
    gap> MinimumDistance(C);time;
    12
    196
    gap> c:=MinimumDistanceLeon(C);time;
    12
    66
    gap> C:=RandomLinearCode(30,10,GF(3));
    a  [30,10,?] randomly generated code over GF(3)
    gap> a:=MinimumDistanceRandom(C,10,10);time;
    
     This is a probabilistic algorithm which may return the wrong answer.
    [ 13, [ 0 0 0 1 0 0 0 0 0 0 1 0 2 2 1 1 0 2 2 0 1 0 2 1 0 0 0 1 0 2 ] ]
    229
    gap> a[2] in C;
    true
    gap> MinimumDistance(C);time;
    9
    45
    gap> c:=MinimumDistanceLeon(C);
    Code must be binary. Quitting.
    0
    gap> a:=MinimumDistanceRandom(C,1,29);time;
    
     This is a probabilistic algorithm which may return the wrong answer.
    [ 10, [ 0 0 1 0 2 0 2 0 1 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 2 2 2 0 ] ]
    53
  ------------------------------------------------------------------
  
  4.8-8 CoveringRadius
  
  > CoveringRadius( C ) ______________________________________________function
  
  CoveringRadius  returns  the covering radius of a linear code C. This is the
  smallest  number  r  with  the  property  that each element v of the ambient
  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. The smallest covering
  radius  of  any  [n,k] binary linear code is denoted t(n,k). A binary linear
  code with reasonable small covering radius is called a covering code.
  
  If  C  is a perfect code (see IsPerfectCode (4.3-6)), the covering radius is
  equal  to t, the number of errors the code can correct, where d = 2t+1, with
  d the minimum distance of C (see MinimumDistance (4.8-3)).
  
  If  there exists a function called SpecialCoveringRadius in the `operations'
  field of the code, then this function will be called to compute the covering
  radius   of  the  code.  At  the  moment,  no  code-specific  functions  are
  implemented.
  
  If the length of BoundsCoveringRadius (see BoundsCoveringRadius (7.2-1)), is
  1, then the value in
  
  
  C.boundsCoveringRadius
  is returned. Otherwise, the function
  
  
  C.operations.CoveringRadius
  is  executed,  unless  the redundancy of C is too large. In the last case, a
  warning is issued.
  
  The  algorithm  used to compute the covering radius is the following. First,
  CosetLeadersMatFFE  is  used  to  compute  the  list of coset leaders (which
  returns  a  codeword  in  each  coset  of GF(q)^n/C of minimum weight). Then
  WeightVecFFE  is  used to compute the weight of each of these coset leaders.
  The program returns the maximum of these weights.
  
  ---------------------------  Example  ----------------------------
    gap> H := RandomLinearCode(10, 5, GF(2));
    a  [10,5,?] randomly generated code over GF(2)
    gap> CoveringRadius(H);
    3
    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 
    gap> CoveringRadius( BCHCode( 17, 3, GF(2) ) );
    3
    gap> CoveringRadius( HammingCode( 5, GF(2) ) );
    1
    gap> C := ReedMullerCode( 1, 9 );;
    gap> CoveringRadius( C );
    CoveringRadius: warning, the covering radius of
    this code cannot be computed straightforward.
    Try to use IncreaseCoveringRadiusLowerBound( code ).
    (see the manual for more details).
    The covering radius of code lies in the interval:
    [ 240 .. 248 ]
  ------------------------------------------------------------------
  
  See  also  the  GUAVA commands relating to bounds on the minimum distance in
  section 7.2.
  
  4.8-9 SetCoveringRadius
  
  > SetCoveringRadius( C, intlist ) __________________________________function
  
  SetCoveringRadius  enables  the  user  to  set  the covering radius herself,
  instead  of  letting  GUAVA compute it. If intlist is an integer, GUAVA will
  simply  put  it  in  the  `boundsCoveringRadius'  field.  If it is a list of
  integers,    however,    it    will    intersect    this   list   with   the
  `boundsCoveringRadius'  field,  thus  taking the best of both lists. If this
  would  leave  an empty list, the field is set to intlist. Because some other
  computations  use  the covering radius of the code, it is important that the
  entered value is not wrong, otherwise new results may be invalid.
  
  ---------------------------  Example  ----------------------------
    gap> C := BCHCode( 17, 3, GF(2) );;
    gap> BoundsCoveringRadius( C );
    [ 3 .. 4 ]
    gap> SetCoveringRadius( C, [ 2 .. 3 ] );
    gap> BoundsCoveringRadius( C );
    [ [ 2 .. 3 ] ]
  ------------------------------------------------------------------
  
  
  4.9 Distributions
  
  4.9-1 MinimumWeightWords
  
  > MinimumWeightWords( C ) __________________________________________function
  
  MinimumWeightWords returns the list of minimum weight codewords of C.
  
  This  algorithm  is  written  in  GAP is slow, so is only suitable for small
  codes.
  
  This  does  not call the very fast function MinimumWeight (see MinimumWeight
  (4.8-5)).
  
  ---------------------------  Example  ----------------------------
    gap> C:=HammingCode(3,GF(2));
    a linear [7,4,3]1 Hamming (3,2) code over GF(2)
    gap> MinimumWeightWords(C);
    [ [ 1 0 0 0 0 1 1 ], [ 0 1 0 1 0 1 0 ], [ 0 1 0 0 1 0 1 ], [ 1 0 0 1 1 0 0 ], [ 0 0 1 0 1 1 0 ],
      [ 0 0 1 1 0 0 1 ], [ 1 1 1 0 0 0 0 ] ]
    
  ------------------------------------------------------------------
  
  4.9-2 WeightDistribution
  
  > WeightDistribution( C ) __________________________________________function
  
  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   (4.9-3)).   If  w  is  the  weight
  distribution of a linear code C, it must have the zero codeword, so w[1] = 1
  (one word of weight 0).
  
  Some   codes,   such   as   the   Hamming  codes,  have  precomputed  weight
  distributions.  For  others,  the  program  WeightDistribution calls the GAP
  program  DistancesDistributionMatFFEVecFFE,  which is written in C. See also
  CodeWeightEnumerator.
  
  ---------------------------  Example  ----------------------------
    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 ] 
  ------------------------------------------------------------------
  
  4.9-3 InnerDistribution
  
  > InnerDistribution( C ) ___________________________________________function
  
  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 (4.9-2)).
  
  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] <> 0,
  because  a  distance  between  zero  and d never occurs. See MinimumDistance
  (4.8-3).
  
  ---------------------------  Example  ----------------------------
    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 ] 
  ------------------------------------------------------------------
  
  4.9-4 DistancesDistribution
  
  > DistancesDistribution( C, w ) ____________________________________function
  
  DistancesDistribution  returns  the  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] <> 0, is defined as the distance
  to C (see MinimumDistance (4.8-3)).
  
  ---------------------------  Example  ----------------------------
    gap> H := HadamardCode(20);
    a (20,40,10)6..8 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 
  ------------------------------------------------------------------
  
  4.9-5 OuterDistribution
  
  > OuterDistribution( C ) ___________________________________________function
  
  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  pairs,  the  first coordinate being an element of GF(q)^n
  (this  is a codeword type) and the second coordinate being a 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  (4.9-4))  can be used to
  calculate one entry of the list.
  
  ---------------------------  Example  ----------------------------
    gap> C := RepetitionCode( 3, GF(2) );
    a cyclic [3,1,3]1 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 
  ------------------------------------------------------------------
  
  
  4.10 Decoding Functions
  
  4.10-1 Decode
  
  > Decode( C, r ) ___________________________________________________function
  
  Decode  decodes r (a 'received word') with respect to code C and returns the
  `message word' (i.e., the information digits associated to the codeword c in
  C  closest  to  r).  Here  r can be a GUAVA codeword or a list of codewords.
  First,  possible  errors in r are corrected, then the codeword is decoded to
  an  information codeword m (and not an element of C). If the code record has
  a  field  `specialDecoder',  this  special  algorithm  is used to decode the
  vector.  Hamming codes, cyclic codes, and generalized Reed-Solomon have such
  a  special  algorithm.  (The  algorithm  used  for BCH codes is the Sugiyama
  algorithm  described,  for  example,  in  section 5.4.3 of [HP03]. A special
  decoder  has  also being written for the generalized Reed-Solomon code using
  the  interpolation algorithm. For cyclic codes, the error-trapping algorithm
  is  used.)  If  C  is  linear and no special decoder field has been set then
  syndrome  decoding  is  used.  Otherwise (when C is non-linear), the nearest
  neighbor decoding algorithm is used (which is very slow).
  
  A special decoder can be created by defining a function
  
  
  C!.SpecialDecoder := function(C, r) ... end;
  The  function  uses the arguments C (the code record itself) and r (a vector
  of the codeword type) to decode r to an information vector. A normal decoder
  would  take  a  codeword r of the same word length and field as C, and would
  return  an  information  vector 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.
  
  Encoding  is  done  by multiplying the information vector with the code (see
  4.2).
  
  ---------------------------  Example  ----------------------------
    gap> C := HammingCode(3);
    a linear [7,4,3]1 Hamming (3,2) code over GF(2)
    gap> c := "1010"*C;                    # encoding
    [ 1 0 1 1 0 1 0 ]
    gap> Decode(C, c);                     # decoding
    [ 1 0 1 0 ]
    gap> Decode(C, Codeword("0010101"));
    [ 1 1 0 1 ]                            # 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 
  ------------------------------------------------------------------
  
  4.10-2 Decodeword
  
  > Decodeword( C, r ) _______________________________________________function
  
  Decodeword  decodes r (a 'received word') with respect to code C and returns
  the  codeword  c in C closest to r. Here r can be a GUAVA codeword or a list
  of  codewords. If the code record has a field `specialDecoder', this special
  algorithm   is  used  to  decode  the  vector.  Hamming  codes,  generalized
  Reed-Solomon  codes,  and  BCH  codes  have  such  a special algorithm. (The
  algorithm  used  for  BCH  codes  is  the  Sugiyama algorithm described, for
  example,  in  section  5.4.3  of  [HP03]. The algorithm used for generalized
  Reed-Solomon  codes is the ``interpolation algorithm'' described for example
  in  chapter  5  of  [JH04].) If C is linear and no special decoder field has
  been  set  then  syndrome decoding is used. Otherwise, when C is non-linear,
  the  nearest  neighbor  algorithm has been implemented (which should only be
  used for small-sized codes).
  
  ---------------------------  Example  ----------------------------
    gap> C := HammingCode(3);
    a linear [7,4,3]1 Hamming (3,2) code over GF(2)
    gap> c := "1010"*C;                    # encoding
    [ 1 0 1 1 0 1 0 ]
    gap> Decodeword(C, c);                     # decoding
    [ 1 0 1 1 0 1 0 ]
    gap>
    gap> R:=PolynomialRing(GF(11),["t"]);
    GF(11)[t]
    gap> P:=List([1,3,4,5,7],i->Z(11)^i);
    [ Z(11), Z(11)^3, Z(11)^4, Z(11)^5, Z(11)^7 ]
    gap> C:=GeneralizedReedSolomonCode(P,3,R);
    a linear [5,3,1..3]2  generalized Reed-Solomon code over GF(11)
    gap> MinimumDistance(C);
    3
    gap> c:=Random(C);
    [ 0 9 6 2 1 ]
    gap> v:=Codeword("09620");
    [ 0 9 6 2 0 ]
    gap> GeneralizedReedSolomonDecoderGao(C,v);
    [ 0 9 6 2 1 ]
    gap> Decodeword(C,v); # calls the special interpolation decoder
    [ 0 9 6 2 1 ]
    gap> G:=GeneratorMat(C);
    [ [ Z(11)^0, 0*Z(11), 0*Z(11), Z(11)^8, Z(11)^9 ],
      [ 0*Z(11), Z(11)^0, 0*Z(11), Z(11)^0, Z(11)^8 ],
      [ 0*Z(11), 0*Z(11), Z(11)^0, Z(11)^3, Z(11)^8 ] ]
    gap> C1:=GeneratorMatCode(G,GF(11));
    a linear [5,3,1..3]2 code defined by generator matrix over GF(11)
    gap> Decodeword(C,v); # calls syndrome decoding
    [ 0 9 6 2 1 ]
  ------------------------------------------------------------------
  
  4.10-3 GeneralizedReedSolomonDecoderGao
  
  > GeneralizedReedSolomonDecoderGao( C, r ) _________________________function
  
  GeneralizedReedSolomonDecoderGao decodes r (a 'received word') to a codeword
  c  in C in a generalized Reed-Solomon code C (see GeneralizedReedSolomonCode
  (5.6-2)),  closest to r. Here r must be a GUAVA codeword. If the code record
  does  not  have  name  `generalized  Reed-Solomon  code'  then  an  error is
  returned. Otherwise, the Gao decoder [Gao03] is used to compute c.
  
  For  long  codes,  this  method is faster in practice than the interpolation
  method used in Decodeword.
  
  ---------------------------  Example  ----------------------------
    gap> R:=PolynomialRing(GF(11),["t"]);
    GF(11)[t]
    gap> P:=List([1,3,4,5,7],i->Z(11)^i);
    [ Z(11), Z(11)^3, Z(11)^4, Z(11)^5, Z(11)^7 ]
    gap> C:=GeneralizedReedSolomonCode(P,3,R);
    a linear [5,3,1..3]2  generalized Reed-Solomon code over GF(11)
    gap> MinimumDistance(C);
    3
    gap> c:=Random(C);
    [ 0 9 6 2 1 ]
    gap> v:=Codeword("09620");
    [ 0 9 6 2 0 ]
    gap> GeneralizedReedSolomonDecoderGao(C,v); 
    [ 0 9 6 2 1 ]
  ------------------------------------------------------------------
  
  4.10-4 GeneralizedReedSolomonListDecoder
  
  > GeneralizedReedSolomonListDecoder( C, r, tau ) ___________________function
  
  GeneralizedReedSolomonListDecoder  implements Sudans list-decoding algorithm
  (see section 12.1 of [JH04]) for ``low rate'' Reed-Solomon codes. It returns
  the list of all codewords in C which are a distance of at most tau from r (a
  'received  word').  C  must  be  a  generalized  Reed-Solomon  code  C  (see
  GeneralizedReedSolomonCode (5.6-2)) and r must be a GUAVA codeword.
  
  ---------------------------  Example  ----------------------------
    gap> F:=GF(16);
    GF(2^4)
    gap>
    gap> a:=PrimitiveRoot(F);; b:=a^7;; b^4+b^3+1; 
    0*Z(2)
    gap> Pts:=List([0..14],i->b^i);
    [ Z(2)^0, Z(2^4)^7, Z(2^4)^14, Z(2^4)^6, Z(2^4)^13, Z(2^2), Z(2^4)^12, Z(2^4)^4,
      Z(2^4)^11, Z(2^4)^3, Z(2^2)^2, Z(2^4)^2, Z(2^4)^9, Z(2^4), Z(2^4)^8 ]
    gap> x:=X(F);;
    gap> R1:=PolynomialRing(F,[x]);;
    gap> vars:=IndeterminatesOfPolynomialRing(R1);;
    gap> y:=X(F,vars);;
    gap> R2:=PolynomialRing(F,[x,y]);;
    gap> C:=GeneralizedReedSolomonCode(Pts,3,R1); 
    a linear [15,3,1..13]10..12  generalized Reed-Solomon code over GF(16)
    gap> MinimumDistance(C); ## 6 error correcting
    13
    gap> z:=Zero(F);;
    gap> r:=[z,z,z,z,z,z,z,z,b^6,b^2,b^5,b^14,b,b^7,b^11];; 
    gap> r:=Codeword(r);
    [ 0 0 0 0 0 0 0 0 a^12 a^14 a^5 a^8 a^7 a^4 a^2 ]
    gap> cs:=GeneralizedReedSolomonListDecoder(C,r,2); time;
    [ [ 0 a^9 a^3 a^13 a^6 a^10 a^11 a a^12 a^14 a^5 a^8 a^7 a^4 a^2 ],
      [ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ] ]
    250
    gap> c1:=cs[1]; c1 in C;
    [ 0 a^9 a^3 a^13 a^6 a^10 a^11 a a^12 a^14 a^5 a^8 a^7 a^4 a^2 ]
    true
    gap> c2:=cs[2]; c2 in C;
    [ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
    true
    gap> WeightCodeword(c1-r);
    7
    gap> WeightCodeword(c2-r);
    7
  ------------------------------------------------------------------
  
  4.10-5 BitFlipDecoder
  
  > BitFlipDecoder( C, r ) ___________________________________________function
  
  The  iterative  decoding  method BitFlipDecoder must only be applied to LDPC
  codes.  For  more information on LDPC codes, refer to Section 5.8. For these
  codes,  BitFlipDecoder  decodes  very  quickly. (Warning: it can give wildly
  wrong results for arbitrary binary linear codes.) The bit flipping algorithm
  is described for example in Chapter 13 of [JH04].
  
  ---------------------------  Example  ----------------------------
    gap> C:=HammingCode(4,GF(2));
    a linear [15,11,3]1 Hamming (4,2) code over GF(2)
    gap> c:=Random(C);
    [ 0 0 0 1 0 0 1 0 0 1 1 0 1 0 1 ]
    gap> v:=List(c);
    [ 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2),
      Z(2)^0, Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0 ]
    gap> v[1]:=Z(2)+v[1]; # flip 1st bit of c to create an error
    Z(2)^0
    gap> v:=Codeword(v);
    [ 1 0 0 1 0 0 1 0 0 1 1 0 1 0 1 ]
    gap> BitFlipDecoder(C,v);
    [ 0 0 0 1 0 0 1 0 0 1 1 0 1 0 1 ]
    
    
  ------------------------------------------------------------------
  
  4.10-6 NearestNeighborGRSDecodewords
  
  > NearestNeighborGRSDecodewords( C, v, dist ) ______________________function
  
  NearestNeighborGRSDecodewords  finds  all generalized Reed-Solomon codewords
  within  distance  dist  from  v and the associated polynomial, using ``brute
  force''.  Input: v is a received vector (a GUAVA codeword), C is a GRS code,
  dist  >  0  is  the  distance from v to search in C. Output: a list of pairs
  [c,f(x)], where wt(c-v)<= dist-1 and c = (f(x_1),...,f(x_n)).
  
  ---------------------------  Example  ----------------------------
    gap> F:=GF(16);
    GF(2^4)
    gap> a:=PrimitiveRoot(F);; b:=a^7; b^4+b^3+1;
    Z(2^4)^7
    0*Z(2)
    gap> Pts:=List([0..14],i->b^i);
    [ Z(2)^0, Z(2^4)^7, Z(2^4)^14, Z(2^4)^6, Z(2^4)^13, Z(2^2), Z(2^4)^12,
      Z(2^4)^4, Z(2^4)^11, Z(2^4)^3, Z(2^2)^2, Z(2^4)^2, Z(2^4)^9, Z(2^4),
      Z(2^4)^8 ]
    gap> x:=X(F);;
    gap> R1:=PolynomialRing(F,[x]);;
    gap> vars:=IndeterminatesOfPolynomialRing(R1);;
    gap> y:=X(F,vars);;
    gap> R2:=PolynomialRing(F,[x,y]);;
    gap> C:=GeneralizedReedSolomonCode(Pts,3,R1);
    a linear [15,3,1..13]10..12  generalized Reed-Solomon code over GF(16)
    gap> MinimumDistance(C); # 6 error correcting
    13
    gap> z:=Zero(F);
    0*Z(2)
    gap> r:=[z,z,z,z,z,z,z,z,b^6,b^2,b^5,b^14,b,b^7,b^11];; # 7 errors
    gap> r:=Codeword(r);
    [ 0 0 0 0 0 0 0 0 a^12 a^14 a^5 a^8 a^7 a^4 a^2 ]
    gap> cs:=NearestNeighborGRSDecodewords(C,r,7);
    [ [ [ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ], 0*Z(2) ],
      [ [ 0 a^9 a^3 a^13 a^6 a^10 a^11 a a^12 a^14 a^5 a^8 a^7 a^4 a^2 ], x_1+Z(2)^0 ] ]
  ------------------------------------------------------------------
  
  4.10-7 NearestNeighborDecodewords
  
  > NearestNeighborDecodewords( C, v, dist ) _________________________function
  
  NearestNeighborDecodewords  finds  all  codewords  in a linear code C within
  distance  dist  from v, using ``brute force''. Input: v is a received vector
  (a  GUAVA  codeword), C is a linear code, dist > 0 is the distance from v to
  search in C. Output: a list of c in C, where wt(c-v)<= dist-1.
  
  ---------------------------  Example  ----------------------------
    gap> F:=GF(16);
    GF(2^4)
    gap> a:=PrimitiveRoot(F);; b:=a^7; b^4+b^3+1;
    Z(2^4)^7
    0*Z(2)
    gap> Pts:=List([0..14],i->b^i);
    [ Z(2)^0, Z(2^4)^7, Z(2^4)^14, Z(2^4)^6, Z(2^4)^13, Z(2^2), Z(2^4)^12,
      Z(2^4)^4, Z(2^4)^11, Z(2^4)^3, Z(2^2)^2, Z(2^4)^2, Z(2^4)^9, Z(2^4),
      Z(2^4)^8 ]
    gap> x:=X(F);;
    gap> R1:=PolynomialRing(F,[x]);;
    gap> vars:=IndeterminatesOfPolynomialRing(R1);;
    gap> y:=X(F,vars);;
    gap> R2:=PolynomialRing(F,[x,y]);;
    gap> C:=GeneralizedReedSolomonCode(Pts,3,R1);
    a linear [15,3,1..13]10..12  generalized Reed-Solomon code over GF(16)
    gap> MinimumDistance(C);
    13
    gap> z:=Zero(F);
    0*Z(2)
    gap> r:=[z,z,z,z,z,z,z,z,b^6,b^2,b^5,b^14,b,b^7,b^11];;
    gap> r:=Codeword(r);
    [ 0 0 0 0 0 0 0 0 a^12 a^14 a^5 a^8 a^7 a^4 a^2 ]
    gap> cs:=NearestNeighborDecodewords(C,r,7);
    [ [ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ], 
      [ 0 a^9 a^3 a^13 a^6 a^10 a^11 a a^12 a^14 a^5 a^8 a^7 a^4 a^2 ] ]
    
  ------------------------------------------------------------------
  
  4.10-8 Syndrome
  
  > Syndrome( C, v ) _________________________________________________function
  
  Syndrome  returns  the syndrome of word v with respect to a linear code C. v
  is a codeword in the ambient vector space of C. If v 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 (4.10-9)) that is needed to
  correct an error in v.
  
  A  syndrome  is  not  defined for non-linear codes. Syndrome then returns an
  error.
  
  ---------------------------  Example  ----------------------------
    gap> C := HammingCode(4);
    a linear [15,11,3]1 Hamming (4,2) code over GF(2)
    gap> v := CodewordNr( C, 7 );
    [ 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 ]
    gap> Syndrome( C, v );
    [ 0 0 0 0 ]
    gap> Syndrome( C, Codeword( "000000001100111" ) );
    [ 1 1 1 1 ]
    gap> Syndrome( C, Codeword( "000000000000001" ) );
    [ 1 1 1 1 ]    # the same syndrome: both codewords are in the same
                   # coset of C 
  ------------------------------------------------------------------
  
  4.10-9 SyndromeTable
  
  > SyndromeTable( C ) _______________________________________________function
  
  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 v with Syndrome (see
  Syndrome (4.10-8)), the error vector needed to correct v can be found in the
  syndrome  table.  Subtracting  this vector from v yields an element of C. To
  make  the search for the syndrome as fast as possible, the syndrome table is
  sorted according to the syndrome vectors.
  
  ---------------------------  Example  ----------------------------
    gap> H := HammingCode(2);
    a linear [3,1,3]1 Hamming (2,2) code 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 
  ------------------------------------------------------------------
  
  4.10-10 StandardArray
  
  > StandardArray( C ) _______________________________________________function
  
  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=n-k 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 (4.10-8)).
  
  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.
  
  ---------------------------  Example  ----------------------------
    gap> StandardArray(RepetitionCode(3)); 
    [ [ [ 0 0 0 ], [ 1 1 1 ] ], [ [ 0 0 1 ], [ 1 1 0 ] ], 
      [ [ 0 1 0 ], [ 1 0 1 ] ], [ [ 1 0 0 ], [ 0 1 1 ] ] ]
  ------------------------------------------------------------------
  
  4.10-11 PermutationDecode
  
  > PermutationDecode( C, v ) ________________________________________function
  
  PermutationDecode  performs  permutation  decoding when possible and returns
  original vector and prints 'fail' when not possible.
  
  This   uses   AutomorphismGroup   in  the  binary  case,  and  (the  slower)
  PermutationAutomorphismGroup   otherwise,   to   compute   the   permutation
  automorphism  group  P  of C. The algorithm runs through the elements p of P
  checking  if  the  weight of H(p* v) is less than (d-1)/2. If it is then the
  vector  p*  v  is  used  to  decode  v:  assuming C is in standard form then
  c=p^-1Em  is  the decoded word, where m is the information digits part of p*
  v.  If no such p exists then ``fail'' is returned. See, for example, section
  10.2 of Huffman and Pless [HP03] for more details.
  
  ---------------------------  Example  ----------------------------
    gap> C0:=HammingCode(3,GF(2));
    a linear [7,4,3]1 Hamming (3,2) code over GF(2)
    gap> G0:=GeneratorMat(C0);;
    gap> G := List(G0, ShallowCopy);;
    gap> PutStandardForm(G);
    ()
    gap> Display(G);
     1 . . . . 1 1
     . 1 . . 1 . 1
     . . 1 . 1 1 .
     . . . 1 1 1 1
    gap> H0:=CheckMat(C0);;
    gap> Display(H0);
     . . . 1 1 1 1
     . 1 1 . . 1 1
     1 . 1 . 1 . 1
    gap> c0:=Random(C0);
    [ 0 0 0 1 1 1 1 ]
    gap> v01:=c0[1]+Z(2)^2;;
    gap> v1:=List(c0, ShallowCopy);;
    gap> v1[1]:=v01;;
    gap> v1:=Codeword(v1);
    [ 1 0 0 1 1 1 1 ]
    gap> c1:=PermutationDecode(C0,v1);
    [ 0 0 0 1 1 1 1 ]
    gap> c1=c0;
    true
  ------------------------------------------------------------------
  
  4.10-12 PermutationDecodeNC
  
  > PermutationDecodeNC( C, v, P ) ___________________________________function
  
  Same  as  PermutationDecode  except  that  one  may  enter  the  permutation
  automorphism group P in as an argument, saving time. Here P is a subgroup of
  the symmetric group on n letters, where n is the word length of C.