3. Codewords
  
  Let GF(q) denote a finite field with q (a prime power) elements. A code is a
  subset C of some finite-dimensional vector space V over GF(q). The length of
  C  is the dimension of V. Usually, V=GF(q)^n and the length is the number of
  coordinate  entries.  When  C is itself a vector space over GF(q) then it is
  called  a  linear  code  and the dimension of C is its dimension as a vector
  space over GF(q).
  
  In  GUAVA, a `codeword' is a GAP record, with one of its components being an
  element in V. Likewise, a `code' is a GAP record, with one of its components
  being a subset (or subspace with given basis, if C is linear) of V.
  
  ---------------------------  Example  ----------------------------
      gap> C:=RandomLinearCode(20,10,GF(4));
      a  [20,10,?] randomly generated code over GF(4)
      gap> c:=Random(C);
      [ 1 a 0 0 0 1 1 a^2 0 0 a 1 1 1 a 1 1 a a 0 ]
      gap> NamesOfComponents(C);
      [ "LeftActingDomain", "GeneratorsOfLeftOperatorAdditiveGroup", "WordLength",
        "GeneratorMat", "name", "Basis", "NiceFreeLeftModule", "Dimension", 
         "Representative", "ZeroImmutable" ]
      gap> NamesOfComponents(c);
      [ "VectorCodeword", "WordLength", "treatAsPoly" ]
      gap> c!.VectorCodeword;
      [ immutable compressed vector length 20 over GF(4) ] 
      gap> Display(last);
      [ Z(2^2), Z(2^2), Z(2^2), Z(2)^0, Z(2^2), Z(2^2)^2, 0*Z(2), Z(2^2), Z(2^2),
        Z(2)^0, Z(2^2)^2, 0*Z(2), 0*Z(2), Z(2^2), 0*Z(2), 0*Z(2), 0*Z(2), Z(2^2)^2,
        Z(2)^0, 0*Z(2) ]
      gap> C!.Dimension;
      10
  ------------------------------------------------------------------
  
  Mathematically,  a  `codeword'  is  an element of a code C, but in GUAVA the
  Codeword and VectorCodeword commands have implementations which do not check
  if  the  codeword  belongs  to C (i.e., are independent of the code itself).
  They  exist  primarily  to  make  it  easier for the user to construct a the
  associated GAP record. Using these commands, one can enter into a GAP both a
  codeword c (belonging to C) and a received word r (not belonging to C) using
  the  same  command.  The  user  can input codewords in different formats (as
  strings, vectors, and polynomials), and output information is formatted in a
  readable way.
  
  A codeword c in a linear code C arises in practice by an initial encoding of
  a  'block'  message  m,  adding  enough  redundancy  to recover m after c is
  transmitted  via a 'noisy' communication medium. In GUAVA, for linear codes,
  the  map mlongmapsto c is computed using the command c:=m*C and recovering m
  from  c  is obtained by the command InformationWord(C,c). These commands are
  explained more below.
  
  Many  operations  are  available on codewords themselves, although codewords
  also work together with codes (see chapter 4. on Codes).
  
  The  first  section  describes  how  codewords are constructed (see Codeword
  (3.1-1)   and  IsCodeword  (3.1-3)).  Sections  3.2  and  3.3  describe  the
  arithmetic   operations   applicable  to  codewords.  Section  3.4  describe
  functions  that  convert  codewords  back  to  vectors  or  polynomials (see
  VectorCodeword  (3.4-1) and PolyCodeword (3.4-2)). Section ???Functions that
  Change  the Display Form of a Codeword??? describe functions that change the
  way  a  codeword  is  displayed  (see  TreatAsVector (3.5-1) and TreatAsPoly
  (3.5-2)).  Finally, Section 3.6 describes a function to generate a null word
  (see  NullWord  (3.6-1))  and  some  functions  for extracting properties of
  codewords  (see DistanceCodeword (3.6-2), Support (3.6-3) and WeightCodeword
  (3.6-4)).
  
  
  3.1 Construction of Codewords
  
  3.1-1 Codeword
  
  > Codeword( obj[, n][, F] ) ________________________________________function
  
  Codeword returns a codeword or a list of codewords constructed from obj. The
  object  obj  can  be  a vector, a string, a polynomial or a codeword. It may
  also be a list of those (even a mixed list).
  
  If a number n is specified, all constructed codewords have length n. This is
  the  only  way  to  make  sure  that  all  elements  of obj are converted to
  codewords  of  the  same  length. Elements of obj that are longer than n are
  reduced in length by cutting of the last positions. Elements of obj that are
  shorter  than  n  are  lengthened  by  adding  zeros  at the end. If no n is
  specified, each constructed codeword is handled individually.
  
  If  a  Galois  field F is specified, all codewords are constructed over this
  field.  This  is  the  only  way  to  make sure that all elements of obj are
  converted  to  the  same  field F (otherwise they are converted one by one).
  Note  that all elements of obj must have elements over F or over `Integers'.
  Converting  from  one  Galois  field  to  another is not allowed. If no F is
  specified, vectors or strings with integer elements will be converted to the
  smallest Galois field possible.
  
  Note  that  a significant speed increase is achieved if F is specified, even
  when all elements of obj already have elements over F.
  
  Every  vector  in  obj  can be a finite field vector over F or a vector over
  `Integers'.  In  the  last case, it is converted to F or, if omitted, to the
  smallest Galois field possible.
  
  Every  string  in obj must be a string of numbers, without spaces, commas or
  any  other  characters.  These  numbers  must  be from 0 to 9. The string is
  converted to a codeword over F or, if F is omitted, over the smallest Galois
  field possible. Note that since all numbers in the string are interpreted as
  one-digit  numbers,  Galois  fields  of size larger than 10 are not properly
  represented when using strings. In fact, no finite field of size larger than
  11 arises in this fashion at all.
  
  Every  polynomial  in  obj  is  converted  to  a codeword of length n or, if
  omitted,  of  a  length  dictated  by  the degree of the polynomial. If F is
  specified, a polynomial in obj must be over F.
  
  Every  element of obj that is already a codeword is changed to a codeword of
  length  n.  If  no  n  was  specified,  the codeword doesn't change. If F is
  specified, the codeword must have base field F.
  
  ---------------------------  Example  ----------------------------
    gap> c := Codeword([0,1,1,1,0]);
    [ 0 1 1 1 0 ]
    gap> VectorCodeword( c ); 
    [ 0*Z(2), Z(2)^0, Z(2)^0, Z(2)^0, 0*Z(2) ]
    gap> c2 := Codeword([0,1,1,1,0], GF(3));
    [ 0 1 1 1 0 ]
    gap> VectorCodeword( c2 );
    [ 0*Z(3), Z(3)^0, Z(3)^0, Z(3)^0, 0*Z(3) ]
    gap> Codeword([c, c2, "0110"]);
    [ [ 0 1 1 1 0 ], [ 0 1 1 1 0 ], [ 0 1 1 0 ] ]
    gap> p := UnivariatePolynomial(GF(2), [Z(2)^0, 0*Z(2), Z(2)^0]);
    Z(2)^0+x_1^2
    gap> Codeword(p);
    x^2 + 1 
  ------------------------------------------------------------------
  
  This  command  can  also be called using the syntax Codeword(obj,C). In this
  format,  the  elements  of obj are converted to elements of the same ambient
  vector  space  as the elements of a code C. The command Codeword(c,C) is the
  same  as  calling Codeword(c,n,F), where n is the word length of C and the F
  is the ground field of C.
  
  ---------------------------  Example  ----------------------------
    gap> C := WholeSpaceCode(7,GF(5));
    a cyclic [7,7,1]0 whole space code over GF(5)
    gap> Codeword(["0220110", [1,1,1]], C);
    [ [ 0 2 2 0 1 1 0 ], [ 1 1 1 0 0 0 0 ] ]
    gap> Codeword(["0220110", [1,1,1]], 7, GF(5));
    [ [ 0 2 2 0 1 1 0 ], [ 1 1 1 0 0 0 0 ] ] 
    gap> C:=RandomLinearCode(10,5,GF(3));
    a linear [10,5,1..3]3..5 random linear code over GF(3)
    gap> Codeword("1000000000",C);
    [ 1 0 0 0 0 0 0 0 0 0 ]
    gap> Codeword("1000000000",10,GF(3));
    [ 1 0 0 0 0 0 0 0 0 0 ]
  ------------------------------------------------------------------
  
  3.1-2 CodewordNr
  
  > CodewordNr( C, list ) ____________________________________________function
  
  CodewordNr  returns a list of codewords of C. list may be a list of integers
  or a single integer. For each integer of list, the corresponding codeword of
  C  is  returned.  The  correspondence  of  a  number  i  with  a codeword is
  determined  as  follows:  if  a list of elements of C is available, the i^th
  element  is taken. Otherwise, it is calculated by multiplication of the i^th
  information  vector  by  the generator matrix or generator polynomial, where
  the  information  vectors  are ordered lexicographically. In particular, the
  returned  codeword(s) could be a vector or a polynomial. So CodewordNr(C, i)
  is  equal  to AsSSortedList(C)[i], described in the next chapter. The latter
  function  first calculates the set of all the elements of C and then returns
  the  i^th  element  of that set, whereas the former only calculates the i^th
  codeword.
  
  ---------------------------  Example  ----------------------------
    gap> B := BinaryGolayCode();
    a cyclic [23,12,7]3 binary Golay code over GF(2)
    gap> c := CodewordNr(B, 4);
    x^22 + x^20 + x^17 + x^14 + x^13 + x^12 + x^11 + x^10
    gap> R := ReedSolomonCode(2,2);
    a cyclic [2,1,2]1 Reed-Solomon code over GF(3)
    gap> AsSSortedList(R);
    [ [ 0 0 ], [ 1 1 ], [ 2 2 ] ]
    gap> CodewordNr(R, [1,3]);
    [ [ 0 0 ], [ 2 2 ] ]
  ------------------------------------------------------------------
  
  3.1-3 IsCodeword
  
  > IsCodeword( obj ) ________________________________________________function
  
  IsCodeword  returns `true' if obj, which can be an object of arbitrary type,
  is  of  the codeword type and `false' otherwise. The function will signal an
  error if obj is an unbound variable.
  
  ---------------------------  Example  ----------------------------
    gap> IsCodeword(1);
    false
    gap> IsCodeword(ReedMullerCode(2,3));
    false
    gap> IsCodeword("11111");
    false
    gap> IsCodeword(Codeword("11111"));
    true 
  ------------------------------------------------------------------
  
  
  3.2 Comparisons of Codewords
  
  3.2-1 =
  
  > =( c1, c2 ) ______________________________________________________function
  
  The equality operator c1 = c2 evaluates to `true' if the codewords c1 and c2
  are  equal,  and  to `false' otherwise. Note that codewords are equal if and
  only  if  their  base  vectors  are equal. Whether they are represented as a
  vector or polynomial has nothing to do with the comparison.
  
  Comparing codewords with objects of other types is not recommended, although
  it  is  possible.  If  c2  is  the  codeword,  the  other object c1 is first
  converted  to  a  codeword,  after which comparison is possible. This way, a
  codeword  can be compared with a vector, polynomial, or string. If c1 is the
  codeword,  then  problems may arise if c2 is a polynomial. In that case, the
  comparison  always  yields  a  `false', because the polynomial comparison is
  called.
  
  The  equality operator is also denoted EQ, and EQ(c1,c2) is the same as c1 =
  c2. There is also an inequality operator, < >, or not EQ.
  
  ---------------------------  Example  ----------------------------
    gap> P := UnivariatePolynomial(GF(2), Z(2)*[1,0,0,1]);
    Z(2)^0+x_1^3
    gap> c := Codeword(P, GF(2));
    x^3 + 1
    gap> P = c;        # codeword operation
    true
    gap> c2 := Codeword("1001", GF(2));
    [ 1 0 0 1 ]
    gap> c = c2;
    true 
    gap> C:=HammingCode(3);
    a linear [7,4,3]1 Hamming (3,2) code over GF(2)
    gap> c1:=Random(C);
    [ 1 0 0 1 1 0 0 ]
    gap> c2:=Random(C);
    [ 0 1 0 0 1 0 1 ]
    gap> EQ(c1,c2);
    false
    gap> not EQ(c1,c2);
    true
  ------------------------------------------------------------------
  
  
  3.3 Arithmetic Operations for Codewords
  
  3.3-1 +
  
  > +( c1, c2 ) ______________________________________________________function
  
  The  following  operations  are always available for codewords. The operands
  must  have  a  common base field, and must have the same length. No implicit
  conversions are performed.
  
  The operator + evaluates to the sum of the codewords c1 and c2.
  
  ---------------------------  Example  ----------------------------
    gap> C:=RandomLinearCode(10,5,GF(3));
    a linear [10,5,1..3]3..5 random linear code over GF(3)
    gap> c:=Random(C);
    [ 1 0 2 2 2 2 1 0 2 0 ]
    gap> Codeword(c+"2000000000");
    [ 0 0 2 2 2 2 1 0 2 0 ]
    gap> Codeword(c+"1000000000");
  ------------------------------------------------------------------
  
  The  last  command  returns  a  GAP  ERROR  since the `codeword' which GUAVA
  associates to "1000000000" belongs to GF(2) and not GF(3).
  
  3.3-2 -
  
  > -( c1, c2 ) ______________________________________________________function
  
  Similar  to  addition:  the  operator  -  evaluates to the difference of the
  codewords c1 and c2.
  
  3.3-3 +
  
  > +( v, C ) ________________________________________________________function
  
  The  operator  v+C  evaluates  to  the  coset  code of code C after adding a
  `codeword'  v to all codewords in C. Note that if c in C then mathematically
  c+C=C but GUAVA only sees them equal as sets. See CosetCode (6.1-17).
  
  Note that the command C+v returns the same output as the command v+C.
  
  ---------------------------  Example  ----------------------------
    gap> C:=RandomLinearCode(10,5);
    a  [10,5,?] randomly generated code over GF(2)
    gap> c:=Random(C);
    [ 0 0 0 0 0 0 0 0 0 0 ]
    gap> c+C;
    [ add. coset of a  [10,5,?] randomly generated code over GF(2) ]
    gap> c+C=C;
    true
    gap> IsLinearCode(c+C);
    false
    gap> v:=Codeword("100000000");
    [ 1 0 0 0 0 0 0 0 0 ]
    gap> v+C;
    [ add. coset of a  [10,5,?] randomly generated code over GF(2) ]
    gap> C=v+C;
    false
    gap> C := GeneratorMatCode( [ [1, 0,0,0], [0, 1,0,0] ], GF(2) );
    a linear [4,2,1]1 code defined by generator matrix over GF(2)
    gap> Elements(C);
    [ [ 0 0 0 0 ], [ 0 1 0 0 ], [ 1 0 0 0 ], [ 1 1 0 0 ] ]
    gap> v:=Codeword("0011");
    [ 0 0 1 1 ]
    gap> C+v;
    [ add. coset of a linear [4,2,4]1 code defined by generator matrix over GF(2) ]
    gap> Elements(C+v);
    [ [ 0 0 1 1 ], [ 0 1 1 1 ], [ 1 0 1 1 ], [ 1 1 1 1 ] ]
  ------------------------------------------------------------------
  
  In general, the operations just described can also be performed on codewords
  expressed   as  vectors,  strings  or  polynomials,  although  this  is  not
  recommended.  The  vector,  string  or  polynomial  is  first converted to a
  codeword,  after  which  the  normal  operation is performed. For this to go
  right,  make  sure  that at least one of the operands is a codeword. Further
  more, it will not work when the right operand is a polynomial. In that case,
  the  polynomial operations (FiniteFieldPolynomialOps) are called, instead of
  the codeword operations (CodewordOps).
  
  Some other code-oriented operations with codewords are described in 4.2.
  
  
  3.4 Functions that Convert Codewords to Vectors or Polynomials
  
  3.4-1 VectorCodeword
  
  > VectorCodeword( obj ) ____________________________________________function
  
  Here  obj  can be a code word or a list of code words. This function returns
  the corresponding vectors over a finite field.
  
  ---------------------------  Example  ----------------------------
    gap> a := Codeword("011011");; 
    gap> VectorCodeword(a);
    [ 0*Z(2), Z(2)^0, Z(2)^0, 0*Z(2), Z(2)^0, Z(2)^0 ]
  ------------------------------------------------------------------
  
  3.4-2 PolyCodeword
  
  > PolyCodeword( obj ) ______________________________________________function
  
  PolyCodeword  returns  a  polynomial  or a list of polynomials over a Galois
  field,  converted  from  obj. The object obj can be a codeword, or a list of
  codewords.
  
  ---------------------------  Example  ----------------------------
    gap> a := Codeword("011011");; 
    gap> PolyCodeword(a);
    x_1+x_1^2+x_1^4+x_1^5
  ------------------------------------------------------------------
  
  
  3.5 Functions that Change the Display Form of a Codeword
  
  3.5-1 TreatAsVector
  
  > TreatAsVector( obj ) _____________________________________________function
  
  TreatAsVector  adapts  the codewords in obj to make sure they are printed as
  vectors.  obj may be a codeword or a list of codewords. Elements of obj that
  are  not codewords are ignored. After this function is called, the codewords
  will  be  treated as vectors. The vector representation is obtained by using
  the coefficient list of the polynomial.
  
  Note  that  this  only  changes the way a codeword is printed. TreatAsVector
  returns  nothing,  it  is  called  only  for  its  side effect. The function
  VectorCodeword converts codewords to vectors (see VectorCodeword (3.4-1)).
  
  ---------------------------  Example  ----------------------------
    gap> B := BinaryGolayCode();
    a cyclic [23,12,7]3 binary Golay code over GF(2)
    gap> c := CodewordNr(B, 4);
    x^22 + x^20 + x^17 + x^14 + x^13 + x^12 + x^11 + x^10
    gap> TreatAsVector(c);
    gap> c;
    [ 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0 1 0 1 ] 
  ------------------------------------------------------------------
  
  3.5-2 TreatAsPoly
  
  > TreatAsPoly( obj ) _______________________________________________function
  
  TreatAsPoly  adapts  the  codewords  in obj to make sure they are printed as
  polynomials.  obj  may be a codeword or a list of codewords. Elements of obj
  that  are  not  codewords  are  ignored.  After this function is called, the
  codewords  will  be  treated  as  polynomials.  The finite field vector that
  defines  the  codeword  is  used  as  a  coefficient  list of the polynomial
  representation,  where the first element of the vector is the coefficient of
  degree zero, the second element is the coefficient of degree one, etc, until
  the last element, which is the coefficient of highest degree.
  
  Note  that  this  only  changes  the  way a codeword is printed. TreatAsPoly
  returns  nothing,  it  is  called  only  for  its  side effect. The function
  PolyCodeword converts codewords to polynomials (see PolyCodeword (3.4-2)).
  
  ---------------------------  Example  ----------------------------
    gap> a := Codeword("00001",GF(2));
    [ 0 0 0 0 1 ]
    gap> TreatAsPoly(a); a;
    x^4
    gap> b := NullWord(6,GF(4));
    [ 0 0 0 0 0 0 ]
    gap> TreatAsPoly(b); b;
    0 
  ------------------------------------------------------------------
  
  
  3.6 Other Codeword Functions
  
  3.6-1 NullWord
  
  > NullWord( n, F ) _________________________________________________function
  
  Other  uses:  NullWord(  n  )  (default F=GF(2)) and NullWord( C ). NullWord
  returns a codeword of length n over the field F of only zeros. The integer n
  must  be  greater  then  zero.  If only a code C is specified, NullWord will
  return a null word with both the word length and the Galois field of C.
  
  ---------------------------  Example  ----------------------------
    gap> NullWord(8);
    [ 0 0 0 0 0 0 0 0 ]
    gap> Codeword("0000") = NullWord(4);
    true
    gap> NullWord(5,GF(16));
    [ 0 0 0 0 0 ]
    gap> NullWord(ExtendedTernaryGolayCode());
    [ 0 0 0 0 0 0 0 0 0 0 0 0 ] 
  ------------------------------------------------------------------
  
  3.6-2 DistanceCodeword
  
  > DistanceCodeword( c1, c2 ) _______________________________________function
  
  DistanceCodeword  returns the Hamming distance from c1 to c2. Both variables
  must  be  codewords  with  equal word length over the same Galois field. The
  Hamming  distance  between  two  words is the number of places in which they
  differ. As a result, DistanceCodeword always returns an integer between zero
  and the word length of the codewords.
  
  ---------------------------  Example  ----------------------------
    gap> a := Codeword([0, 1, 2, 0, 1, 2]);; b := NullWord(6, GF(3));;
    gap> DistanceCodeword(a, b);
    4
    gap> DistanceCodeword(b, a);
    4
    gap> DistanceCodeword(a, a);
    0 
  ------------------------------------------------------------------
  
  3.6-3 Support
  
  > Support( c ) _____________________________________________________function
  
  Support  returns  a set of integers indicating the positions of the non-zero
  entries in a codeword c.
  
  ---------------------------  Example  ----------------------------
    gap> a := Codeword("012320023002");; Support(a);
    [ 2, 3, 4, 5, 8, 9, 12 ]
    gap> Support(NullWord(7));
    [  ] 
  ------------------------------------------------------------------
  
  The  support  of a list with codewords can be calculated by taking the union
  of  the  individual supports. The weight of the support is the length of the
  set.
  
  ---------------------------  Example  ----------------------------
    gap> L := Codeword(["000000", "101010", "222000"], GF(3));;
    gap> S := Union(List(L, i -> Support(i)));
    [ 1, 2, 3, 5 ]
    gap> Length(S);
    4 
  ------------------------------------------------------------------
  
  3.6-4 WeightCodeword
  
  > WeightCodeword( c ) ______________________________________________function
  
  WeightCodeword  returns  the  weight of a codeword c, the number of non-zero
  entries  in c. As a result, WeightCodeword always returns an integer between
  zero and the word length of the codeword.
  
  ---------------------------  Example  ----------------------------
    gap> WeightCodeword(Codeword("22222"));
    5
    gap> WeightCodeword(NullWord(3));
    0
    gap> C := HammingCode(3);
    a linear [7,4,3]1 Hamming (3,2) code over GF(2)
    gap> Minimum(List(AsSSortedList(C){[2..Size(C)]}, WeightCodeword ) );
    3 
  ------------------------------------------------------------------