[Up] [Previous] [Next] [Index]

# 3 Codes

### Sections

1. Comparisons of Codes
2. Operations for Codes
3. Boolean Functions for Codes
4. Equivalence and Isomorphism of Codes
5. Domain Functions for Codes
6. Printing and Displaying Codes
7. Generating (Check) Matrices and Polynomials
8. Parameters of Codes
9. Distributions
10. Decoding Functions

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

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

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

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

An (n,M,d) code is a code with word length n, size M and minimum distance d. If the minimum distance has not yet been calculated, the lower bound and upper bound are printed. So

    a (4,3,1..4)2..4 code over GF(2)

means a binary unrestricted code of length 4, with 3 elements and the minimum distance is greater than or equal to 1 and less than or equal to 4 and the covering radius is greater than or equal to 2 and less than or equal to 4.

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

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

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

So a linear [n, k, d]r code is a code with word length n, dimension k, minimum distance d and covering radius r.

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

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

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

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

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

Codes are printed simply by giving a small description of their parameters, the word length, size or dimension and minimum distance, followed by a short description and the base field of the code. The function `Display` gives a more detailed description, showing the construction history of the code.

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

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

Sections Comparisons of Codes and Operations for Codes describe the operations that are available for codes.

Section Boolean Functions for Codes describe the functions that tests whether an object is a code and what kind of code it is (see IsCode, IsLinearCode and IsCyclicCode) and various other boolean functions for codes.

Section Equivalence and Isomorphism of Codes describe functions about equivalence and isomorphism of codes (see IsEquivalent, CodeIsomorphism and AutomorphismGroup).

Section Domain Functions for Codes describes functions that work on domains (see Chapter Domains and their Elements in the GAP Reference Manual).

Section Printing and Displaying Codes describes functions for printing and displaying codes.

Section Generating (Check) Matrices and Polynomials describes functions that return the matrices and polynomials that define a code (see GeneratorMat, CheckMat, GeneratorPol, CheckPol, RootsOfCode).

Section Parameters of Codes describes functions that return the basic parameters of codes (see WordLength, Redundancy and MinimumDistance).

Section Distributions describes functions that return distance and weight distributions (see WeightDistribution, InnerDistribution, OuterDistribution and DistancesDistribution).

Section Decoding Functions describes functions that are related to decoding (see Decode, Syndrome, SyndromeTable and StandardArray).

In Chapters Generating Codes and Manipulating Codes we follow on, describing functions that generate and manipulate codes.

## 3.1 Comparisons of Codes

- ``C1`=` C2``
- ``C1`<>` C2``

  The equality operator `=` evaluates to `true` if the codes C1 and C2 are equal, and to `false` otherwise. The inequality operator `<>` evaluates to `true` if the codes C1 and C2 are not equal, and to `false` otherwise.

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

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

  Another way of comparing codes is `IsEquivalent`, which checks if two codes are equivalent (see IsEquivalent).

  ## 3.2 Operations for Codes

- ``C1`+` C2``

  The operator `+` evaluates to the direct sum of the codes C1 and C2. See DirectSumCode.

- ``C`+` c``
- ``c`+` C``

  The operator `+` evaluates to the coset code of code C after adding c to all elements of C. See CosetCode.

- ``C1`*` C2``

  The operator `*` evaluates to the direct product of the codes C1 and C2. See DirectProductCode.

- ``x`*` C``

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

  To decode, use the function `Decode` (see Decode).

- ``c `in` C``

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

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

- `IsSubset(`C1`,`C2`)`

  returns `true` if C2 is a subcode of C1, i.e. if C1 contains at least all the elements of C2.

      gap> IsSubset( HammingCode(3), RepetitionCode( 7 ) );
      true
      gap> IsSubset( RepetitionCode( 7 ), HammingCode( 3 ) );
      false
      gap> IsSubset( WholeSpaceCode( 7 ), HammingCode( 3 ) );
      true

  ## 3.3 Boolean Functions for Codes

- `IsCode(` obj`)`

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

      gap> IsCode( 1 );
      false
      gap> IsCode( ReedMullerCode( 2,3 ) );
      true

- `IsLinearCode(` obj`)`

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

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

- `IsCyclicCode(` obj`)`

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

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

- `IsPerfectCode(` C`)`

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

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

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

- `IsMDSCode(` C`)`

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

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

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

- `IsSelfDualCode(` C`)`

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

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

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

- `IsSelfOrthogonalCode(` C`)`

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

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

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

  ## 3.4 Equivalence and Isomorphism of Codes

