  
  [1X4 [33X[0;0YCodes[133X[101X
  
  [33X[0;0YA  [13Xcode[113X  is  a  set  of  codewords  (recall  a codeword in [5XGUAVA[105X is simply a
  sequence  of elements of a finite field [22XGF(q)[122X, where [22Xq[122X is a prime power). We
  call  these  the  [13Xelements[113X  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 [14X3.0[114X.[133X
  
  [33X[0;0YIn  [5XGUAVA[105X, codes can be a set specified by its elements (this will be called
  an [13Xunrestricted code[113X), by a generator matrix listing a set of basis elements
  (for a linear code) or by a generator polynomial (for a cyclic code).[133X
  
  [33X[0;0YAny  code can be defined by its elements. If you like, you can give the code
  a name.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XC := ElementsCode(["1100", "1010", "0001"], "example code", GF(2) );[127X[104X
    [4X[28Xa (4,3,1..4)2..4 example code over GF(2)[128X[104X
  [4X[32X[104X
  
  [33X[0;0YAn [22X(n,M,d)[122X code is a code with word [13Xlength[113X [22Xn[122X, [13Xsize[113X [22XM[122X and [13Xminimum distance[113X [22Xd[122X.
  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[133X
  
  a (4,3,1..4)2..4 code over GF(2)
  
  [33X[0;0Ymeans  a  binary  unrestricted  code  of  length  [22X4[122X, with [22X3[122X elements and the
  minimum  distance  is greater than or equal to [22X1[122X and less than or equal to [22X4[122X
  and the covering radius is greater than or equal to [22X2[122X and less than or equal
  to [22X4[122X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XC := ElementsCode(["1100", "1010", "0001"], "example code", GF(2) );[127X[104X
    [4X[28Xa (4,3,1..4)2..4 example code over GF(2)[128X[104X
    [4X[25Xgap>[125X [27XMinimumDistance(C);[127X[104X
    [4X[28X2[128X[104X
    [4X[25Xgap>[125X [27XC;[127X[104X
    [4X[28Xa (4,3,2)2..4 example code over GF(2)[128X[104X
  [4X[32X[104X
  
  [33X[0;0YIf  the  set of elements is a linear subspace of [22XGF(q)^n[122X, the code is called
  [13Xlinear[113X.  If  a  code is linear, it can be defined by its [13Xgenerator matrix[113X or
  [13Xparity  check  matrix[113X.  By definition, the rows of the generator matrix is a
  basis  for  the code (as a vector space over [22XGF(q)[122X). By definition, the rows
  of the parity check matrix is a basis for the dual space of the code,[133X
  
  
  [24X[33X[0;6YC^* = \{ v \in GF(q)^n\ |\ v\cdot c = 0,\ for \ all\ c \in C \}.[133X
  
  [124X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XG := GeneratorMatCode([[1,0,1],[0,1,2]], "demo code", GF(3) );[127X[104X
    [4X[28Xa linear [3,2,1..2]1 demo code over GF(3)[128X[104X
  [4X[32X[104X
  
  [33X[0;0YSo  a  linear  [22X[n,  k,  d]r[122X  code is a code with word [13Xlength[113X [22Xn[122X, [13Xdimension[113X [22Xk[122X,
  [13Xminimum distance[113X [22Xd[122X and [13Xcovering radius[113X [22Xr[122X.[133X
  
  [33X[0;0YIf  the  code  is linear and all cyclic shifts of its codewords (regarded as
  [22Xn[122X-tuples)  are again codewords, the code is called [13Xcyclic[113X. All elements of a
  cyclic  code  are  multiples of the monic polynomial modulo a polynomial [22Xx^n
  -1[122X,  where  [22Xn[122X  is the word length of the code. Such a polynomial is called a
  [13Xgenerator  polynomial[113X  The  generator  polynomial  must divide [22Xx^n-1[122X and its
  quotient  is  called  a [13Xcheck polynomial[113X. Multiplying a codeword in a cyclic
  code  by the check polynomial yields zero (modulo the polynomial [22Xx^n -1[122X). In
  [5XGUAVA[105X,  a  cyclic  code can be defined by either its generator polynomial or
  check polynomial.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XG := GeneratorPolCode(Indeterminate(GF(2))+Z(2)^0, 7, GF(2) );[127X[104X
    [4X[28Xa cyclic [7,6,1..2]1 code defined by generator polynomial over GF(2)[128X[104X
  [4X[32X[104X
  
  [33X[0;0YIt is possible that [5XGUAVA[105X 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 [10XElementsCode[110X (see [2XElementsCode[102X ([14X5.1-1[114X)).
  By calling the function [10XIsLinearCode[110X (see [2XIsLinearCode[102X ([14X4.3-4[114X)), [5XGUAVA[105X tests
  if the code can be represented by a generator matrix. If so, the code record
  and the operations are converted accordingly.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XL := Z(2)*[ [0,0,0], [1,0,0], [0,1,1], [1,1,1] ];;[127X[104X
    [4X[25Xgap>[125X [27XC := ElementsCode( L, GF(2) );[127X[104X
    [4X[28Xa (3,4,1..3)1 user defined unrestricted code over GF(2)[128X[104X
    [4X[28X[128X[104X
    [4X[28X# so far, GUAVA does not know what kind of code this is[128X[104X
    [4X[25Xgap>[125X [27XIsLinearCode( C );[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XC;[127X[104X
    [4X[28Xa linear [3,2,1]1 user defined unrestricted code over GF(2)[128X[104X
  [4X[32X[104X
  
  [33X[0;0YOf  course the same holds for unrestricted codes that in fact are cyclic, or
  codes, defined by a generator matrix, that actually are cyclic.[133X
  
  [33X[0;0YCodes  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
  [10XDisplay[110X  gives a more detailed description, showing the construction history
  of the code.[133X
  
  [33X[0;0Y[5XGUAVA[105X  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  [10XDecode[110X  or  [10XDecodeword[110X.  For  more information about encoding and
  decoding, see sections [14X4.2[114X and [14X4.10-1[114X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XR := ReedMullerCode( 1, 3 );[127X[104X
    [4X[28Xa linear [8,4,4]2 Reed-Muller (1,3) code over GF(2)[128X[104X
    [4X[25Xgap>[125X [27Xw := [ 1, 0, 1, 1 ] * R;[127X[104X
    [4X[28X[ 1 0 0 1 1 0 0 1 ][128X[104X
    [4X[25Xgap>[125X [27XDecode( R, w );[127X[104X
    [4X[28X[ 1 0 1 1 ][128X[104X
    [4X[25Xgap>[125X [27XDecode( R, w + "10000000" ); # One error at the first position. Corrected by Guava.[127X[104X
    [4X[28X[ 1 0 1 1 ][128X[104X
  [4X[32X[104X
  
  [33X[0;0YSections  [14X4.1[114X  and [14X4.2[114X describe the operations that are available for codes.
  Section  [14X4.3[114X  describe  the functions that tests whether an object is a code
  and  what  kind  of  code  it  is  (see  [10XIsCode[110X,  [2XIsLinearCode[102X  ([14X4.3-4[114X)  and
  [10XIsCyclicCode[110X)  and  various  other  boolean functions for codes. Section [14X4.4[114X
  describe   functions   about  equivalence  and  isomorphism  of  codes  (see
  [2XIsEquivalent[102X   ([14X4.4-1[114X),   [2XCodeIsomorphism[102X   ([14X4.4-2[114X)   and  [2XAutomorphismGroup[102X
  ([14X4.4-3[114X)).  Section [14X4.5[114X describes functions that work on [13Xdomains[113X (see Chapter
  "Domains  and  their  Elements"  in  the  GAP Reference Manual). Section [14X4.6[114X
  describes functions for printing and displaying codes. Section [14X4.7[114X describes
  functions  that  return the matrices and polynomials that define a code (see
  [2XGeneratorMat[102X  ([14X4.7-1[114X),  [2XCheckMat[102X  ([14X4.7-2[114X),  [2XGeneratorPol[102X  ([14X4.7-3[114X),  [2XCheckPol[102X
  ([14X4.7-4[114X),  [2XRootsOfCode[102X  ([14X4.7-5[114X)). Section [14X4.8[114X describes functions that return
  the  basic  parameters  of codes (see [2XWordLength[102X ([14X4.8-1[114X), [2XRedundancy[102X ([14X4.8-2[114X)
  and  [2XMinimumDistance[102X  ([14X4.8-3[114X)).  Section [14X4.9[114X describes functions that return
  distance   and   weight   distributions   (see  [2XWeightDistribution[102X  ([14X4.9-2[114X),
  [2XInnerDistribution[102X      ([14X4.9-3[114X),      [2XOuterDistribution[102X      ([14X4.9-5[114X)      and
  [2XDistancesDistribution[102X  ([14X4.9-4[114X)).  Section  [14X4.10[114X describes functions that are
  related  to  decoding  (see  [2XDecode[102X  ([14X4.10-1[114X), [2XDecodeword[102X ([14X4.10-2[114X), [2XSyndrome[102X
  ([14X4.10-8[114X),  [2XSyndromeTable[102X  ([14X4.10-9[114X) and [2XStandardArray[102X ([14X4.10-10[114X)). In Chapters
  [14X5.0[114X and [14X6.0[114X which follow, we describe functions that generate and manipulate
  codes.[133X
  
  
  [1X4.1 [33X[0;0YComparisons of Codes[133X[101X
  
  [1X4.1-1 \=[101X
  
  [33X[1;0Y[29X[2X\=[102X( [3XC1[103X, [3XC2[103X ) [32X method[133X
  
  [33X[0;0YThe equality operator [10XC1 = C2[110X evaluates to `true' if the codes [3XC1[103X and [3XC2[103X are
  equal, and to `false' otherwise.[133X
  
  [33X[0;0YThe  equality operator is also denoted [10XEQ[110X, and [10XEq(C1,C2)[110X is the same as [10XC1 =
  C2[110X. There is also an inequality operator, < >, or [10Xnot EQ[110X.[133X
  
  [33X[0;0YNote  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.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XM := [ [0, 0], [1, 0], [0, 1], [1, 1] ];;[127X[104X
    [4X[25Xgap>[125X [27XC1 := ElementsCode( M, GF(2) );[127X[104X
    [4X[28Xa (2,4,1..2)0 user defined unrestricted code over GF(2)[128X[104X
    [4X[25Xgap>[125X [27XM = C1;[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27XC2 := GeneratorMatCode( [ [1, 0], [0, 1] ], GF(2) );[127X[104X
    [4X[28Xa linear [2,2,1]0 code defined by generator matrix over GF(2)[128X[104X
    [4X[25Xgap>[125X [27XC1 = C2;[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XReedMullerCode( 1, 3 ) = HadamardCode( 8 );[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XWholeSpaceCode( 5, GF(4) ) = WholeSpaceCode( 5, GF(2) );[127X[104X
    [4X[28Xfalse[128X[104X
  [4X[32X[104X
  
  [33X[0;0YAnother  way  of  comparing codes is [10XIsEquivalent[110X, which checks if two codes
  are   equivalent  (see  [2XIsEquivalent[102X  ([14X4.4-1[114X)).  By  the  way,  this  called
  [10XCodeIsomorphism[110X.  For  the current version of [5XGUAVA[105X, 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).[133X
  
  
  [1X4.2 [33X[0;0YOperations for Codes[133X[101X
  
  [1X4.2-1 \+[101X
  
  [33X[1;0Y[29X[2X\+[102X( [3XC1[103X, [3XC2[103X ) [32X method[133X
  
  [33X[0;0YThe  operator  `+'  evaluates  to the direct sum of the codes [3XC1[103X and [3XC2[103X. See
  [2XDirectSumCode[102X ([14X6.2-1[114X).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XC1:=RandomLinearCode(10,5);[127X[104X
    [4X[28Xa  [10,5,?] randomly generated code over GF(2)[128X[104X
    [4X[25Xgap>[125X [27XC2:=RandomLinearCode(9,4);[127X[104X
    [4X[28Xa  [9,4,?] randomly generated code over GF(2)[128X[104X
    [4X[25Xgap>[125X [27XC1+C2;[127X[104X
    [4X[28Xa linear [19,9,1..2]4..9 direct sum code[128X[104X
  [4X[32X[104X
  
  [1X4.2-2 \*[101X
  
  [33X[1;0Y[29X[2X\*[102X( [3XC1[103X, [3XC2[103X ) [32X method[133X
  
  [33X[0;0YThe operator `*' evaluates to the direct product of the codes [3XC1[103X and [3XC2[103X. See
  [2XDirectProductCode[102X ([14X6.2-3[114X).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XC1 := GeneratorMatCode( [ [1, 0,0,0], [0, 1,0,0] ], GF(2) );[127X[104X
    [4X[28Xa linear [4,2,1]1..2 code defined by generator matrix over GF(2)[128X[104X
    [4X[25Xgap>[125X [27XC2 := GeneratorMatCode( [ [0,0,1, 1], [0,0,0, 1] ], GF(2) );[127X[104X
    [4X[28Xa linear [4,2,1]1..2 code defined by generator matrix over GF(2)[128X[104X
    [4X[25Xgap>[125X [27XC1*C2;[127X[104X
    [4X[28Xa linear [16,4,1]4..12 direct product code[128X[104X
  [4X[32X[104X
  
  [1X4.2-3 \*[101X
  
  [33X[1;0Y[29X[2X\*[102X( [3Xm[103X, [3XC[103X ) [32X method[133X
  
  [33X[0;0YThe operator [10Xm*C[110X evaluates to the element of [3XC[103X belonging to information word
  ('message')  [3Xm[103X.  Here [3Xm[103X may be a vector, polynomial, string or codeword or a
  list  of  those.  This is the way to do encoding in [5XGUAVA[105X. [3XC[103X must be linear,
  because  in  [5XGUAVA[105X,  encoding  by  multiplication is only defined for linear
  codes. If [3XC[103X is a cyclic code, this multiplication is the same as multiplying
  an  information  polynomial  [3Xm[103X  by  the generator polynomial of [3XC[103X. If [3XC[103X is a
  linear code, it is equal to the multiplication of an information vector [3Xm[103X by
  a generator matrix of [3XC[103X.[133X
  
  [33X[0;0YTo  invert  this,  use  the  function  [10XInformationWord[110X  (see [2XInformationWord[102X
  ([14X4.2-4[114X), which simply calls the function [10XDecode[110X).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XC := GeneratorMatCode( [ [1, 0,0,0], [0, 1,0,0] ], GF(2) );[127X[104X
    [4X[28Xa linear [4,2,1]1..2 code defined by generator matrix over GF(2)[128X[104X
    [4X[25Xgap>[125X [27Xm:=Codeword("11");[127X[104X
    [4X[28X[ 1 1 ][128X[104X
    [4X[25Xgap>[125X [27Xm*C;[127X[104X
    [4X[28X[ 1 1 0 0 ][128X[104X
  [4X[32X[104X
  
  [1X4.2-4 InformationWord[101X
  
  [33X[1;0Y[29X[2XInformationWord[102X( [3XC[103X, [3Xc[103X ) [32X function[133X
  
  [33X[0;0YHere  [3XC[103X  is  a  linear  code  and  [3Xc[103X  is  a  codeword  in  it.  The  command
  [10XInformationWord[110X  returns  the  message  word  (or  'information  digits')  [22Xm[122X
  satisfying [10Xc=m*C[110X. This command simply calls [10XDecode[110X, provided [10Xc in C[110X is true.
  Otherwise, it returns an error.[133X
  
  [33X[0;0YTo invert this, use the encoding function [10X*[110X (see [2X\*[102X ([14X4.2-3[114X)).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XC:=HammingCode(3);[127X[104X
    [4X[28Xa linear [7,4,3]1 Hamming (3,2) code over GF(2)[128X[104X
    [4X[25Xgap>[125X [27Xc:=Random(C);[127X[104X
    [4X[28X[ 0 0 0 1 1 1 1 ][128X[104X
    [4X[25Xgap>[125X [27XInformationWord(C,c);[127X[104X
    [4X[28X[ 0 1 1 1 ][128X[104X
    [4X[25Xgap>[125X [27Xc:=Codeword("1111100");[127X[104X
    [4X[28X[ 1 1 1 1 1 0 0 ][128X[104X
    [4X[25Xgap>[125X [27XInformationWord(C,c);[127X[104X
    [4X[28XError, ERROR: codeword must belong to code[128X[104X
    [4X[25Xgap>[125X [27XC:=NordstromRobinsonCode();[127X[104X
    [4X[28Xa (16,256,6)4 Nordstrom-Robinson code over GF(2)[128X[104X
    [4X[25Xgap>[125X [27Xc:=Random(C);[127X[104X
    [4X[28X[ 0 0 0 1 0 0 0 1 0 0 1 0 1 1 0 1 ][128X[104X
    [4X[25Xgap>[125X [27XInformationWord(C,c);[127X[104X
    [4X[28X"ERROR: code must be linear"[128X[104X
  [4X[32X[104X
  
  
  [1X4.3 [33X[0;0YBoolean Functions for Codes[133X[101X
  
  [1X4.3-1 in[101X
  
  [33X[1;0Y[29X[2Xin[102X( [3Xc[103X, [3XC[103X ) [32X function[133X
  
  [33X[0;0YThe command [10Xc in C[110X evaluates to `true' if [3XC[103X contains the codeword or list of
  codewords specified by [3Xc[103X. Of course, [3Xc[103X and [3XC[103X must have the same word lengths
  and base fields.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XC:= HammingCode( 2 );; eC:= AsSSortedList( C );[127X[104X
    [4X[28X[ [ 0 0 0 ], [ 1 1 1 ] ][128X[104X
    [4X[25Xgap>[125X [27XeC[2] in C;[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27X[ 0 ] in C;[127X[104X
    [4X[28Xfalse[128X[104X
  [4X[32X[104X
  
  [1X4.3-2 IsSubset[101X
  
  [33X[1;0Y[29X[2XIsSubset[102X( [3XC1[103X, [3XC2[103X ) [32X function[133X
  
  [33X[0;0YThe command [10XIsSubset(C1,C2)[110X returns `true' if [3XC2[103X is a subcode of [3XC1[103X, i.e. if
  [3XC1[103X contains all the elements of [3XC2[103X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XIsSubset( HammingCode(3), RepetitionCode( 7 ) );[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsSubset( RepetitionCode( 7 ), HammingCode( 3 ) );[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27XIsSubset( WholeSpaceCode( 7 ), HammingCode( 3 ) );[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [1X4.3-3 IsCode[101X
  
  [33X[1;0Y[29X[2XIsCode[102X( [3Xobj[103X ) [32X function[133X
  
  [33X[0;0Y[10XIsCode[110X returns `true' if [3Xobj[103X, which can be an object of arbitrary type, is a
  code  and  `false'  otherwise.  Will  cause  an  error  if [3Xobj[103X is an unbound
  variable.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XIsCode( 1 );[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27XIsCode( ReedMullerCode( 2,3 ) );[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [1X4.3-4 IsLinearCode[101X
  
  [33X[1;0Y[29X[2XIsLinearCode[102X( [3Xobj[103X ) [32X function[133X
  
  [33X[0;0Y[10XIsLinearCode[110X checks if object [3Xobj[103X (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 [22XG[122X of
  the  elements  of [3Xobj[103X exists that generates the elements of [3Xobj[103X. If so, [22XG[122X is
  recorded  as  a  generator matrix of [3Xobj[103X and the function returns `true'. If
  not, the function returns `false'.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XC := ElementsCode( [ [0,0,0],[1,1,1] ], GF(2) );[127X[104X
    [4X[28Xa (3,2,1..3)1 user defined unrestricted code over GF(2)[128X[104X
    [4X[25Xgap>[125X [27XIsLinearCode( C );[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsLinearCode( ElementsCode( [ [1,1,1] ], GF(2) ) );[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27XIsLinearCode( 1 );[127X[104X
    [4X[28Xfalse[128X[104X
  [4X[32X[104X
  
  [1X4.3-5 IsCyclicCode[101X
  
  [33X[1;0Y[29X[2XIsCyclicCode[102X( [3Xobj[103X ) [32X function[133X
  
  [33X[0;0Y[10XIsCyclicCode[110X  checks  if  the  object  [3Xobj[103X  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 [22Xg[122X exists that generates the
  elements  of  [3Xobj[103X. If so, [22Xg[122X is recorded as a generator polynomial of [3Xobj[103X and
  the function returns `true'. If not, the function returns `false'.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XC := ElementsCode( [ [0,0,0], [1,1,1] ], GF(2) );[127X[104X
    [4X[28Xa (3,2,1..3)1 user defined unrestricted code over GF(2)[128X[104X
    [4X[25Xgap>[125X [27X# GUAVA does not know the code is cyclic[127X[104X
    [4X[25Xgap>[125X [27XIsCyclicCode( C );      # this command tells GUAVA to find out[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsCyclicCode( HammingCode( 4, GF(2) ) );[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27XIsCyclicCode( 1 );[127X[104X
    [4X[28Xfalse[128X[104X
  [4X[32X[104X
  
  [1X4.3-6 IsPerfectCode[101X
  
  [33X[1;0Y[29X[2XIsPerfectCode[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XIsPerfectCode(C)[110X  returns `true' if [3XC[103X is a perfect code. If [22XC⊂ GF(q)^n[122X then,
  by  definition,  this  means  that  for  some  positive integer [22Xt[122X, the space
  [22XGF(q)^n[122X is covered by non-overlapping spheres of (Hamming) radius [22Xt[122X centered
  at  the  codewords in [3XC[103X. For a code with odd minimum distance [22Xd = 2t+1[122X, this
  is  the case when every word of the vector space of [3XC[103X is at distance at most
  [22Xt[122X  from exactly one element of [3XC[103X. Codes with even minimum distance are never
  perfect.[133X
  
  [33X[0;0YIn 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]).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XH := HammingCode(2);[127X[104X
    [4X[28Xa linear [3,1,3]1 Hamming (2,2) code over GF(2)[128X[104X
    [4X[25Xgap>[125X [27XIsPerfectCode( H );[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsPerfectCode( ElementsCode([[1,1,0],[0,0,1]],GF(2)) );[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsPerfectCode( ReedSolomonCode( 6, 3 ) );[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27XIsPerfectCode( BinaryGolayCode() );[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [1X4.3-7 IsMDSCode[101X
  
  [33X[1;0Y[29X[2XIsMDSCode[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XIsMDSCode(C)[110X returns true if [3XC[103X is a maximum distance separable (MDS) code. A
  linear  [22X[n, k, d][122X-code of length [22Xn[122X, dimension [22Xk[122X and minimum distance [22Xd[122X is an
  MDS  code  if  [22Xk=n-d+1[122X,  in  other words if [3XC[103X meets the Singleton bound (see
  [2XUpperBoundSingleton[102X  ([14X7.1-1[114X)).  An unrestricted [22X(n, M, d)[122X code is called [13XMDS[113X
  if  [22Xk=n-d+1[122X,  with  [22Xk[122X equal to the largest integer less than or equal to the
  logarithm of [22XM[122X with base [22Xq[122X, the size of the base field of [3XC[103X.[133X
  
  [33X[0;0YWell-known  MDS  codes  include the repetition codes, the whole space codes,
  the  even  weight  codes  (these  are  the  only  [13Xbinary[113X  MDS codes) and the
  Reed-Solomon codes.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XC1 := ReedSolomonCode( 6, 3 );[127X[104X
    [4X[28Xa cyclic [6,4,3]2 Reed-Solomon code over GF(7)[128X[104X
    [4X[25Xgap>[125X [27XIsMDSCode( C1 );  # verify it is an MDS code, as 6-3+1 = 4[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsMDSCode( QRCode( 23, GF(2) ) );[127X[104X
    [4X[28Xfalse[128X[104X
  [4X[32X[104X
  
  [1X4.3-8 IsSelfDualCode[101X
  
  [33X[1;0Y[29X[2XIsSelfDualCode[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XIsSelfDualCode(C)[110X  returns `true' if [3XC[103X is self-dual, i.e. when [3XC[103X is equal to
  its  dual  code  (see  also  [2XDualCode[102X  ([14X6.1-14[114X)).  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 [2XIsSelfOrthogonalCode[102X
  ([14X4.3-9[114X)).[133X
  
  [33X[0;0YIf  [3XC[103X  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 [22Xk[122X is equal to the redundancy [22Xr[122X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XIsSelfDualCode( ExtendedBinaryGolayCode() );[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XC := ReedMullerCode( 1, 3 );[127X[104X
    [4X[28Xa linear [8,4,4]2 Reed-Muller (1,3) code over GF(2)[128X[104X
    [4X[25Xgap>[125X [27XDualCode( C ) = C;[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [1X4.3-9 IsSelfOrthogonalCode[101X
  
  [33X[1;0Y[29X[2XIsSelfOrthogonalCode[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XIsSelfOrthogonalCode(C)[110X  returns  `true'  if [3XC[103X is self-orthogonal. A code is
  [13Xself-orthogonal[113X  if  every  element of [3XC[103X is orthogonal to all elements of [3XC[103X,
  including  itself. (In the linear case, this simply means that the generator
  matrix of [3XC[103X multiplied with its transpose yields a null matrix.)[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XR := ReedMullerCode(1,4);[127X[104X
    [4X[28Xa linear [16,5,8]6 Reed-Muller (1,4) code over GF(2)[128X[104X
    [4X[25Xgap>[125X [27XIsSelfOrthogonalCode(R);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsSelfDualCode(R);[127X[104X
    [4X[28Xfalse[128X[104X
  [4X[32X[104X
  
  [1X4.3-10 IsDoublyEvenCode[101X
  
  [33X[1;0Y[29X[2XIsDoublyEvenCode[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XIsDoublyEvenCode(C)[110X  returns  `true'  if [3XC[103X 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.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XC:=BinaryGolayCode();[127X[104X
    [4X[28Xa cyclic [23,12,7]3 binary Golay code over GF(2)[128X[104X
    [4X[25Xgap>[125X [27XWeightDistribution(C);[127X[104X
    [4X[28X[ 1, 0, 0, 0, 0, 0, 0, 253, 506, 0, 0, 1288, 1288, 0, 0, 506, 253, 0, 0, 0, [128X[104X
    [4X[28X  0, 0, 0, 1 ][128X[104X
    [4X[25Xgap>[125X [27XIsDoublyEvenCode(C);  [127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27XC:=ExtendedCode(C);  [127X[104X
    [4X[28Xa linear [24,12,8]4 extended code[128X[104X
    [4X[25Xgap>[125X [27XWeightDistribution(C);[127X[104X
    [4X[28X[ 1, 0, 0, 0, 0, 0, 0, 0, 759, 0, 0, 0, 2576, 0, 0, 0, 759, 0, 0, 0, 0, 0, 0, [128X[104X
    [4X[28X  0, 1 ][128X[104X
    [4X[25Xgap>[125X [27XIsDoublyEvenCode(C);  [127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [1X4.3-11 IsSinglyEvenCode[101X
  
  [33X[1;0Y[29X[2XIsSinglyEvenCode[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XIsSinglyEvenCode(C)[110X  returns  `true' if [3XC[103X is a binary self-orthogonal linear
  code which is not doubly-even. In other words, [3XC[103X is a binary self-orthogonal
  code which has codewords of even weight.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xx:=Indeterminate(GF(2));                     [127X[104X
    [4X[28Xx_1[128X[104X
    [4X[25Xgap>[125X [27XC:=QuasiCyclicCode( [x^0, 1+x^3+x^5+x^6+x^7], 11, GF(2) );[127X[104X
    [4X[28Xa linear [22,11,1..6]4..7 quasi-cyclic code over GF(2)[128X[104X
    [4X[25Xgap>[125X [27XIsSelfDualCode(C);  # self-dual is a restriction of self-orthogonal[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsDoublyEvenCode(C);[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27XIsSinglyEvenCode(C);[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [1X4.3-12 IsEvenCode[101X
  
  [33X[1;0Y[29X[2XIsEvenCode[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XIsEvenCode(C)[110X  returns  `true'  if  [3XC[103X  is  a  binary  linear  code which has
  codewords of even weight--regardless whether or not it is self-orthogonal.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XC:=BinaryGolayCode();[127X[104X
    [4X[28Xa cyclic [23,12,7]3 binary Golay code over GF(2)[128X[104X
    [4X[25Xgap>[125X [27XIsSelfOrthogonalCode(C);[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27XIsEvenCode(C);[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27XC:=ExtendedCode(C);[127X[104X
    [4X[28Xa linear [24,12,8]4 extended code[128X[104X
    [4X[25Xgap>[125X [27XIsSelfOrthogonalCode(C);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsEvenCode(C);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XC:=ExtendedCode(QRCode(17,GF(2)));[127X[104X
    [4X[28Xa linear [18,9,6]3..5 extended code[128X[104X
    [4X[25Xgap>[125X [27XIsSelfOrthogonalCode(C);[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27XIsEvenCode(C);[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [1X4.3-13 IsSelfComplementaryCode[101X
  
  [33X[1;0Y[29X[2XIsSelfComplementaryCode[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XIsSelfComplementaryCode[110X returns `true' if[133X
  
  
  [24X[33X[0;6Yv \in C \Rightarrow 1 - v \in C,[133X
  
  [124X
  
  [33X[0;0Ywhere [22X1[122X is the all-one word of length [22Xn[122X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XIsSelfComplementaryCode( HammingCode( 3, GF(2) ) );[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsSelfComplementaryCode( EvenWeightSubcode([127X[104X
    [4X[25X>[125X [27XHammingCode( 3, GF(2) ) ) );[127X[104X
    [4X[28Xfalse[128X[104X
  [4X[32X[104X
  
  [1X4.3-14 IsAffineCode[101X
  
  [33X[1;0Y[29X[2XIsAffineCode[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XIsAffineCode[110X  returns `true' if [3XC[103X is an affine code. A code is called [13Xaffine[113X
  if  it is an affine space. In other words, a code is affine if it is a coset
  of a linear code.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XIsAffineCode( HammingCode( 3, GF(2) ) );[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsAffineCode( CosetCode( HammingCode( 3, GF(2) ),[127X[104X
    [4X[25X>[125X [27XCodeword([ 1, 0, 0, 0, 0, 0, 0 ]) ) );[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsAffineCode( NordstromRobinsonCode() );[127X[104X
    [4X[28Xfalse[128X[104X
  [4X[32X[104X
  
  [1X4.3-15 IsAlmostAffineCode[101X
  
  [33X[1;0Y[29X[2XIsAlmostAffineCode[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XIsAlmostAffineCode[110X  returns  `true' if [3XC[103X is an almost affine code. A code is
  called  [13Xalmost affine[113X if the size of any punctured code of [3XC[103X is [22Xq^r[122X for some
  [22Xr[122X,  where  [22Xq[122X  is  the size of the alphabet of the code. Every affine code is
  also  almost  affine,  and  every  code  over [22XGF(2)[122X and [22XGF(3)[122X that is almost
  affine is also affine.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xcode := ElementsCode( [ [0,0,0], [0,1,1], [0,2,2], [0,3,3],[127X[104X
    [4X[25X>[125X [27X                            [1,0,1], [1,1,0], [1,2,3], [1,3,2],[127X[104X
    [4X[25X>[125X [27X                            [2,0,2], [2,1,3], [2,2,0], [2,3,1],[127X[104X
    [4X[25X>[125X [27X                            [3,0,3], [3,1,2], [3,2,1], [3,3,0] ],[127X[104X
    [4X[25X>[125X [27X                            GF(4) );;[127X[104X
    [4X[25Xgap>[125X [27XIsAlmostAffineCode( code );[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XIsAlmostAffineCode( NordstromRobinsonCode() );[127X[104X
    [4X[28Xfalse[128X[104X
  [4X[32X[104X
  
  
  [1X4.4 [33X[0;0YEquivalence and Isomorphism of Codes[133X[101X
  
  [1X4.4-1 IsEquivalent[101X
  
  [33X[1;0Y[29X[2XIsEquivalent[102X( [3XC1[103X, [3XC2[103X ) [32X function[133X
  
  [33X[0;0YWe say that [3XC1[103X is [13Xpermutation equivalent[113X to [3XC2[103X if [3XC1[103X can be obtained from [3XC2[103X
  by  carrying out column permutations. [10XIsEquivalent[110X returns true if [3XC1[103X and [3XC2[103X
  are  equivalent codes. At this time, [10XIsEquivalent[110X only handles [13Xbinary[113X codes.
  (The  external  unix/linux  program  [12Xdesauto[112X  from  J.  S. Leon is called by
  [10XIsEquivalent[110X.) Of course, if [3XC1[103X and [3XC2[103X are equal, they are also equivalent.[133X
  
  [33X[0;0YNote that the algorithm is [13Xvery slow[113X for non-linear codes.[133X
  
  [33X[0;0YMore  generally,  we  say  that [3XC1[103X is [13Xequivalent[113X to [3XC2[103X if [3XC1[103X can be obtained
  from  [3XC2[103X  by  carrying  out  column  permutations  and  a permutation of the
  alphabet.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xx:= Indeterminate( GF(2), "x" );; pol:= x^3+x+1; [127X[104X
    [4X[28Xx^3+x+Z(2)^0[128X[104X
    [4X[25Xgap>[125X [27XH := GeneratorPolCode( pol, 7, GF(2));          [127X[104X
    [4X[28Xa cyclic [7,4,1..3]1 code defined by generator polynomial over GF(2)[128X[104X
    [4X[25Xgap>[125X [27XH = HammingCode(3, GF(2));[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[28X[128X[104X
    [4X[28X# verify that H is equivalent to a Hamming code[128X[104X
    [4X[25Xgap>[125X [27XIsEquivalent(H, HammingCode(3, GF(2)));[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XCodeIsomorphism(H, HammingCode(3, GF(2)));[127X[104X
    [4X[28X(3,4)(5,6,7)[128X[104X
  [4X[32X[104X
  
  [1X4.4-2 CodeIsomorphism[101X
  
  [33X[1;0Y[29X[2XCodeIsomorphism[102X( [3XC1[103X, [3XC2[103X ) [32X function[133X
  
  [33X[0;0YIf   the  two  codes  [3XC1[103X  and  [3XC2[103X  are  permutation  equivalent  codes  (see
  [2XIsEquivalent[102X   ([14X4.4-1[114X)),   [10XCodeIsomorphism[110X   returns  the  permutation  that
  transforms [3XC1[103X into [3XC2[103X. If the codes are not equivalent, it returns `false'.[133X
  
  [33X[0;0YAt  this  time, [10XIsEquivalent[110X only computes isomorphisms between [13Xbinary[113X codes
  on a linux/unix computer (since it calls Leon's C program [12Xdesauto[112X).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xx:= Indeterminate( GF(2), "x" );; pol:= x^3+x+1; [127X[104X
    [4X[28Xx^3+x+Z(2)^0[128X[104X
    [4X[25Xgap>[125X [27XH := GeneratorPolCode( pol, 7, GF(2));          [127X[104X
    [4X[28Xa cyclic [7,4,1..3]1 code defined by generator polynomial over GF(2)[128X[104X
    [4X[25Xgap>[125X [27XCodeIsomorphism(H, HammingCode(3, GF(2)));[127X[104X
    [4X[28X(3,4)(5,6,7)[128X[104X
    [4X[25Xgap>[125X [27XPermutedCode(H, (3,4)(5,6,7)) = HammingCode(3, GF(2));[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [1X4.4-3 AutomorphismGroup[101X
  
  [33X[1;0Y[29X[2XAutomorphismGroup[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XAutomorphismGroup[110X  returns  the automorphism group of a linear code [3XC[103X. For a
  binary  code,  the  automorphism  group  is the largest permutation group of
  degree [22Xn[122X such that each permutation applied to the columns of [3XC[103X again yields
  [3XC[103X.  [5XGUAVA[105X  calls  the  external program [12Xdesauto[112X 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 [10XPermutationAutomorphismGroup[110X.[133X
  
  [33X[0;0YSee  Leon  [Leo82]  for  a  more  precise description of the method, and the
  [11Xguava/src/leon/doc[111X subdirectory for for details about Leon's C programs.[133X
  
  [33X[0;0YThe  function  [10XPermutedCode[110X permutes the columns of a code (see [2XPermutedCode[102X
  ([14X6.1-4[114X)).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XR := RepetitionCode(7,GF(2));[127X[104X
    [4X[28Xa cyclic [7,1,7]3 repetition code over GF(2)[128X[104X
    [4X[28X[128X[104X
    [4X[28X# verify that every permutation keeps R identical, that is, the[128X[104X
    [4X[28X# automorphism group is Sym(7)[128X[104X
    [4X[25Xgap>[125X [27XAutomorphismGroup(R);[127X[104X
    [4X[28XSym( [ 1 .. 7 ] )[128X[104X
    [4X[25Xgap>[125X [27XC := CordaroWagnerCode(7);[127X[104X
    [4X[28Xa linear [7,2,4]3 Cordaro-Wagner code over GF(2)[128X[104X
    [4X[25Xgap>[125X [27XAsSSortedList(C);[127X[104X
    [4X[28X[ [ 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 ] ][128X[104X
    [4X[25Xgap>[125X [27XAutomorphismGroup(C);[127X[104X
    [4X[28XGroup([ (3,4), (4,5), (1,6)(2,7), (1,2), (6,7) ])[128X[104X
    [4X[25Xgap>[125X [27XC2 :=  PermutedCode(C, (1,6)(2,7));[127X[104X
    [4X[28Xa linear [7,2,4]3 permuted code[128X[104X
    [4X[25Xgap>[125X [27XAsSSortedList(C2);[127X[104X
    [4X[28X[ [ 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 ] ][128X[104X
    [4X[25Xgap>[125X [27XC2 = C;[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [1X4.4-4 PermutationAutomorphismGroup[101X
  
  [33X[1;0Y[29X[2XPermutationAutomorphismGroup[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XPermutationAutomorphismGroup[110X returns the permutation automorphism group of a
  linear  code  [3XC[103X. This is the largest permutation group of degree [22Xn[122X such that
  each  permutation  applied to the columns of [3XC[103X again yields [3XC[103X. It is written
  in GAP, so is much slower than [10XAutomorphismGroup[110X.[133X
  
  [33X[0;0YWhen    [3XC[103X    is    binary   [10XPermutationAutomorphismGroup[110X   does   [13Xnot[113X   call
  [10XAutomorphismGroup[110X,  even though they agree mathematically in that case. This
  way  [10XPermutationAutomorphismGroup[110X  can  be called on any platform which runs
  GAP.[133X
  
  [33X[0;0YThe  older  name for this command, [10XPermutationGroup[110X, will become obsolete in
  the next version of GAP.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XR := RepetitionCode(3,GF(3));[127X[104X
    [4X[28Xa cyclic [3,1,3]2 repetition code over GF(3)[128X[104X
    [4X[25Xgap>[125X [27XG:=PermutationAutomorphismGroup(R);;[127X[104X
    [4X[25Xgap>[125X [27XG=SymmetricGroup(3);[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  
  [1X4.5 [33X[0;0YDomain Functions for Codes[133X[101X
  
  [33X[0;0YThese  are  some  GAP  functions  that  work  on `Domains' in general. Their
  specific effect on `Codes' is explained here.[133X
  
  [1X4.5-1 IsFinite[101X
  
  [33X[1;0Y[29X[2XIsFinite[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XIsFinite[110X  is  an  implementation  of  the  GAP  domain function [10XIsFinite[110X. It
  returns true for a code [3XC[103X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XIsFinite( RepetitionCode( 1000, GF(11) ) );[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [1X4.5-2 Size[101X
  
  [33X[1;0Y[29X[2XSize[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XSize[110X  returns the size of [3XC[103X, the number of elements of the code. If the code
  is  linear, the size of the code is equal to [22Xq^k[122X, where [22Xq[122X is the size of the
  base field of [3XC[103X and [22Xk[122X is the dimension.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XSize( RepetitionCode( 1000, GF(11) ) );[127X[104X
    [4X[28X11[128X[104X
    [4X[25Xgap>[125X [27XSize( NordstromRobinsonCode() );[127X[104X
    [4X[28X256[128X[104X
  [4X[32X[104X
  
  [1X4.5-3 LeftActingDomain[101X
  
  [33X[1;0Y[29X[2XLeftActingDomain[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XLeftActingDomain[110X  returns  the  base  field  of  a code [3XC[103X. Each element of [3XC[103X
  consists  of  elements  of  this base field. If the base field is [22XF[122X, and the
  word  length  of the code is [22Xn[122X, then the codewords are elements of [22XF^n[122X. If [3XC[103X
  is  a  cyclic  code,  its  elements  are  interpreted  as  polynomials  with
  coefficients over [22XF[122X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XC1 := ElementsCode([[0,0,0], [1,0,1], [0,1,0]], GF(4));[127X[104X
    [4X[28Xa (3,3,1..3)2..3 user defined unrestricted code over GF(4)[128X[104X
    [4X[25Xgap>[125X [27XLeftActingDomain( C1 );[127X[104X
    [4X[28XGF(2^2)[128X[104X
    [4X[25Xgap>[125X [27XLeftActingDomain( HammingCode( 3, GF(9) ) );[127X[104X
    [4X[28XGF(3^2)[128X[104X
  [4X[32X[104X
  
  [1X4.5-4 Dimension[101X
  
  [33X[1;0Y[29X[2XDimension[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XDimension[110X  returns  the  parameter [22Xk[122X of [3XC[103X, the dimension of the code, or the
  number of information symbols in each codeword. The dimension is not defined
  for non-linear codes; [10XDimension[110X then returns an error.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XDimension( NullCode( 5, GF(5) ) );[127X[104X
    [4X[28X0[128X[104X
    [4X[25Xgap>[125X [27XC := BCHCode( 15, 4, GF(4) );[127X[104X
    [4X[28Xa cyclic [15,9,5]3..4 BCH code, delta=5, b=1 over GF(4)[128X[104X
    [4X[25Xgap>[125X [27XDimension( C );[127X[104X
    [4X[28X9[128X[104X
    [4X[25Xgap>[125X [27XSize( C ) = Size( LeftActingDomain( C ) ) ^ Dimension( C );[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [1X4.5-5 AsSSortedList[101X
  
  [33X[1;0Y[29X[2XAsSSortedList[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XAsSSortedList[110X (as strictly sorted list) returns an immutable, duplicate free
  list  of  the elements of [3XC[103X. For a finite field [22XGF(q)[122X generated by powers of
  [22XZ(q)[122X, the ordering on[133X
  
  
  [24X[33X[0;6YGF(q)=\{ 0 , Z(q)^0, Z(q), Z(q)^2, ...Z(q)^{q-2} \}[133X
  
  [124X
  
  [33X[0;0Yis  that  determined  by  the  exponents  [22Xi[122X.  These elements are of the type
  codeword  (see  [2XCodeword[102X ([14X3.1-1[114X)). 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  [10XCodewordNr[110X  (see [2XCodewordNr[102X
  ([14X3.1-2[114X)).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XC := ConferenceCode( 5 );[127X[104X
    [4X[28Xa (5,12,2)1..4 conference code over GF(2)[128X[104X
    [4X[25Xgap>[125X [27XAsSSortedList( C );[127X[104X
    [4X[28X[ [ 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 ], [128X[104X
    [4X[28X  [ 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 ], [128X[104X
    [4X[28X  [ 1 1 1 0 0 ], [ 1 1 1 1 1 ] ][128X[104X
    [4X[25Xgap>[125X [27XCodewordNr( C, [ 1, 2 ] );[127X[104X
    [4X[28X[ [ 0 0 0 0 0 ], [ 0 0 1 1 1 ] ][128X[104X
  [4X[32X[104X
  
  
  [1X4.6 [33X[0;0YPrinting and Displaying Codes[133X[101X
  
  [1X4.6-1 Print[101X
  
  [33X[1;0Y[29X[2XPrint[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XPrint[110X  prints information about [3XC[103X. This is the same as typing the identifier
  [3XC[103X at the GAP-prompt.[133X
  
  [33X[0;0YIf the argument is an unrestricted code, information in the form[133X
  
  a (n,M,d)r ... code over GF(q)
  
  [33X[0;0Yis  printed,  where  [3Xn[103X  is  the word length, [3XM[103X the number of elements of the
  code, [3Xd[103X the minimum distance and [3Xr[103X the covering radius.[133X
  
  [33X[0;0YIf the argument is a linear code, information in the form[133X
  
  a linear [n,k,d]r ... code over GF(q)
  
  [33X[0;0Yis  printed,  where [3Xn[103X is the word length, [3Xk[103X the dimension of the code, [3Xd[103X the
  minimum distance and [3Xr[103X the covering radius.[133X
  
  [33X[0;0YExcept  for codes produced by [10XRandomLinearCode[110X, if [3Xd[103X is not yet known, it is
  displayed in the form[133X
  
  lowerbound..upperbound
  
  [33X[0;0Yand  if  [3Xr[103X  is  not  yet known, it is displayed in the same way. For certain
  ranges  of  [22Xn[122X,  the  values  of  [3Xlowerbound[103X and [3Xupperbound[103X are obtained from
  tables.[133X
  
  [33X[0;0YThe function [10XDisplay[110X gives more information. See [2XDisplay[102X ([14X4.6-3[114X).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XC1 := ExtendedCode( HammingCode( 3, GF(2) ) );[127X[104X
    [4X[28Xa linear [8,4,4]2 extended code[128X[104X
    [4X[25Xgap>[125X [27XPrint( "This is ", NordstromRobinsonCode(), ". \n");[127X[104X
    [4X[28XThis is a (16,256,6)4 Nordstrom-Robinson code over GF(2). [128X[104X
  [4X[32X[104X
  
  [1X4.6-2 String[101X
  
  [33X[1;0Y[29X[2XString[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XString[110X  returns  information  about  [3XC[103X in a string. This function is used by
  [10XPrint[110X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xx:= Indeterminate( GF(3), "x" );; pol:= x^2+1;[127X[104X
    [4X[28Xx^2+Z(3)^0[128X[104X
    [4X[25Xgap>[125X [27XFactors(pol);[127X[104X
    [4X[28X[ x^2+Z(3)^0 ][128X[104X
    [4X[25Xgap>[125X [27XH := GeneratorPolCode( pol, 8, GF(3));[127X[104X
    [4X[28Xa cyclic [8,6,1..2]1..2 code defined by generator polynomial over GF(3)[128X[104X
    [4X[25Xgap>[125X [27XString(H);[127X[104X
    [4X[28X"a cyclic [8,6,1..2]1..2 code defined by generator polynomial over GF(3)"[128X[104X
  [4X[32X[104X
  
  [1X4.6-3 Display[101X
  
  [33X[1;0Y[29X[2XDisplay[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XDisplay[110X  prints  the method of construction of code [3XC[103X. With this history, in
  most  cases  an  equal  or  equivalent code can be reconstructed. If [3XC[103X is an
  unmanipulated code, the result is equal to output of the function [10XPrint[110X (see
  [2XPrint[102X ([14X4.6-1[114X)).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XDisplay( RepetitionCode( 6, GF(3) ) );[127X[104X
    [4X[28Xa cyclic [6,1,6]4 repetition code over GF(3)[128X[104X
    [4X[25Xgap>[125X [27XC1 := ExtendedCode( HammingCode(2) );;[127X[104X
    [4X[25Xgap>[125X [27XC2 := PuncturedCode( ReedMullerCode( 2, 3 ) );;[127X[104X
    [4X[25Xgap>[125X [27XDisplay( LengthenedCode( UUVCode( C1, C2 ) ) );[127X[104X
    [4X[28Xa linear [12,8,2]2..4 code, lengthened with 1 column(s) of[128X[104X
    [4X[28Xa linear [11,8,1]1..2 U|U+V construction code of[128X[104X
    [4X[28XU: a linear [4,1,4]2 extended code of[128X[104X
    [4X[28X   a linear [3,1,3]1 Hamming (2,2) code over GF(2)[128X[104X
    [4X[28XV: a linear [7,7,1]0 punctured code of[128X[104X
    [4X[28X   a cyclic [8,7,2]1 Reed-Muller (2,3) code over GF(2)[128X[104X
  [4X[32X[104X
  
  [1X4.6-4 DisplayBoundsInfo[101X
  
  [33X[1;0Y[29X[2XDisplayBoundsInfo[102X( [3Xbds[103X ) [32X function[133X
  
  [33X[0;0Y[10XDisplayBoundsInfo[110X  prints the method of construction of the code [22XC[122X indicated
  in [10Xbds:= BoundsMinimumDistance( n, k, GF(q) )[110X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xbounds := BoundsMinimumDistance( 20, 17, GF(4) );;[127X[104X
    [4X[25Xgap>[125X [27XDisplayBoundsInfo(bounds);[127X[104X
    [4X[28Xan optimal linear [20,17,d] code over GF(4) has d=3[128X[104X
    [4X[28X------------------------------------------------------------------------------[128X[104X
    [4X[28XLb(20,17)=3, by shortening of:[128X[104X
    [4X[28XLb(21,18)=3, by applying construction B to a [81,77,3] code[128X[104X
    [4X[28XLb(81,77)=3, by shortening of:[128X[104X
    [4X[28XLb(85,81)=3, reference: Ham[128X[104X
    [4X[28X------------------------------------------------------------------------------[128X[104X
    [4X[28XUb(20,17)=3, by considering shortening to:[128X[104X
    [4X[28XUb(7,4)=3, by considering puncturing to:[128X[104X
    [4X[28XUb(6,4)=2, by construction B applied to:[128X[104X
    [4X[28XUb(2,1)=2, repetition code[128X[104X
    [4X[28X------------------------------------------------------------------------------[128X[104X
    [4X[28XReference Ham:[128X[104X
    [4X[28X%T this reference is unknown, for more info[128X[104X
    [4X[28X%T contact A.E. Brouwer (aeb@cwi.nl)[128X[104X
  [4X[32X[104X
  
  
  [1X4.7 [33X[0;0YGenerating (Check) Matrices and Polynomials[133X[101X
  
  [1X4.7-1 GeneratorMat[101X
  
  [33X[1;0Y[29X[2XGeneratorMat[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XGeneratorMat[110X  returns  a  generator  matrix  of  [3XC[103X. The code consists of all
  linear combinations of the rows of this matrix.[133X
  
  [33X[0;0YIf  until  now  no generator matrix of [3XC[103X 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.[133X
  
  [33X[0;0YIf [3XC[103X is a non-linear code, the function returns an error.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XGeneratorMat( HammingCode( 3, GF(2) ) );[127X[104X
    [4X[28X[ <an immutable GF2 vector of length 7>, [128X[104X
    [4X[28X  <an immutable GF2 vector of length 7>, [128X[104X
    [4X[28X  <an immutable GF2 vector of length 7>, [128X[104X
    [4X[28X  <an immutable GF2 vector of length 7> ][128X[104X
    [4X[25Xgap>[125X [27XDisplay(last);[127X[104X
    [4X[28X 1 1 1 . . . .[128X[104X
    [4X[28X 1 . . 1 1 . .[128X[104X
    [4X[28X . 1 . 1 . 1 .[128X[104X
    [4X[28X 1 1 . 1 . . 1[128X[104X
    [4X[25Xgap>[125X [27XGeneratorMat( RepetitionCode( 5, GF(25) ) );[127X[104X
    [4X[28X[ [ Z(5)^0, Z(5)^0, Z(5)^0, Z(5)^0, Z(5)^0 ] ][128X[104X
    [4X[25Xgap>[125X [27XGeneratorMat( NullCode( 14, GF(4) ) );[127X[104X
    [4X[28X[  ][128X[104X
  [4X[32X[104X
  
  [1X4.7-2 CheckMat[101X
  
  [33X[1;0Y[29X[2XCheckMat[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XCheckMat[110X  returns a parity check matrix of [3XC[103X. 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 [3XC[103X (if possible), whichever is available.[133X
  
  [33X[0;0YIf [3XC[103X is a non-linear code, the function returns an error.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XCheckMat( HammingCode(3, GF(2) ) );[127X[104X
    [4X[28X[ [ 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0, Z(2)^0, Z(2)^0, Z(2)^0 ], [128X[104X
    [4X[28X  [ 0*Z(2), Z(2)^0, Z(2)^0, 0*Z(2), 0*Z(2), Z(2)^0, Z(2)^0 ], [128X[104X
    [4X[28X  [ Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0 ] ][128X[104X
    [4X[25Xgap>[125X [27XDisplay(last);[127X[104X
    [4X[28X . . . 1 1 1 1[128X[104X
    [4X[28X . 1 1 . . 1 1[128X[104X
    [4X[28X 1 . 1 . 1 . 1[128X[104X
    [4X[25Xgap>[125X [27XCheckMat( RepetitionCode( 5, GF(25) ) );[127X[104X
    [4X[28X[ [ Z(5)^0, Z(5)^2, 0*Z(5), 0*Z(5), 0*Z(5) ], [128X[104X
    [4X[28X  [ 0*Z(5), Z(5)^0, Z(5)^2, 0*Z(5), 0*Z(5) ], [128X[104X
    [4X[28X  [ 0*Z(5), 0*Z(5), Z(5)^0, Z(5)^2, 0*Z(5) ], [128X[104X
    [4X[28X  [ 0*Z(5), 0*Z(5), 0*Z(5), Z(5)^0, Z(5)^2 ] ][128X[104X
    [4X[25Xgap>[125X [27XCheckMat( WholeSpaceCode( 12, GF(4) ) );[127X[104X
    [4X[28X[  ][128X[104X
  [4X[32X[104X
  
  [1X4.7-3 GeneratorPol[101X
  
  [33X[1;0Y[29X[2XGeneratorPol[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XGeneratorPol[110X returns the generator polynomial of [3XC[103X. The code consists of all
  multiples  of  the  generator  polynomial  modulo [22Xx^n-1[122X, where [22Xn[122X is the word
  length  of  [3XC[103X.  The generator polynomial is determined from either the check
  polynomial,  the  generator  or  check  matrix  or  the  elements  of  [3XC[103X (if
  possible), whichever is available.[133X
  
  [33X[0;0YIf [3XC[103X is not a cyclic code, the function returns `false'.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XGeneratorPol(GeneratorMatCode([[1, 1, 0], [0, 1, 1]], GF(2)));[127X[104X
    [4X[28Xx_1+Z(2)^0[128X[104X
    [4X[25Xgap>[125X [27XGeneratorPol( WholeSpaceCode( 4, GF(2) ) );[127X[104X
    [4X[28XZ(2)^0[128X[104X
    [4X[25Xgap>[125X [27XGeneratorPol( NullCode( 7, GF(3) ) );[127X[104X
    [4X[28Xx_1^7-Z(3)^0[128X[104X
  [4X[32X[104X
  
  [1X4.7-4 CheckPol[101X
  
  [33X[1;0Y[29X[2XCheckPol[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XCheckPol[110X  returns  the  check  polynomial  of  [3XC[103X.  The  code consists of all
  polynomials [22Xf[122X with[133X
  
  
  [24X[33X[0;6Yf\cdot h \equiv 0 \ ({\rm mod}\ x^n-1),[133X
  
  [124X
  
  [33X[0;0Ywhere  [22Xh[122X  is  the check polynomial, and [22Xn[122X is the word length of [3XC[103X. The check
  polynomial  is  computed  from  the  generator  polynomial, the generator or
  parity  check  matrix  or  the  elements  of  [3XC[103X  (if possible), whichever is
  available.[133X
  
  [33X[0;0YIf [3XC[103X if not a cyclic code, the function returns an error.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XCheckPol(GeneratorMatCode([[1, 1, 0], [0, 1, 1]], GF(2)));[127X[104X
    [4X[28Xx_1^2+x_1+Z(2)^0[128X[104X
    [4X[25Xgap>[125X [27XCheckPol(WholeSpaceCode(4, GF(2)));[127X[104X
    [4X[28Xx_1^4+Z(2)^0[128X[104X
    [4X[25Xgap>[125X [27XCheckPol(NullCode(7,GF(3)));[127X[104X
    [4X[28XZ(3)^0[128X[104X
  [4X[32X[104X
  
  [1X4.7-5 RootsOfCode[101X
  
  [33X[1;0Y[29X[2XRootsOfCode[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XRootsOfCode[110X  returns  a  list  of all zeros of the generator polynomial of a
  cyclic code [3XC[103X. These are finite field elements in the splitting field of the
  generator  polynomial, [22XGF(q^m)[122X, [22Xm[122X is the multiplicative order of the size of
  the base field of the code, modulo the word length.[133X
  
  [33X[0;0YThe reverse process, constructing a code from a set of roots, can be carried
  out by the function [10XRootsCode[110X (see [2XRootsCode[102X ([14X5.5-3[114X)).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XC1 := ReedSolomonCode( 16, 5 );[127X[104X
    [4X[28Xa cyclic [16,12,5]3..4 Reed-Solomon code over GF(17)[128X[104X
    [4X[25Xgap>[125X [27XRootsOfCode( C1 );[127X[104X
    [4X[28X[ Z(17), Z(17)^2, Z(17)^3, Z(17)^4 ][128X[104X
    [4X[25Xgap>[125X [27XC2 := RootsCode( 16, last );[127X[104X
    [4X[28Xa cyclic [16,12,5]3..4 code defined by roots over GF(17)[128X[104X
    [4X[25Xgap>[125X [27XC1 = C2;[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  
  [1X4.8 [33X[0;0YParameters of Codes[133X[101X
  
  [1X4.8-1 WordLength[101X
  
  [33X[1;0Y[29X[2XWordLength[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XWordLength[110X  returns  the  parameter [22Xn[122X of [3XC[103X, the word length of the elements.
  Elements  of  cyclic  codes  are  polynomials  of  maximum  degree  [22Xn-1[122X,  as
  calculations are carried out modulo [22Xx^n-1[122X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XWordLength( NordstromRobinsonCode() );[127X[104X
    [4X[28X16[128X[104X
    [4X[25Xgap>[125X [27XWordLength( PuncturedCode( WholeSpaceCode(7) ) );[127X[104X
    [4X[28X6[128X[104X
    [4X[25Xgap>[125X [27XWordLength( UUVCode( WholeSpaceCode(7), RepetitionCode(7) ) );[127X[104X
    [4X[28X14[128X[104X
  [4X[32X[104X
  
  [1X4.8-2 Redundancy[101X
  
  [33X[1;0Y[29X[2XRedundancy[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XRedundancy[110X  returns  the  redundancy [22Xr[122X of [3XC[103X, which is equal to the number of
  check  symbols  in each element. If [3XC[103X is not a linear code the redundancy is
  not defined and [10XRedundancy[110X returns an error.[133X
  
  [33X[0;0YIf  a  linear  code  [3XC[103X  has dimension [22Xk[122X and word length [22Xn[122X, it has redundancy
  [22Xr=n-k[122X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XC := TernaryGolayCode();[127X[104X
    [4X[28Xa cyclic [11,6,5]2 ternary Golay code over GF(3)[128X[104X
    [4X[25Xgap>[125X [27XRedundancy(C);[127X[104X
    [4X[28X5[128X[104X
    [4X[25Xgap>[125X [27XRedundancy( DualCode(C) );[127X[104X
    [4X[28X6[128X[104X
  [4X[32X[104X
  
  [1X4.8-3 MinimumDistance[101X
  
  [33X[1;0Y[29X[2XMinimumDistance[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XMinimumDistance[110X  returns  the  minimum  distance of [3XC[103X, the largest integer [22Xd[122X
  with  the property that every element of [3XC[103X has at least a Hamming distance [22Xd[122X
  (see  [2XDistanceCodeword[102X ([14X3.6-2[114X)) to any other element of [3XC[103X. For linear codes,
  the  minimum  distance  is equal to the minimum weight. This means that [22Xd[122X is
  also    the    smallest    positive   value   with   [22Xw[d+1]   ≠   0[122X,   where
  [22Xw=(w[1],w[2],...,w[n])[122X    is    the    weight   distribution   of   [3XC[103X   (see
  [2XWeightDistribution[102X  ([14X4.9-2[114X)).  For  unrestricted  codes,  [22Xd[122X  is the smallest
  positive  value with [22Xw[d+1] ≠ 0[122X, where [22Xw[122X is the inner distribution of [3XC[103X (see
  [2XInnerDistribution[102X ([14X4.9-3[114X)).[133X
  
  [33X[0;0YFor codes with only one element, the minimum distance is defined to be equal
  to the word length.[133X
  
  [33X[0;0YFor  linear  codes [3XC[103X, the algorithm used is the following: After replacing [3XC[103X
  by  a permutation equivalent [3XC'[103X, one may assume the generator matrix has the
  following  form  [22XG=(I_k | A)[122X, for some [22Xk× (n-k)[122X matrix [22XA[122X. If [22XA=0[122X then return
  [22Xd(C)=1[122X.  Next,  find the minimum distance of the code spanned by the rows of
  [22XA[122X.  Call  this  distance  [22Xd(A)[122X.  Note  that [22Xd(A)[122X is equal to the the Hamming
  distance [22Xd(v,0)[122X where [22Xv[122X is some proper linear combination of [22Xi[122X distinct rows
  of [22XA[122X. Return [22Xd(C)=d(A)+i[122X, where [22Xi[122X is as in the previous step.[133X
  
  [33X[0;0YThis  command  may also be called using the syntax [10XMinimumDistance(C, w)[110X. In
  this  form,  [10XMinimumDistance[110X returns the minimum distance of a codeword [3Xw[103X to
  the code [3XC[103X, also called the [13Xdistance from [3Xw[103X to[113X [3XC[103X. This is the smallest value
  [22Xd[122X  for which there is an element [22Xc[122X of the code [3XC[103X which is at distance [22Xd[122X from
  [3Xw[103X.  So  [22Xd[122X  is  also  the  minimum value for which [22XD[d+1] ≠ 0[122X, where [22XD[122X is the
  distance distribution of [3Xw[103X to [3XC[103X (see [2XDistancesDistribution[102X ([14X4.9-4[114X)).[133X
  
  [33X[0;0YNote  that  [3Xw[103X must be an element of the same vector space as the elements of
  [3XC[103X.  [3Xw[103X  does  not  necessarily  belong  to  the code (if it does, the minimum
  distance is zero).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XC := MOLSCode(7);; MinimumDistance(C);[127X[104X
    [4X[28X3[128X[104X
    [4X[25Xgap>[125X [27XWeightDistribution(C);[127X[104X
    [4X[28X[ 1, 0, 0, 24, 24 ][128X[104X
    [4X[25Xgap>[125X [27XMinimumDistance( WholeSpaceCode( 5, GF(3) ) );[127X[104X
    [4X[28X1[128X[104X
    [4X[25Xgap>[125X [27XMinimumDistance( NullCode( 4, GF(2) ) );[127X[104X
    [4X[28X4[128X[104X
    [4X[25Xgap>[125X [27XC := ConferenceCode(9);; MinimumDistance(C);[127X[104X
    [4X[28X4[128X[104X
    [4X[25Xgap>[125X [27XInnerDistribution(C);[127X[104X
    [4X[28X[ 1, 0, 0, 0, 63/5, 9/5, 18/5, 0, 9/10, 1/10 ][128X[104X
    [4X[25Xgap>[125X [27XC := MOLSCode(7);; w := CodewordNr( C, 17 );[127X[104X
    [4X[28X[ 3 3 6 2 ][128X[104X
    [4X[25Xgap>[125X [27XMinimumDistance( C, w );[127X[104X
    [4X[28X0[128X[104X
    [4X[25Xgap>[125X [27XC := RemovedElementsCode( C, w );; # so w no longer belongs to C [127X[104X
    [4X[25Xgap>[125X [27XMinimumDistance( C, w );[127X[104X
    [4X[28X3[128X[104X
  [4X[32X[104X
  
  [33X[0;0YSee  also  the  [5XGUAVA[105X commands relating to bounds on the minimum distance in
  section [14X7.1[114X.[133X
  
  [1X4.8-4 MinimumDistanceLeon[101X
  
  [33X[1;0Y[29X[2XMinimumDistanceLeon[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XMinimumDistanceLeon[110X  returns  the  ``probable'' minimum distance [22Xd_Leon[122X of a
  linear  binary  code  [3XC[103X,  using  an  implementation  of Leon's probabilistic
  polynomial  time  algorithm.  Briefly: Let [3XC[103X be a linear code of dimension [22Xk[122X
  over  [22XGF(q)[122X as above. The algorithm has input parameters [22Xs[122X and [22Xρ[122X, where [22Xs[122X is
  an integer between [22X2[122X and [22Xn-k[122X, and [22Xρ[122X is an integer between [22X2[122X and [22Xk[122X.[133X
  
  [30X    [33X[0;6YFind a generator matrix [22XG[122X of [22XC[122X.[133X
  
  [30X    [33X[0;6YRandomly permute the columns of [22XG[122X.[133X
  
  [30X    [33X[0;6YPerform  Gaussian  elimination  on the permuted matrix to obtain a new
        matrix of the following form:[133X
  
  
  [24X      [33X[0;6YG=(I_{k} \, | \, Z \, | \, B)[133X
  
  [124X
  
        [33X[0;6Ywith  [22XZ[122X  a  [22Xk× s[122X matrix. If [22X(Z,B)[122X is the zero matrix then return [22X1[122X for
        the  minimum  distance.  If  [22XZ=0[122X  but not [22XB[122X then either choose another
        permutation of the rows of [3XC[103X or return `method fails'.[133X
  
  [30X    [33X[0;6YSearch [22XZ[122X for at most [22Xρ[122X rows that lead to codewords of weight less than
        [22Xρ[122X.[133X
  
  [30X    [33X[0;6YFor these codewords, compute the weight of the whole word in [3XC[103X. Return
        this weight.[133X
  
  [33X[0;0Y(See for example J. S. Leon, [Leo88] for more details.) Sometimes (as is the
  case  in  [5XGUAVA[105X)  this probabilistic algorithm is repeated several times and
  the  most commonly occurring value is taken. (This function actually has two
  optional  arguments:  [10Xp[110X  and  [10Xnum[110X.  The command [10XMinimumDistanceLeon(C,p,num)[110X
  allows  a bit more flexibility for the user - see the GAP code in codeops.gi
  for details.)[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XC:=RandomLinearCode(50,22,GF(2));[127X[104X
    [4X[28Xa  [50,22,?] randomly generated code over GF(2)[128X[104X
    [4X[25Xgap>[125X [27XMinimumDistanceLeon(C); #time; #Uncomment the call to "time;"" to see performance data[127X[104X
    [4X[28X6[128X[104X
    [4X[25Xgap>[125X [27XMinimumDistance(C); #time; #Uncomment the call to "time;"" to see performance data[127X[104X
    [4X[28X6[128X[104X
  [4X[32X[104X
  
  [1X4.8-5 MinimumWeight[101X
  
  [33X[1;0Y[29X[2XMinimumWeight[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XMinimumWeight[110X  returns the minimum Hamming weight of a linear code [3XC[103X. At the
  moment,  this  function  works  for  binary  and  ternary  codes  only.  The
  [10XMinimumWeight[110X  function  relies  on  an external executable program which is
  written in C language. As a consequence, the execution time of [10XMinimumWeight[110X
  function is faster than that of [2XMinimumDistance[102X ([14X4.8-3[114X) function.[133X
  
  [33X[0;0YThe  [10XMinimumWeight[110X  function  implements  Chen's  [Che69]  algorithm if [3XC[103X is
  cyclic,  and  Zimmermann's  [Zim96] algorithm if [3XC[103X 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.  Similarly,  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  [22X[151,45][122X  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 [22X10[122X, rather than [22X9[122X. We can see
  that,  this  0  mod  4 constraint on the codeword weights, has allowed us to
  avoid  enumeration  of  [22Xb(45,10) = 3,190,187,286[122X additional codewords, where
  [22Xb(n,k)=n!/((n-k)!k!)[122X is the binomial coefficient of integers [22Xn[122X and [22Xk[122X.[133X
  
  [33X[0;0YNote  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.[133X
  
  [33X[0;0YIf   you   find   any   bugs   on   this   function,  please  report  it  to
  ctjhai@plymouth.ac.uk.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27X# Extended ternary quadratic residue code of length 48[127X[104X
    [4X[25Xgap>[125X [27Xn := 47;;[127X[104X
    [4X[25Xgap>[125X [27Xx := Indeterminate(GF(3), "x");;[127X[104X
    [4X[25Xgap>[125X [27XF := Factors(x^n-1);;[127X[104X
    [4X[25Xgap>[125X [27Xv := NullVector(n,GF(3));;[127X[104X
    [4X[25Xgap>[125X [27Xv := v + ShallowCopy(VectorCodeword( Codeword(F[2]) ));;[127X[104X
    [4X[25Xgap>[125X [27XG := CirculantMatrix(24, v);;[127X[104X
    [4X[25Xgap>[125X [27Xfor i in [1..Size(G)] do; s:=Zero(GF(3));[127X[104X
    [4X[25X>[125X [27Xfor j in [1..Size(G[i])] do; s:=s+G[i][j]; od; Append(G[i], [ s ]);[127X[104X
    [4X[25X>[125X [27Xod;;[127X[104X
    [4X[25Xgap>[125X [27XC := GeneratorMatCodeNC(G, GF(3));[127X[104X
    [4X[28Xa  [48,24,?] randomly generated code over GF(3)[128X[104X
    [4X[25Xgap>[125X [27XMinimumWeight(C);[127X[104X
    [4X[28X15[128X[104X
    [4X[25Xgap>[125X [27X# Binary cyclic code [151,45,36][127X[104X
    [4X[25Xgap>[125X [27Xn := 151;;[127X[104X
    [4X[25Xgap>[125X [27Xx := Indeterminate(GF(2), "x");;[127X[104X
    [4X[25Xgap>[125X [27XF := Factors(x^n-1);;[127X[104X
    [4X[25Xgap>[125X [27XC := CheckPolCode(F[2]*F[3]*F[3]*F[4], n, GF(2));[127X[104X
    [4X[28Xa cyclic [151,45,1..50]31..75 code defined by check polynomial over GF(2)[128X[104X
    [4X[25Xgap>[125X [27XMinimumWeight(C);[127X[104X
    [4X[28X36[128X[104X
  [4X[32X[104X
  
  [1X4.8-6 DecreaseMinimumDistanceUpperBound[101X
  
  [33X[1;0Y[29X[2XDecreaseMinimumDistanceUpperBound[102X( [3XC[103X, [3Xt[103X, [3Xm[103X ) [32X function[133X
  
  [33X[0;0Y[10XDecreaseMinimumDistanceUpperBound[110X  is an implementation of the algorithm for
  the  minimum  distance  of  a  linear  binary  code  [3XC[103X by Leon [Leo88]. This
  algorithm  tries to find codewords with small minimum weights. The parameter
  [3Xt[103X  is  at  least  [22X1[122X  and  less than the dimension of [3XC[103X. The best results are
  obtained  if it is close to the dimension of the code. The parameter [3Xm[103X gives
  the number of runs that the algorithm will perform.[133X
  
  [33X[0;0YThe  result  returned is a record with two fields; the first, [10Xmindist[110X, gives
  the  lowest  weight  found, and [10Xword[110X gives the corresponding codeword. (This
  was  implemented  before  [10XMinimumDistanceLeon[110X  but  independently. The older
  manual  had  given  the  command  incorrectly, so the command was only found
  after  reading  all  the  [13X*.gi[113X  files  in  the  [5XGUAVA[105X  library.  Though both
  [10XMinimumDistance[110X   and   [10XMinimumDistanceLeon[110X   often  run  much  faster  than
  [10XDecreaseMinimumDistanceUpperBound[110X, [10XDecreaseMinimumDistanceUpperBound[110X appears
  to be more accurate than [10XMinimumDistanceLeon[110X.)[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XC:=RandomLinearCode(5,2,GF(2));[127X[104X
    [4X[28Xa  [5,2,?] randomly generated code over GF(2)[128X[104X
    [4X[25Xgap>[125X [27XDecreaseMinimumDistanceUpperBound(C,1,4);[127X[104X
    [4X[28Xrec( mindist := 3, word := [ 0*Z(2), Z(2)^0, Z(2)^0, 0*Z(2), Z(2)^0 ] )[128X[104X
    [4X[25Xgap>[125X [27XMinimumDistance(C);[127X[104X
    [4X[28X3[128X[104X
    [4X[25Xgap>[125X [27XC:=RandomLinearCode(8,4,GF(2));[127X[104X
    [4X[28Xa  [8,4,?] randomly generated code over GF(2)[128X[104X
    [4X[25Xgap>[125X [27XDecreaseMinimumDistanceUpperBound(C,3,4);[127X[104X
    [4X[28Xrec( mindist := 2, [128X[104X
    [4X[28X  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 ] )[128X[104X
    [4X[25Xgap>[125X [27XMinimumDistance(C);[127X[104X
    [4X[28X2[128X[104X
  [4X[32X[104X
  
  [1X4.8-7 MinimumDistanceRandom[101X
  
  [33X[1;0Y[29X[2XMinimumDistanceRandom[102X( [3XC[103X, [3Xnum[103X, [3Xs[103X ) [32X function[133X
  
  [33X[0;0Y[10XMinimumDistanceRandom[110X  returns  an  upper  bound  for  the  minimum distance
  [22Xd_random[122X  of  a  linear binary code [3XC[103X, using a probabilistic polynomial time
  algorithm.  Briefly:  Let  [3XC[103X  be  a linear code of dimension [22Xk[122X over [22XGF(q)[122X as
  above.  The  algorithm has input parameters [22Xnum[122X and [22Xs[122X, where [22Xs[122X is an integer
  between [22X2[122X and [22Xn-1[122X, and [22Xnum[122X is an integer greater than or equal to [22X1[122X.[133X
  
  [30X    [33X[0;6YFind a generator matrix [22XG[122X of [22XC[122X.[133X
  
  [30X    [33X[0;6YRandomly permute the columns of [22XG[122X, written [22XG_p[122X..[133X
  
  [30X
  [24X    [33X[0;6YG=(A, B)[133X
  
  [124X
  
        [33X[0;6Ywith  [22XA[122X  a  [22Xk×  s[122X  matrix. If [22XA[122X is the zero matrix then return `method
        fails'.[133X
  
  [30X    [33X[0;6YSearch  [22XA[122X  for  at most [22X5[122X rows that lead to codewords, in the code [22XC_A[122X
        with generator matrix [22XA[122X, of minimum weight.[133X
  
  [30X    [33X[0;6YFor  these codewords, use the associated linear combination to compute
        the weight of the whole word in [3XC[103X. Return this weight and codeword.[133X
  
  [33X[0;0YThis  probabilistic  algorithm  is repeated [3Xnum[103X times (with different random
  permutations  of the rows of [22XG[122X each time) and the weight and codeword of the
  lowest occurring weight is taken.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XC:=RandomLinearCode(60,20,GF(2));[127X[104X
    [4X[28Xa  [60,20,?] randomly generated code over GF(2)[128X[104X
    [4X[25Xgap>[125X [27X#mindist(C); #time;[127X[104X
    [4X[25Xgap>[125X [27X#mindistleon(C,10,30); #time; #doesn't work well[127X[104X
    [4X[25Xgap>[125X [27Xa:=MinimumDistanceRandom(C,10,30); #time; # done 10 times -with fastest time!![127X[104X
    [4X[28X[128X[104X
    [4X[28X This is a probabilistic algorithm which may return the wrong answer.[128X[104X
    [4X[28X[ 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 [128X[104X
    [4X[28X        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 ] ][128X[104X
    [4X[25Xgap>[125X [27Xa[2] in C;[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27Xb:=DecreaseMinimumDistanceUpperBound(C,10,1); #time; #only done once![127X[104X
    [4X[28Xrec( mindist := 12, word := [ 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), [128X[104X
    [4X[28X      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), [128X[104X
    [4X[28X      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), [128X[104X
    [4X[28X      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), [128X[104X
    [4X[28X      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), [128X[104X
    [4X[28X      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), [128X[104X
    [4X[28X      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) ] )[128X[104X
    [4X[25Xgap>[125X [27XCodeword(b!.word) in C;[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XMinimumDistance(C); #time; #Uncomment the call to "time;"" to see performance data[127X[104X
    [4X[28X12[128X[104X
    [4X[25Xgap>[125X [27Xc:=MinimumDistanceLeon(C); #time; #Uncomment the call to "time;"" to see performance data[127X[104X
    [4X[28X12[128X[104X
    [4X[25Xgap>[125X [27XC:=RandomLinearCode(30,10,GF(3));[127X[104X
    [4X[28Xa  [30,10,?] randomly generated code over GF(3)[128X[104X
    [4X[25Xgap>[125X [27Xa:=MinimumDistanceRandom(C,10,10); #time; #Uncomment the call to "time;"" to see performance data[127X[104X
    [4X[28X[128X[104X
    [4X[28X This is a probabilistic algorithm which may return the wrong answer.[128X[104X
    [4X[28X[ 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 ] ][128X[104X
    [4X[25Xgap>[125X [27Xa[2] in C;[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XMinimumDistance(C); #time; #Uncomment the call to "time;"" to see performance data[127X[104X
    [4X[28X9[128X[104X
    [4X[25Xgap>[125X [27Xc:=MinimumDistanceLeon(C);[127X[104X
    [4X[28XCode must be binary. Quitting. [128X[104X
    [4X[28X0[128X[104X
    [4X[25Xgap>[125X [27Xa:=MinimumDistanceRandom(C,1,29); #time; #Uncomment the call to "time;"" to see performance data[127X[104X
    [4X[28X[128X[104X
    [4X[28X This is a probabilistic algorithm which may return the wrong answer.[128X[104X
    [4X[28X[ 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 ] ][128X[104X
  [4X[32X[104X
  
  [1X4.8-8 CoveringRadius[101X
  
  [33X[1;0Y[29X[2XCoveringRadius[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XCoveringRadius[110X  returns  the [13Xcovering radius[113X of a linear code [3XC[103X. This is the
  smallest  number  [22Xr[122X  with  the  property  that each element [22Xv[122X of the ambient
  vector space of [3XC[103X has at most a distance [22Xr[122X to the code [3XC[103X. So for each vector
  [22Xv[122X  there  must  be  an element [22Xc[122X of [3XC[103X with [22Xd(v,c) ≤ r[122X. The smallest covering
  radius  of  any  [22X[n,k][122X binary linear code is denoted [22Xt(n,k)[122X. A binary linear
  code with reasonable small covering radius is called a [13Xcovering code[113X.[133X
  
  [33X[0;0YIf  [3XC[103X  is a perfect code (see [2XIsPerfectCode[102X ([14X4.3-6[114X)), the covering radius is
  equal  to [22Xt[122X, the number of errors the code can correct, where [22Xd = 2t+1[122X, with
  [22Xd[122X the minimum distance of [3XC[103X (see [2XMinimumDistance[102X ([14X4.8-3[114X)).[133X
  
  [33X[0;0YIf  there exists a function called [10XSpecialCoveringRadius[110X 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.[133X
  
  [33X[0;0YIf the length of [10XBoundsCoveringRadius[110X (see [2XBoundsCoveringRadius[102X ([14X7.2-1[114X)), is
  1, then the value in[133X
  
  C.boundsCoveringRadius
  
  [33X[0;0Yis returned. Otherwise, the function[133X
  
  C.operations.CoveringRadius
  
  [33X[0;0Yis  executed,  unless  the redundancy of [3XC[103X is too large. In the last case, a
  warning is issued.[133X
  
  [33X[0;0YThe  algorithm  used to compute the covering radius is the following. First,
  [10XCosetLeadersMatFFE[110X  is  used  to  compute  the  list of coset leaders (which
  returns  a  codeword  in  each  coset  of [22XGF(q)^n/C[122X of minimum weight). Then
  [10XWeightVecFFE[110X  is  used to compute the weight of each of these coset leaders.
  The program returns the maximum of these weights.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XH := RandomLinearCode(10, 5, GF(2));[127X[104X
    [4X[28Xa  [10,5,?] randomly generated code over GF(2)[128X[104X
    [4X[25Xgap>[125X [27XCoveringRadius(H);[127X[104X
    [4X[28X3[128X[104X
    [4X[25Xgap>[125X [27XH := HammingCode(4, GF(2));; IsPerfectCode(H);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XCoveringRadius(H); # Hamming codes have minimum distance 3[127X[104X
    [4X[28X1[128X[104X
    [4X[25Xgap>[125X [27XCoveringRadius(ReedSolomonCode(7,4));[127X[104X
    [4X[28X3[128X[104X
    [4X[25Xgap>[125X [27XCoveringRadius( BCHCode( 17, 3, GF(2) ) );[127X[104X
    [4X[28X3[128X[104X
    [4X[25Xgap>[125X [27XCoveringRadius( HammingCode( 5, GF(2) ) );[127X[104X
    [4X[28X1[128X[104X
    [4X[25Xgap>[125X [27XC := ReedMullerCode( 1, 9 );;[127X[104X
    [4X[25Xgap>[125X [27XCoveringRadius( C );[127X[104X
    [4X[28XCoveringRadius: warning, the covering radius of [128X[104X
    [4X[28Xthis code cannot be computed straightforward. [128X[104X
    [4X[28XTry to use IncreaseCoveringRadiusLowerBound( <code> ).[128X[104X
    [4X[28X(see the manual for more details).[128X[104X
    [4X[28XThe covering radius of <code> lies in the interval:[128X[104X
    [4X[28X[ 240 .. 248 ][128X[104X
  [4X[32X[104X
  
  [33X[0;0YSee  also  the  [5XGUAVA[105X commands relating to bounds on the minimum distance in
  section [14X7.2[114X.[133X
  
  [1X4.8-9 SetCoveringRadius[101X
  
  [33X[1;0Y[29X[2XSetCoveringRadius[102X( [3XC[103X, [3Xintlist[103X ) [32X function[133X
  
  [33X[0;0Y[10XSetCoveringRadius[110X  enables  the  user  to  set  the covering radius herself,
  instead  of  letting  [5XGUAVA[105X compute it. If [3Xintlist[103X is an integer, [5XGUAVA[105X 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 [3Xintlist[103X. 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.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XC := BCHCode( 17, 3, GF(2) );;[127X[104X
    [4X[25Xgap>[125X [27XBoundsCoveringRadius( C );[127X[104X
    [4X[28X[ 3, 4 ][128X[104X
    [4X[25Xgap>[125X [27XSetCoveringRadius( C, [ 2 .. 3 ] );[127X[104X
    [4X[25Xgap>[125X [27XBoundsCoveringRadius( C );[127X[104X
    [4X[28X[ [ 2, 3 ] ][128X[104X
  [4X[32X[104X
  
  
  [1X4.9 [33X[0;0YDistributions[133X[101X
  
  [1X4.9-1 MinimumWeightWords[101X
  
  [33X[1;0Y[29X[2XMinimumWeightWords[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XMinimumWeightWords[110X returns the list of minimum weight codewords of [3XC[103X.[133X
  
  [33X[0;0YThis algorithm is written in GAP and is rather slow. It is only suitable for
  small codes.[133X
  
  [33X[0;0YThis  does  not call the very fast function [10XMinimumWeight[110X (see [2XMinimumWeight[102X
  ([14X4.8-5[114X)).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XC:=HammingCode(3,GF(2));[127X[104X
    [4X[28Xa linear [7,4,3]1 Hamming (3,2) code over GF(2)[128X[104X
    [4X[25Xgap>[125X [27XMinimumWeightWords(C);[127X[104X
    [4X[28X[ [ 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 ], [128X[104X
    [4X[28X  [ 0 0 1 0 1 1 0 ], [ 0 0 1 1 0 0 1 ], [ 1 1 1 0 0 0 0 ] ][128X[104X
  [4X[32X[104X
  
  [1X4.9-2 WeightDistribution[101X
  
  [33X[1;0Y[29X[2XWeightDistribution[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XWeightDistribution[110X  returns  the  weight distribution of [3XC[103X, as a vector. The
  [22Xi^th[122X element of this vector contains the number of elements of [3XC[103X with weight
  [22Xi-1[122X.  For  linear  codes,  the  weight  distribution  is  equal to the inner
  distribution   (see   [2XInnerDistribution[102X   ([14X4.9-3[114X)).   If  [22Xw[122X  is  the  weight
  distribution of a linear code [3XC[103X, it must have the zero codeword, so [22Xw[1] = 1[122X
  (one word of weight 0).[133X
  
  [33X[0;0YSome   codes,   such   as   the   Hamming  codes,  have  precomputed  weight
  distributions.  For  others,  the  program  WeightDistribution calls the GAP
  program  [10XDistancesDistributionMatFFEVecFFE[110X,  which is written in C. See also
  [10XCodeWeightEnumerator[110X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XWeightDistribution( ConferenceCode(9) );[127X[104X
    [4X[28X[ 1, 0, 0, 0, 0, 18, 0, 0, 0, 1 ][128X[104X
    [4X[25Xgap>[125X [27XWeightDistribution( RepetitionCode( 7, GF(4) ) );[127X[104X
    [4X[28X[ 1, 0, 0, 0, 0, 0, 0, 3 ][128X[104X
    [4X[25Xgap>[125X [27XWeightDistribution( WholeSpaceCode( 5, GF(2) ) );[127X[104X
    [4X[28X[ 1, 5, 10, 10, 5, 1 ][128X[104X
  [4X[32X[104X
  
  [1X4.9-3 InnerDistribution[101X
  
  [33X[1;0Y[29X[2XInnerDistribution[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XInnerDistribution[110X  returns  the inner distribution of [3XC[103X. The [22Xi^th[122X element of
  the  vector  contains the average number of elements of [3XC[103X at distance [22Xi-1[122X to
  an  element  of  [3XC[103X. For linear codes, the inner distribution is equal to the
  weight distribution (see [2XWeightDistribution[102X ([14X4.9-2[114X)).[133X
  
  [33X[0;0YSuppose  [22Xw[122X  is  the  inner  distribution  of  [3XC[103X. Then [22Xw[1] = 1[122X, because each
  element  of [3XC[103X has exactly one element at distance zero (the element itself).
  The  minimum  distance  of  [3XC[103X  is  the smallest value [22Xd > 0[122X with [22Xw[d+1] ≠ 0[122X,
  because  a  distance  between  zero  and [22Xd[122X never occurs. See [2XMinimumDistance[102X
  ([14X4.8-3[114X).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XInnerDistribution( ConferenceCode(9) );[127X[104X
    [4X[28X[ 1, 0, 0, 0, 63/5, 9/5, 18/5, 0, 9/10, 1/10 ][128X[104X
    [4X[25Xgap>[125X [27XInnerDistribution( RepetitionCode( 7, GF(4) ) );[127X[104X
    [4X[28X[ 1, 0, 0, 0, 0, 0, 0, 3 ][128X[104X
  [4X[32X[104X
  
  [1X4.9-4 DistancesDistribution[101X
  
  [33X[1;0Y[29X[2XDistancesDistribution[102X( [3XC[103X, [3Xw[103X ) [32X function[133X
  
  [33X[0;0Y[10XDistancesDistribution[110X  returns  the  distribution  of  the  distances of all
  elements  of [3XC[103X to a codeword [3Xw[103X in the same vector space. The [22Xi^th[122X element of
  the distance distribution is the number of codewords of [3XC[103X that have distance
  [22Xi-1[122X  to  [3Xw[103X. The smallest value [22Xd[122X with [22Xw[d+1] ≠ 0[122X, is defined as the [13Xdistance
  to[113X [3XC[103X (see [2XMinimumDistance[102X ([14X4.8-3[114X)).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XH := HadamardCode(20);[127X[104X
    [4X[28Xa (20,40,10)6..8 Hadamard code of order 20 over GF(2)[128X[104X
    [4X[25Xgap>[125X [27Xc := Codeword("10110101101010010101", H);[127X[104X
    [4X[28X[ 1 0 1 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 ][128X[104X
    [4X[25Xgap>[125X [27XDistancesDistribution(H, c);[127X[104X
    [4X[28X[ 0, 0, 0, 0, 0, 1, 0, 7, 0, 12, 0, 12, 0, 7, 0, 1, 0, 0, 0, 0, 0 ][128X[104X
    [4X[25Xgap>[125X [27XMinimumDistance(H, c); # distance to H [127X[104X
    [4X[28X5[128X[104X
  [4X[32X[104X
  
  [1X4.9-5 OuterDistribution[101X
  
  [33X[1;0Y[29X[2XOuterDistribution[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0YThe  function [10XOuterDistribution[110X returns a list of length [22Xq^n[122X, where [22Xq[122X is the
  size  of  the  base field of [3XC[103X and [22Xn[122X is the word length. The elements of the
  list  consist  of  pairs,  the  first coordinate being an element of [22XGF(q)^n[122X
  (this  is a codeword type) and the second coordinate being a distribution of
  distances  to  the  code (a list of integers). This table is [13Xvery[113X large, and
  for  [22Xn  >  20[122X  it will not fit in the memory of most computers. The function
  [10XDistancesDistribution[110X  (see  [2XDistancesDistribution[102X  ([14X4.9-4[114X))  can be used to
  calculate one entry of the list.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XC := RepetitionCode( 3, GF(2) );[127X[104X
    [4X[28Xa cyclic [3,1,3]1 repetition code over GF(2)[128X[104X
    [4X[25Xgap>[125X [27XOD := OuterDistribution(C);[127X[104X
    [4X[28X[ [ [ 0 0 0 ], [ 1, 0, 0, 1 ] ], [ [ 1 1 1 ], [ 1, 0, 0, 1 ] ], [128X[104X
    [4X[28X  [ [ 0 0 1 ], [ 0, 1, 1, 0 ] ], [ [ 1 1 0 ], [ 0, 1, 1, 0 ] ], [128X[104X
    [4X[28X  [ [ 1 0 0 ], [ 0, 1, 1, 0 ] ], [ [ 0 1 1 ], [ 0, 1, 1, 0 ] ], [128X[104X
    [4X[28X  [ [ 0 1 0 ], [ 0, 1, 1, 0 ] ], [ [ 1 0 1 ], [ 0, 1, 1, 0 ] ] ][128X[104X
    [4X[25Xgap>[125X [27XWeightDistribution(C) = OD[1][2];[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XDistancesDistribution( C, Codeword("110") ) = OD[4][2];[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  
  [1X4.10 [33X[0;0YDecoding Functions[133X[101X
  
  [1X4.10-1 Decode[101X
  
  [33X[1;0Y[29X[2XDecode[102X( [3XC[103X, [3Xr[103X ) [32X function[133X
  
  [33X[0;0Y[10XDecode[110X  decodes [3Xr[103X (a 'received word') with respect to code [3XC[103X and returns the
  `message  word' (i.e., the information digits associated to the codeword [22Xc ∈
  C[122X  closest  to  [3Xr[103X).  Here  [3Xr[103X can be a [5XGUAVA[105X codeword or a list of codewords.
  First,  possible  errors in [3Xr[103X are corrected, then the codeword is decoded to
  an  [13Xinformation codeword[113X [22Xm[122X (and not an element of [3XC[103X). 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  [3XC[103X  is  linear and no special decoder field has been set then
  syndrome  decoding  is  used.  Otherwise (when [3XC[103X is non-linear), the nearest
  neighbor decoding algorithm is used (which is very slow).[133X
  
  [33X[0;0YA special decoder can be created by defining a function[133X
  
  C!.SpecialDecoder := function(C, r) ... end;
  
  [33X[0;0YThe  function  uses the arguments [3XC[103X (the code record itself) and [3Xr[103X (a vector
  of the codeword type) to decode [3Xr[103X to an information vector. A normal decoder
  would  take  a  codeword [3Xr[103X of the same word length and field as [3XC[103X, and would
  return  an  information  vector of length [22Xk[122X, the dimension of [3XC[103X. The user is
  not restricted to these normal demands though, and can for instance define a
  decoder for non-linear codes.[133X
  
  [33X[0;0YEncoding  is  done  by multiplying the information vector with the code (see
  [14X4.2[114X).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XC := HammingCode(3);[127X[104X
    [4X[28Xa linear [7,4,3]1 Hamming (3,2) code over GF(2)[128X[104X
    [4X[25Xgap>[125X [27Xc := "1010"*C;                    # encoding[127X[104X
    [4X[28X[ 1 0 1 1 0 1 0 ][128X[104X
    [4X[25Xgap>[125X [27XDecode(C, c);                     # decoding[127X[104X
    [4X[28X[ 1 0 1 0 ][128X[104X
    [4X[25Xgap>[125X [27XDecode(C, Codeword("0010101")); # one error corrected[127X[104X
    [4X[28X[ 1 1 0 1 ][128X[104X
    [4X[25Xgap>[125X [27XC!.SpecialDecoder := function(C, c)[127X[104X
    [4X[25X>[125X [27Xreturn NullWord(Dimension(C));[127X[104X
    [4X[25X>[125X [27Xend;[127X[104X
    [4X[28Xfunction( C, c ) ... end[128X[104X
    [4X[25Xgap>[125X [27XDecode(C, c); # new decoder always returns null word [127X[104X
    [4X[28X[ 0 0 0 0 ][128X[104X
  [4X[32X[104X
  
  [1X4.10-2 Decodeword[101X
  
  [33X[1;0Y[29X[2XDecodeword[102X( [3XC[103X, [3Xr[103X ) [32X function[133X
  
  [33X[0;0Y[10XDecodeword[110X  decodes [3Xr[103X (a 'received word') with respect to code [3XC[103X and returns
  the codeword [22Xc ∈ C[122X closest to [3Xr[103X. Here [3Xr[103X can be a [5XGUAVA[105X 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 [3XC[103X is linear and no special decoder field has
  been  set  then  syndrome decoding is used. Otherwise, when [3XC[103X is non-linear,
  the  nearest  neighbor  algorithm has been implemented (which should only be
  used for small-sized codes).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XC := HammingCode(3);[127X[104X
    [4X[28Xa linear [7,4,3]1 Hamming (3,2) code over GF(2)[128X[104X
    [4X[25Xgap>[125X [27Xc := "1010"*C;                    # encoding[127X[104X
    [4X[28X[ 1 0 1 1 0 1 0 ][128X[104X
    [4X[25Xgap>[125X [27XDecodeword(C, c);                     # decoding[127X[104X
    [4X[28X[ 1 0 1 1 0 1 0 ][128X[104X
    [4X[25Xgap>[125X [27XR:=PolynomialRing(GF(11),["t"]);[127X[104X
    [4X[28XGF(11)[t][128X[104X
    [4X[25Xgap>[125X [27XP:=List([1,3,4,5,7],i->Z(11)^i);[127X[104X
    [4X[28X[ Z(11), Z(11)^3, Z(11)^4, Z(11)^5, Z(11)^7 ][128X[104X
    [4X[25Xgap>[125X [27XC:=GeneralizedReedSolomonCode(P,3,R);[127X[104X
    [4X[28Xa linear [5,3,1..3]2  generalized Reed-Solomon code over GF(11)[128X[104X
    [4X[25Xgap>[125X [27XMinimumDistance(C);[127X[104X
    [4X[28X3[128X[104X
    [4X[25Xgap>[125X [27Xc:=Random(C);[127X[104X
    [4X[28X[ 0 9 6 2 1 ][128X[104X
    [4X[25Xgap>[125X [27Xv:=Codeword("09620");[127X[104X
    [4X[28X[ 0 9 6 2 0 ][128X[104X
    [4X[25Xgap>[125X [27XGeneralizedReedSolomonDecoderGao(C,v);[127X[104X
    [4X[28X[ 0 9 6 2 1 ][128X[104X
    [4X[25Xgap>[125X [27XDecodeword(C,v); # calls the special interpolation decoder[127X[104X
    [4X[28X[ 0 9 6 2 1 ][128X[104X
    [4X[25Xgap>[125X [27XG:=GeneratorMat(C);[127X[104X
    [4X[28X[ [ Z(11)^0, 0*Z(11), 0*Z(11), Z(11)^8, Z(11)^9 ], [128X[104X
    [4X[28X  [ 0*Z(11), Z(11)^0, 0*Z(11), Z(11)^0, Z(11)^8 ], [128X[104X
    [4X[28X  [ 0*Z(11), 0*Z(11), Z(11)^0, Z(11)^3, Z(11)^8 ] ][128X[104X
    [4X[25Xgap>[125X [27XC1:=GeneratorMatCode(G,GF(11));[127X[104X
    [4X[28Xa linear [5,3,1..3]2 code defined by generator matrix over GF(11)[128X[104X
    [4X[25Xgap>[125X [27XDecodeword(C,v); # calls syndrome decoding[127X[104X
    [4X[28X[ 0 9 6 2 1 ][128X[104X
  [4X[32X[104X
  
  [1X4.10-3 GeneralizedReedSolomonDecoderGao[101X
  
  [33X[1;0Y[29X[2XGeneralizedReedSolomonDecoderGao[102X( [3XC[103X, [3Xr[103X ) [32X function[133X
  
  [33X[0;0Y[10XGeneralizedReedSolomonDecoderGao[110X decodes [3Xr[103X (a 'received word') to a codeword
  [22Xc  ∈  C[122X in a generalized Reed-Solomon code [3XC[103X (see [2XGeneralizedReedSolomonCode[102X
  ([14X5.6-2[114X)),  closest to [3Xr[103X. Here [3Xr[103X must be a [5XGUAVA[105X 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 [22Xc[122X.[133X
  
  [33X[0;0YFor  long  codes,  this  method is faster in practice than the interpolation
  method used in [10XDecodeword[110X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XR:=PolynomialRing(GF(11),["t"]);[127X[104X
    [4X[28XGF(11)[t][128X[104X
    [4X[25Xgap>[125X [27XP:=List([1,3,4,5,7],i->Z(11)^i);[127X[104X
    [4X[28X[ Z(11), Z(11)^3, Z(11)^4, Z(11)^5, Z(11)^7 ][128X[104X
    [4X[25Xgap>[125X [27XC:=GeneralizedReedSolomonCode(P,3,R);[127X[104X
    [4X[28Xa linear [5,3,1..3]2  generalized Reed-Solomon code over GF(11)[128X[104X
    [4X[25Xgap>[125X [27XMinimumDistance(C);[127X[104X
    [4X[28X3[128X[104X
    [4X[25Xgap>[125X [27Xc:=Random(C);[127X[104X
    [4X[28X[ 0 9 6 2 1 ][128X[104X
    [4X[25Xgap>[125X [27Xv:=Codeword("09620");[127X[104X
    [4X[28X[ 0 9 6 2 0 ][128X[104X
    [4X[25Xgap>[125X [27XGeneralizedReedSolomonDecoderGao(C,v); [127X[104X
    [4X[28X[ 0 9 6 2 1 ][128X[104X
  [4X[32X[104X
  
  [1X4.10-4 GeneralizedReedSolomonListDecoder[101X
  
  [33X[1;0Y[29X[2XGeneralizedReedSolomonListDecoder[102X( [3XC[103X, [3Xr[103X, [3Xtau[103X ) [32X function[133X
  
  [33X[0;0Y[10XGeneralizedReedSolomonListDecoder[110X  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 [3Xtau[103X from [3Xr[103X (a
  'received  word').  [3XC[103X  must  be  a  generalized  Reed-Solomon  code  [3XC[103X  (see
  [2XGeneralizedReedSolomonCode[102X ([14X5.6-2[114X)) and [3Xr[103X must be a [5XGUAVA[105X codeword.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XF:=GF(16);[127X[104X
    [4X[28XGF(2^4)[128X[104X
    [4X[25Xgap>[125X [27Xa:=PrimitiveRoot(F);; b:=a^7;; b^4+b^3+1; [127X[104X
    [4X[28X0*Z(2)[128X[104X
    [4X[25Xgap>[125X [27XPts:=List([0..14],i->b^i);[127X[104X
    [4X[28X[ 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, [128X[104X
    [4X[28X  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), [128X[104X
    [4X[28X  Z(2^4)^8 ][128X[104X
    [4X[25Xgap>[125X [27Xx:=X(F);;[127X[104X
    [4X[25Xgap>[125X [27XR1:=PolynomialRing(F,[x]);;[127X[104X
    [4X[25Xgap>[125X [27Xvars:=IndeterminatesOfPolynomialRing(R1);;[127X[104X
    [4X[25Xgap>[125X [27Xy:=X(F,vars);;[127X[104X
    [4X[25Xgap>[125X [27XR2:=PolynomialRing(F,[x,y]);;[127X[104X
    [4X[25Xgap>[125X [27XC:=GeneralizedReedSolomonCode(Pts,3,R1); [127X[104X
    [4X[28Xa linear [15,3,1..13]10..12  generalized Reed-Solomon code over GF(16)[128X[104X
    [4X[25Xgap>[125X [27XMinimumDistance(C); ## 6 error correcting[127X[104X
    [4X[28X13[128X[104X
    [4X[25Xgap>[125X [27Xz:=Zero(F);;[127X[104X
    [4X[25Xgap>[125X [27Xr:=[z,z,z,z,z,z,z,z,b^6,b^2,b^5,b^14,b,b^7,b^11];; [127X[104X
    [4X[25Xgap>[125X [27Xr:=Codeword(r);[127X[104X
    [4X[28X[ 0 0 0 0 0 0 0 0 a^12 a^14 a^5 a^8 a^7 a^4 a^2 ][128X[104X
    [4X[25Xgap>[125X [27Xcs:=GeneralizedReedSolomonListDecoder(C,r,2); #time; #Uncomment the call to "time;"" to see performance data[127X[104X
    [4X[28X[ [ 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 ], [128X[104X
    [4X[28X  [ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ] ][128X[104X
    [4X[25Xgap>[125X [27Xc1:=cs[1]; c1 in C;[127X[104X
    [4X[28X[ 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 ][128X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27Xc2:=cs[2]; c2 in C;[127X[104X
    [4X[28X[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ][128X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XWeightCodeword(c1-r);[127X[104X
    [4X[28X7[128X[104X
    [4X[25Xgap>[125X [27XWeightCodeword(c2-r);[127X[104X
    [4X[28X7[128X[104X
  [4X[32X[104X
  
  [1X4.10-5 BitFlipDecoder[101X
  
  [33X[1;0Y[29X[2XBitFlipDecoder[102X( [3XC[103X, [3Xr[103X ) [32X function[133X
  
  [33X[0;0YThe  iterative  decoding  method [10XBitFlipDecoder[110X must only be applied to LDPC
  codes.  For  more information on LDPC codes, refer to Section [14X5.8[114X. For these
  codes,  [10XBitFlipDecoder[110X  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].[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XC:=HammingCode(4,GF(2));[127X[104X
    [4X[28Xa linear [15,11,3]1 Hamming (4,2) code over GF(2)[128X[104X
    [4X[25Xgap>[125X [27Xc:=Random(C);[127X[104X
    [4X[28X[ 0 0 0 1 0 0 1 0 0 1 1 0 1 0 1 ][128X[104X
    [4X[25Xgap>[125X [27Xv:=List(c);[127X[104X
    [4X[28X[ 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),[128X[104X
    [4X[28X  Z(2)^0, Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0 ][128X[104X
    [4X[25Xgap>[125X [27Xv[1]:=Z(2)+v[1]; # flip 1st bit of c to create an error[127X[104X
    [4X[28XZ(2)^0[128X[104X
    [4X[25Xgap>[125X [27Xv:=Codeword(v);[127X[104X
    [4X[28X[ 1 0 0 1 0 0 1 0 0 1 1 0 1 0 1 ][128X[104X
    [4X[25Xgap>[125X [27XBitFlipDecoder(C,v);[127X[104X
    [4X[28X[ 0 0 0 1 0 0 1 0 0 1 1 0 1 0 1 ][128X[104X
  [4X[32X[104X
  
  [1X4.10-6 NearestNeighborGRSDecodewords[101X
  
  [33X[1;0Y[29X[2XNearestNeighborGRSDecodewords[102X( [3XC[103X, [3Xv[103X, [3Xdist[103X ) [32X function[133X
  
  [33X[0;0Y[10XNearestNeighborGRSDecodewords[110X  finds  all generalized Reed-Solomon codewords
  within  distance  [3Xdist[103X  from  [3Xv[103X [13Xand[113X the associated polynomial, using ``brute
  force''.  Input: [3Xv[103X is a received vector (a [5XGUAVA[105X codeword), [3XC[103X is a GRS code,
  [3Xdist[103X  >  0  is  the  distance from [3Xv[103X to search in [3XC[103X. Output: a list of pairs
  [22X[c,f(x)][122X, where [22Xwt(c-v)≤ dist-1[122X and [22Xc = (f(x_1),...,f(x_n))[122X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XF:=GF(16);[127X[104X
    [4X[28XGF(2^4)[128X[104X
    [4X[25Xgap>[125X [27Xa:=PrimitiveRoot(F);; b:=a^7; b^4+b^3+1;[127X[104X
    [4X[28XZ(2^4)^7[128X[104X
    [4X[28X0*Z(2)[128X[104X
    [4X[25Xgap>[125X [27XPts:=List([0..14],i->b^i);[127X[104X
    [4X[28X[ 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, [128X[104X
    [4X[28X  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), [128X[104X
    [4X[28X  Z(2^4)^8 ][128X[104X
    [4X[25Xgap>[125X [27Xx:=X(F);;[127X[104X
    [4X[25Xgap>[125X [27XR1:=PolynomialRing(F,[x]);;[127X[104X
    [4X[25Xgap>[125X [27Xvars:=IndeterminatesOfPolynomialRing(R1);;[127X[104X
    [4X[25Xgap>[125X [27Xy:=X(F,vars);;[127X[104X
    [4X[25Xgap>[125X [27XR2:=PolynomialRing(F,[x,y]);;[127X[104X
    [4X[25Xgap>[125X [27XC:=GeneralizedReedSolomonCode(Pts,3,R1);[127X[104X
    [4X[28Xa linear [15,3,1..13]10..12  generalized Reed-Solomon code over GF(16)[128X[104X
    [4X[25Xgap>[125X [27XMinimumDistance(C); # 6 error correcting[127X[104X
    [4X[28X13[128X[104X
    [4X[25Xgap>[125X [27Xz:=Zero(F);[127X[104X
    [4X[28X0*Z(2)[128X[104X
    [4X[25Xgap>[125X [27Xr:=[z,z,z,z,z,z,z,z,b^6,b^2,b^5,b^14,b,b^7,b^11];; # 7 errors[127X[104X
    [4X[25Xgap>[125X [27Xr:=Codeword(r);[127X[104X
    [4X[28X[ 0 0 0 0 0 0 0 0 a^12 a^14 a^5 a^8 a^7 a^4 a^2 ][128X[104X
    [4X[25Xgap>[125X [27Xcs:=NearestNeighborGRSDecodewords(C,r,7);[127X[104X
    [4X[28X[ [ [ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ], 0*Z(2) ], [128X[104X
    [4X[28X  [ [ 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 ], [128X[104X
    [4X[28X      x_1+Z(2)^0 ] ][128X[104X
  [4X[32X[104X
  
  [1X4.10-7 NearestNeighborDecodewords[101X
  
  [33X[1;0Y[29X[2XNearestNeighborDecodewords[102X( [3XC[103X, [3Xv[103X, [3Xdist[103X ) [32X function[133X
  
  [33X[0;0Y[10XNearestNeighborDecodewords[110X  finds  all  codewords  in a linear code [3XC[103X within
  distance  [3Xdist[103X  from [3Xv[103X, using ``brute force''. Input: [3Xv[103X is a received vector
  (a  [5XGUAVA[105X  codeword), [3XC[103X is a linear code, [3Xdist[103X > 0 is the distance from [3Xv[103X to
  search in [3XC[103X. Output: a list of [22Xc ∈ C[122X, where [22Xwt(c-v)≤ dist-1[122X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XF:=GF(16);[127X[104X
    [4X[28XGF(2^4)[128X[104X
    [4X[25Xgap>[125X [27Xa:=PrimitiveRoot(F);; b:=a^7; b^4+b^3+1;[127X[104X
    [4X[28XZ(2^4)^7[128X[104X
    [4X[28X0*Z(2)[128X[104X
    [4X[25Xgap>[125X [27XPts:=List([0..14],i->b^i);[127X[104X
    [4X[28X[ 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, [128X[104X
    [4X[28X  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), [128X[104X
    [4X[28X  Z(2^4)^8 ][128X[104X
    [4X[25Xgap>[125X [27Xx:=X(F);;[127X[104X
    [4X[25Xgap>[125X [27XR1:=PolynomialRing(F,[x]);;[127X[104X
    [4X[25Xgap>[125X [27Xvars:=IndeterminatesOfPolynomialRing(R1);;[127X[104X
    [4X[25Xgap>[125X [27Xy:=X(F,vars);;[127X[104X
    [4X[25Xgap>[125X [27XR2:=PolynomialRing(F,[x,y]);;[127X[104X
    [4X[25Xgap>[125X [27XC:=GeneralizedReedSolomonCode(Pts,3,R1);[127X[104X
    [4X[28Xa linear [15,3,1..13]10..12  generalized Reed-Solomon code over GF(16)[128X[104X
    [4X[25Xgap>[125X [27XMinimumDistance(C);[127X[104X
    [4X[28X13[128X[104X
    [4X[25Xgap>[125X [27Xz:=Zero(F);[127X[104X
    [4X[28X0*Z(2)[128X[104X
    [4X[25Xgap>[125X [27Xr:=[z,z,z,z,z,z,z,z,b^6,b^2,b^5,b^14,b,b^7,b^11];;[127X[104X
    [4X[25Xgap>[125X [27Xr:=Codeword(r);[127X[104X
    [4X[28X[ 0 0 0 0 0 0 0 0 a^12 a^14 a^5 a^8 a^7 a^4 a^2 ][128X[104X
    [4X[25Xgap>[125X [27Xcs:=NearestNeighborDecodewords(C,r,7);[127X[104X
    [4X[28X[ [ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ], [128X[104X
    [4X[28X  [ 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 ] ][128X[104X
  [4X[32X[104X
  
  [1X4.10-8 Syndrome[101X
  
  [33X[1;0Y[29X[2XSyndrome[102X( [3XC[103X, [3Xv[103X ) [32X function[133X
  
  [33X[0;0Y[10XSyndrome[110X  returns  the syndrome of word [3Xv[103X with respect to a linear code [3XC[103X. [3Xv[103X
  is a codeword in the ambient vector space of [3XC[103X. If [3Xv[103X is an element of [3XC[103X, the
  syndrome  is a zero vector. The syndrome can be used for looking up an error
  vector  in the syndrome table (see [2XSyndromeTable[102X ([14X4.10-9[114X)) that is needed to
  correct an error in [22Xv[122X.[133X
  
  [33X[0;0YA  syndrome  is  not  defined for non-linear codes. [10XSyndrome[110X then returns an
  error.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XC := HammingCode(4);[127X[104X
    [4X[28Xa linear [15,11,3]1 Hamming (4,2) code over GF(2)[128X[104X
    [4X[25Xgap>[125X [27Xv := CodewordNr( C, 7 );[127X[104X
    [4X[28X[ 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 ][128X[104X
    [4X[25Xgap>[125X [27XSyndrome( C, v );[127X[104X
    [4X[28X[ 0 0 0 0 ][128X[104X
    [4X[25Xgap>[125X [27XSyndrome( C, Codeword( "000000001100111" ) );[127X[104X
    [4X[28X[ 1 1 1 1 ][128X[104X
    [4X[25Xgap>[125X [27XSyndrome( C, Codeword( "000000000000001" ) ); # the same syndrome: both codewords are in the same coset of C [127X[104X
    [4X[28X[ 1 1 1 1 ][128X[104X
  [4X[32X[104X
  
  [1X4.10-9 SyndromeTable[101X
  
  [33X[1;0Y[29X[2XSyndromeTable[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XSyndromeTable[110X returns a [13Xsyndrome table[113X of a linear code [3XC[103X, 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 [3Xv[103X with [10XSyndrome[110X (see
  [2XSyndrome[102X ([14X4.10-8[114X)), the error vector needed to correct [3Xv[103X can be found in the
  syndrome  table.  Subtracting  this vector from [3Xv[103X yields an element of [3XC[103X. To
  make  the search for the syndrome as fast as possible, the syndrome table is
  sorted according to the syndrome vectors.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XH := HammingCode(2);[127X[104X
    [4X[28Xa linear [3,1,3]1 Hamming (2,2) code over GF(2)[128X[104X
    [4X[25Xgap>[125X [27XSyndromeTable(H);[127X[104X
    [4X[28X[ [ [ 0 0 0 ], [ 0 0 ] ], [ [ 1 0 0 ], [ 0 1 ] ], [ [ 0 1 0 ], [ 1 0 ] ], [128X[104X
    [4X[28X  [ [ 0 0 1 ], [ 1 1 ] ] ][128X[104X
    [4X[25Xgap>[125X [27Xc := Codeword("101");[127X[104X
    [4X[28X[ 1 0 1 ][128X[104X
    [4X[25Xgap>[125X [27Xc in H;  # c is not an element of H[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27XSyndrome(H,c); # according to the syndrome table, the error vector [ 0 1 0 ] belongs to this syndrome[127X[104X
    [4X[28X[ 1 0 ][128X[104X
    [4X[25Xgap>[125X [27Xc - Codeword("010") in H; # so the corrected codeword is [ 1 0 1 ] - [ 0 1 0 ] = [ 1 1 1 ], this is an element of H [127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [1X4.10-10 StandardArray[101X
  
  [33X[1;0Y[29X[2XStandardArray[102X( [3XC[103X ) [32X function[133X
  
  [33X[0;0Y[10XStandardArray[110X  returns the standard array of a code [3XC[103X. This is a matrix with
  elements  of  the codeword type. It has [22Xq^r[122X rows and [22Xq^k[122X columns, where [22Xq[122X is
  the  size of the base field of [3XC[103X, [22Xr=n-k[122X is the redundancy of [3XC[103X, and [22Xk[122X is the
  dimension of [3XC[103X. The first row contains all the elements of [3XC[103X. Each other row
  contains  words  that  do  not  belong to the code, with in the first column
  their syndrome vector (see [2XSyndrome[102X ([14X4.10-8[114X)).[133X
  
  [33X[0;0YA non-linear code does not have a standard array. [10XStandardArray[110X then returns
  an error.[133X
  
  [33X[0;0YNote  that  calculating  a  standard  array  can  be  very time- and memory-
  consuming.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XStandardArray(RepetitionCode(3)); [127X[104X
    [4X[28X[ [ [ 0 0 0 ], [ 1 1 1 ] ], [ [ 0 0 1 ], [ 1 1 0 ] ], [128X[104X
    [4X[28X  [ [ 0 1 0 ], [ 1 0 1 ] ], [ [ 1 0 0 ], [ 0 1 1 ] ] ][128X[104X
  [4X[32X[104X
  
  [1X4.10-11 PermutationDecode[101X
  
  [33X[1;0Y[29X[2XPermutationDecode[102X( [3XC[103X, [3Xv[103X ) [32X function[133X
  
  [33X[0;0Y[10XPermutationDecode[110X  performs  permutation  decoding when possible and returns
  original vector and prints 'fail' when not possible.[133X
  
  [33X[0;0YThis   uses   [10XAutomorphismGroup[110X   in  the  binary  case,  and  (the  slower)
  [10XPermutationAutomorphismGroup[110X   otherwise,   to   compute   the   permutation
  automorphism  group  [22XP[122X  of [3XC[103X. The algorithm runs through the elements [22Xp[122X of [22XP[122X
  checking  if  the  weight of [22XH(p⋅ v)[122X is less than [22X(d-1)/2[122X. If it is then the
  vector  [22Xp⋅  v[122X  is  used  to  decode  [22Xv[122X:  assuming [3XC[103X is in standard form then
  [22Xc=p^-1Em[122X  is  the decoded word, where [22Xm[122X is the information digits part of [22Xp⋅
  v[122X.  If no such [22Xp[122X exists then ``fail'' is returned. See, for example, section
  10.2 of Huffman and Pless [HP03] for more details.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XC0:=HammingCode(3,GF(2));[127X[104X
    [4X[28Xa linear [7,4,3]1 Hamming (3,2) code over GF(2)[128X[104X
    [4X[25Xgap>[125X [27XG0:=GeneratorMat(C0);;[127X[104X
    [4X[25Xgap>[125X [27XG := List(G0, ShallowCopy);;[127X[104X
    [4X[25Xgap>[125X [27XPutStandardForm(G);[127X[104X
    [4X[28X()[128X[104X
    [4X[25Xgap>[125X [27XDisplay(G);[127X[104X
    [4X[28X 1 . . . . 1 1[128X[104X
    [4X[28X . 1 . . 1 . 1[128X[104X
    [4X[28X . . 1 . 1 1 .[128X[104X
    [4X[28X . . . 1 1 1 1[128X[104X
    [4X[25Xgap>[125X [27XH0:=CheckMat(C0);;[127X[104X
    [4X[25Xgap>[125X [27XDisplay(H0);[127X[104X
    [4X[28X . . . 1 1 1 1[128X[104X
    [4X[28X . 1 1 . . 1 1[128X[104X
    [4X[28X 1 . 1 . 1 . 1[128X[104X
    [4X[25Xgap>[125X [27Xc0:=Random(C0);[127X[104X
    [4X[28X[ 0 0 0 1 1 1 1 ][128X[104X
    [4X[25Xgap>[125X [27Xv01:=c0[1]+Z(2)^2;;[127X[104X
    [4X[25Xgap>[125X [27Xv1:=List(c0, ShallowCopy);;[127X[104X
    [4X[25Xgap>[125X [27Xv1[1]:=v01;;[127X[104X
    [4X[25Xgap>[125X [27Xv1:=Codeword(v1);[127X[104X
    [4X[28X[ 1 0 0 1 1 1 1 ][128X[104X
    [4X[25Xgap>[125X [27Xc1:=PermutationDecode(C0,v1);[127X[104X
    [4X[28X[ 0 0 0 1 1 1 1 ][128X[104X
    [4X[25Xgap>[125X [27Xc1=c0;[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [1X4.10-12 PermutationDecodeNC[101X
  
  [33X[1;0Y[29X[2XPermutationDecodeNC[102X( [3XC[103X, [3Xv[103X, [3XP[103X ) [32X function[133X
  
  [33X[0;0YSame  as  [10XPermutationDecode[110X  except  that  one  may  enter  the  permutation
  automorphism group [3XP[103X in as an argument, saving time. Here [3XP[103X is a subgroup of
  the symmetric group on [22Xn[122X letters, where [22Xn[122X is the word length of [3XC[103X.[133X
  