- `IsEquivalent(` C1`,` C2`)`

  `IsEquivalent` returns true if C1 and C2 are equivalent codes. This is the case if C1 can be obtained from C2 by carrying out column permutations. GUAVA only handles binary codes. The external program `desauto` from J.S. Leon is used to compute the isomorphism between the codes. If C1 and C2 are equal, they are also equivalent.

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

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

- `CodeIsomorphism(` C1`,` C2`)`

  If the two codes C1 and C2 are equivalent codes (see IsEquivalent), `CodeIsomorphism` returns the permutation that transforms C1 into C2. If the codes are not equivalent, it returns `false`.

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

- `AutomorphismGroup(` C`)`

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

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

  ## 3.5 Domain Functions for Codes

  These are some GAP functions that work on `Domains` in general. Their specific effect on `Codes` is explained here.

- `IsFinite(` C`)`

  `IsFinite` is an implementation of the GAP domain function `IsFinite`. It returns true for a code C.

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

- `Size(` C`)`

  `Size` returns the size of C, the number of elements of the code. If the code is linear, the size of the code is equal to qk, where q is the size of the base field of C and k is the dimension.

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

- `LeftActingDomain(` C`)`

  `LeftActingDomain` returns the base field of a code C. Each element of C consists of elements of this base field. If the base field is F, and the word length of the code is n, then the codewords are elements of Fn. If C is a cyclic code, its elements are interpreted as polynomials with coefficients over F.

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

- `Dimension(` C`)`

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

      gap> Dimension( NullCode( 5, GF(5) ) );
      0
      gap> C := BCHCode( 15, 4, GF(4) );
      a cyclic [15,9,5]3..4 BCH code, delta=5, b=1 over GF(4)
      gap> Dimension( C );
      9
      gap> Size( C ) = Size( LeftActingDomain( C ) ) ^ Dimension( C );
      true

- `AsSSortedList(` C`)`

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

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

- `CodewordNr(` C`,` list`)`

  `CodewordNr` returns a list of codewords of C. list may be a list of integers or a single integer. For each integer of list, the corresponding codeword of C is returned. The correspondence of a number i with a codeword is determined as follows: if a list of elements of C is available, the ith element is taken. Otherwise, it is calculated by multiplication of the ith information vector by the generator matrix or generator polynomial, where the information vectors are ordered lexicographically.

  So `CodewordNr(`C`,` i`)` is equal to `AsSSortedList(`C`)[`i`]`. The latter function first calculates the set of all the elements of C and then returns the ith element of that set, whereas the former only calculates the ith codeword.

      gap> R := ReedSolomonCode(2,2);
      a cyclic [2,1,2]1 Reed-Solomon code over GF(3)
      gap> AsSSortedList(R);
      [ [ 0 0 ], [ 1 1 ], [ 2 2 ] ]
      gap> CodewordNr(R, [1,3]);
      [ [ 0 0 ], [ 2 2 ] ]
      gap> C := HadamardCode( 16 );
      a (16,32,8)5..6 Hadamard code of order 16 over GF(2)
      gap> AsSSortedList(C)[17] = CodewordNr( C, 17 );
      true

  ## 3.6 Printing and Displaying Codes

- `Print(` C`)`

  `Print` prints information about C. This is the same as typing the identifier C at the GAP-prompt.

  If the argument is an unrestricted code, information in the form

      a (<n>,<M>,<d>)<r> ... code over GF(q)

  is printed, where n is the word length, M the number of elements of the code, d the minimum distance and r the covering radius.

  If the argument is a linear code, information in the form

      a linear [<n>,<k>,<d>]<r> ... code over GF(q)

  is printed, where n is the word length, k the dimension of the code, d the minimum distance and r the covering radius.

  In all cases, if d is not yet known, it is displayed in the form

      <lowerbound>,..,<upperbound>

  and if r is not yet known, it is displayed in the same way.

  The function `Display` gives more information. See Display.

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

- `String(` C`)`

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

- `Display(` C`)`

  `Display` prints the method of construction of code C. With this history, in most cases an equal or equivalent code can be reconstructed. If C is an unmanipulated code, the result is equal to output of the function `Print` (see Print).

      gap> Display( RepetitionCode( 6, GF(3) ) );
      a cyclic [6,1,6]4 repetition code over GF(3)
      gap> C1 := ExtendedCode( HammingCode(2) );;
      gap> C2 := PuncturedCode( ReedMullerCode( 2, 3 ) );;
      gap> Display( LengthenedCode( UUVCode( C1, C2 ) ) );
      a linear [12,8,2]2..4 code, lengthened with 1 column(s) of
      a linear [11,8,1]1..2 U U+V construction code of
      U: a linear [4,1,4]2 extended code of
         a linear [3,1,3]1 Hamming (2,2) code over GF(2)
      V: a linear [7,7,1]0 punctured code of
         a cyclic [8,7,2]1 Reed-Muller (2,3) code over GF(2)

  ## 3.7 Generating (Check) Matrices and Polynomials

- `GeneratorMat(` C`)`

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

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

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

      gap> GeneratorMat( HammingCode( 3, GF(2) ) );
      [ <an immutable GF2 vector of length 7>, <an immutable GF2 vector of length 7>
          , <an immutable GF2 vector of length 7>,
        <an immutable GF2 vector of length 7> ]
      gap> GeneratorMat( RepetitionCode( 5, GF(25) ) );
      [ [ Z(5)^0, Z(5)^0, Z(5)^0, Z(5)^0, Z(5)^0 ] ]
      gap> GeneratorMat( NullCode( 14, GF(4) ) );
      [  ]

- `CheckMat(` C`)`

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

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

      gap> CheckMat( HammingCode(3, GF(2) ) );
      [ <an immutable GF2 vector of length 7>, <an immutable GF2 vector of length 7>
          , <an immutable GF2 vector of length 7> ]
      gap> CheckMat( RepetitionCode( 5, GF(25) ) );
      [ [ Z(5)^0, Z(5)^2, 0*Z(5), 0*Z(5), 0*Z(5) ],
        [ 0*Z(5), Z(5)^0, Z(5)^2, 0*Z(5), 0*Z(5) ],
        [ 0*Z(5), 0*Z(5), Z(5)^0, Z(5)^2, 0*Z(5) ],
        [ 0*Z(5), 0*Z(5), 0*Z(5), Z(5)^0, Z(5)^2 ] ]
      gap> CheckMat( WholeSpaceCode( 12, GF(4) ) );
      [  ]

- `GeneratorPol(` C`)`

  `GeneratorPol` returns the generator polynomial of C. The code consists of all multiples of the generator polynomial modulo xn-1 where n is the word length of C. The generator polynomial is determined from either the check polynomial, the generator or check matrix or the elements of C (if possible), whichever is available.

  If C is not a cyclic code, the function returns `false`.

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

- `CheckPol(` C`)`

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

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

      gap> CheckPol(GeneratorMatCode([[1, 1, 0], [0, 1, 1]], GF(2)));
      Z(2)^0+x_1+x_1^2
      gap> CheckPol(WholeSpaceCode(4, GF(2)));
      Z(2)^0+x_1^4
      gap> CheckPol(NullCode(7,GF(3)));
      Z(3)^0

- `RootsOfCode(` C`)`

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

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

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

  ## 3.8 Parameters of Codes

- `WordLength(` C`)`

  `WordLength` returns the parameter n of C, the word length of the elements. Elements of cyclic codes are polynomials of maximum degree n-1, as calculations are carried out modulo xn-1.

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

- `Redundancy(` C`)`

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

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

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

- `MinimumDistance(` C`)`

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

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

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

- `MinimumDistance(` C`,` w`)`

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

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

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

  ## 3.9 Distributions

- `WeightDistribution(` C`)`

  `WeightDistribution` returns the weight distribution of C, as a vector. The ith element of this vector contains the number of elements of C with weight i-1. For linear codes, the weight distribution is equal to the inner distribution (see InnerDistribution).

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

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

- `InnerDistribution(` C`)`

  `InnerDistribution` returns the inner distribution of C. The ith element of the vector contains the average number of elements of C at distance i-1 to an element of C. For linear codes, the inner distribution is equal to the weight distribution (see WeightDistribution).

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

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

- `OuterDistribution(` C`)`

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

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

- `DistancesDistribution(` C`,` w`)`

  `DistancesDistribution` returns a distribution of the distances of all elements of C to a codeword w in the same vector space. The ith element of the distance distribution is the number of codewords of C that have distance i-1 to w. The smallest value d with w[d+1] ¹ 0 is defined as the distance to C (see MinimumDistance).

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

  ## 3.10 Decoding Functions

- `Decode(` C`,` c`)`

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

  A special decoder can be created by defining a function

      C!.SpecialDecoder := function(C, c) ... end;

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

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

- `Syndrome(` C`,` c`)`

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

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

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

- `SyndromeTable(` C`)`

  `SyndromeTable` returns a syndrome table of a linear code C, consisting of two columns. The first column consists of the error vectors that correspond to the syndrome vectors in the second column. These vectors both are of the codeword type. After calculating the syndrome of a word c with `Syndrome` (see Syndrome), the error vector needed to correct c can be found in the syndrome table. Subtracting this vector from c yields an element of C. To make the search for the syndrome as fast as possible, the syndrome table is sorted according to the syndrome vectors.

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

- `StandardArray(` C`)`

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

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

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

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

  [Up] [Previous] [Next] [Index]