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

# 4 Generating Codes

### Sections

1. Generating Unrestricted Codes
2. Generating Linear Codes
3. Golay Codes
4. Generating Cyclic Codes

In this chapter we describe functions for generating codes.

Section Generating Unrestricted Codes describes function for generating unrestricted codes.

Section Generating Linear Codes describes function for generating linear codes.

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

## 4.1 Generating Unrestricted Codes

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

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

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

- `ElementsCode(` L`[,` Name`],` F`)`

  `ElementsCode` creates an unrestricted code of the list of elements L, in the field F. L must be a list of vectors, strings, polynomials or codewords. Name can contain a short description of the code.

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

      gap> M := Z(3)^0 * [ [1, 0, 1, 1], [2, 2, 0, 0], [0, 1, 2, 2] ];;
      gap> C := ElementsCode( M, "example code", GF(3) );
      a (4,3,1..4)2 example code over GF(3)
      gap> MinimumDistance( C );
      4
      gap> AsSSortedList( C );
      [ [ 0 1 2 2 ], [ 1 0 1 1 ], [ 2 2 0 0 ] ]

- `HadamardCode(` H`,` t`)`
- `HadamardCode(` H`)`

  In the first form `HadamardCode` returns a Hadamard code from the Hadamard matrix H, of the t th kind. In the second form, t = 3 is used.

  A Hadamard matrix is a square matrix H with H *H T = -n*In, where n is the size of H. The entries of H are either 1 or -1.

  The matrix H is first transformed into a binary matrix An (by replacing the 1s by 0s and the -1s by 1s).

  The first kind (t=1) is created by using the rows of An as elements, after deleting the first column. This is a (n-1, n, n/2) code. We use this code for creating the Hadamard code of the second kind (t=2), by adding all the complements of the already existing codewords. This results in a (n-1, 2n, n/2 -1) code. The third code (t=3) is created by using the rows of An (without cutting a column) and their complements as elements. This way, we have an (n, 2n, n/2) code. The returned code is generally an unrestricted code, but for n = 2r, the code is linear.

      gap> H4 := [[1,1,1,1],[1,-1,1,-1],[1,1,-1,-1],[1,-1,-1,1]];;
      gap> HadamardCode( H4, 1 );
      a (3,4,2)1 Hadamard code of order 4 over GF(2)
      gap> HadamardCode( H4, 2 );
      a (3,8,1)0 Hadamard code of order 4 over GF(2)
      gap> HadamardCode( H4 );
      a (4,8,2)1 Hadamard code of order 4 over GF(2)

- `HadamardCode(` n`,` t`)`
- `HadamardCode(` n`)`

  In the first form `HadamardCode` returns a Hadamard code with parameter n of the t th kind. In the second form, t =3 is used.

  When called in these forms, `HadamardCode` first creates a Hadamard matrix (see HadamardMat), of size n and then follows the same procedure as described above. Therefore the same restrictions with respect to n as for Hadamard matrices hold.

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

- `ConferenceCode(` H`)`

  `ConferenceCode` returns a code of length n -1 constructed from a symmetric conference matrix H. H must be a symmetric matrix of order n, which satisfies H*HT = ((n-1)*I. n = 2 (mod 4). The rows of 1/2(H+I+J), 1/2(-H+I+J), plus the zero and all-ones vectors form the elements of a binary non-linear (n-1, 2*n, 1/2 * (n-2)) code.

      gap> H6 := [[0,1,1,1,1,1],[1,0,1,-1,-1,1],[1,1,0,1,-1,-1],
      > [1,-1,1,0,1,-1],[1,-1,-1,1,0,1],[1,1,-1,-1,1,0]];;
      gap> C1 := ConferenceCode( H6 );
      a (5,12,2)1..4 conference code over GF(2)
      gap> IsLinearCode( C1 );
      false

- `ConferenceCode(` n`)`

  GUAVA constructs a symmetric conference matrix of order n +1 (n = 1 (mod 4)) and uses the rows of that matrix, plus the zero and all-ones vectors, to construct a binary non-linear (n, 2*(n+1), 1/2 * (n-1)) code.

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

- `MOLSCode(` n`,` q`)`
- `MOLSCode(` q`)`

  `MOLSCode` returns an (n, q2, n-1) code over `GF(`q`)`. The code is created from n-2 Mutually Orthogonal Latin Squares (MOLS) of size q * q. The default for n is 4. GUAVA can construct a MOLS code for n -2 £ q ; q must be a prime power, q > 2. If there are no n -2 MOLS, an error is signalled.

  Since each of the n -2 MOLS is a q*q matrix, we can create a code of size q2 by listing in each code element the entries that are in the same position in each of the MOLS. We precede each of these lists with the two coordinates that specify this position, making the word length become n.

  The MOLS codes are MDS codes (see IsMDSCode).

      gap> C1 := MOLSCode( 6, 5 );
      a (6,25,5)3..4 code generated by 4 MOLS of order 5 over GF(5)
      gap> mols := List( [1 .. WordLength(C1) - 2 ], function( nr )
      >       local ls, el;
      >       ls := NullMat( Size(LeftActingDomain(C1)), Size(LeftActingDomain(C1)) );
      >       for el in VectorCodeword( AsSSortedList( C1 ) ) do
      >          ls[IntFFE(el[1])+1][IntFFE(el[2])+1] := el[nr + 2];
      >       od;
      >       return ls;
      >    end );;
      gap> AreMOLS( mols );
      true
      gap> C2 := MOLSCode( 11 );
      a (4,121,3)2 code generated by 2 MOLS of order 11 over GF(11)

- `RandomCode(` n`,` M`,` F`)`

  `RandomCode` returns a random unrestricted code of size M with word length n over F. M must be less than or equal to the number of elements in the space GF(q)n.

  The function `RandomLinearCode` returns a random linear code (see RandomLinearCode).

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

- `NordstromRobinsonCode()`

  `NordstromRobinsonCode` returns a Nordstrom-Robinson code, the best code with word length n=16 and minimum distance d=6 over `GF(2)`. This is a non-linear (16, 256, 6) code.

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

- `GreedyCode(` L`,` d`,` F`)`

  `GreedyCode` returns a Greedy code with design distance d over F. The code is constructed using the Greedy algorithm on the list of vectors L. This algorithm checks each vector in L and adds it to the code if its distance to the current code is greater than or equal to d. It is obvious that the resulting code has a minimum distance of at least d.

  Note that Greedy codes are often linear codes.

  The function `LexiCode` creates a Greedy code from a basis instead of an enumerated list (see LexiCode).

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

- `LexiCode(` n`,` d`,` F`)`

  In this format, `Lexicode` returns a Lexicode with word length n, design distance d over F. The code is constructed using the Greedy algorithm on the lexicographically ordered list of all vectors of length n over F. Every time a vector is found that has a distance to the current code of at least d, it is added to the code. This results, obviously, in a code with minimum distance greater than or equal to d.

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

- `LexiCode(` B`,` d`,` F`)`

  When called in this format, `LexiCode` uses the basis B instead of the standard basis. B is a matrix of vectors over F. The code is constructed using the Greedy algorithm on the list of vectors spanned by B, ordered lexicographically with respect to B.

      gap> B := [ [Z(2)^0, 0*Z(2), 0*Z(2)], [Z(2)^0, Z(2)^0, 0*Z(2)] ];;
      gap> C := LexiCode( B, 2, GF(2) );
      a linear [3,1,2]1..2 lexicode over GF(2)

  Note that binary Lexicodes are always linear.

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

  ## 4.2 Generating Linear Codes

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

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

  The next functions we describe generate some well known codes, like Hamming codes (HammingCode), Reed-Muller codes (ReedMullerCode) and the extended Golay codes (ExtendedBinaryGolayCode and ExtendedTernaryGolayCode).

  A large and powerful family of codes are alternant codes. They are obtained by a small modification of the parity check matrix of a BCH code (see AlternantCode, GoppaCode!with list of field elements parameter, GeneralizedSrivastavaCode and SrivastavaCode).

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

- `GeneratorMatCode(` G`[,` Name`],` F`)`

  `GeneratorMatCode` returns a linear code with generator matrix G. G must be a matrix over Galois field F. Name can contain a short description of the code. The generator matrix is the basis of the elements of the code. The resulting code has word length n, dimension k if G is a k * n-matrix. If GF(q) is the field of the code, the size of the code will be qk.

  If the generator matrix does not have full row rank, the linearly dependent rows are removed. This is done by the function `BaseMat` (see BaseMat) and results in an equal code. The generator matrix can be retrieved with the function `GeneratorMat` (see GeneratorMat).

      gap> G := Z(3)^0 * [[1,0,1,2,0],[0,1,2,1,1],[0,0,1,2,1]];;
      gap> C1 := GeneratorMatCode( G, GF(3) );
      a linear [5,3,1..2]1..2 code defined by generator matrix over GF(3)
      gap> C2 := GeneratorMatCode( IdentityMat( 5, GF(2) ), GF(2) );
      a linear [5,5,1]0 code defined by generator matrix over GF(2)
      gap> GeneratorMatCode( List( AsSSortedList( NordstromRobinsonCode() ),
      > x -> VectorCodeword( x ) ), GF( 2 ) );
      a linear [16,11,1..4]2 code defined by generator matrix over GF(2)
      # This is the smallest linear code that contains the N-R code

- `CheckMatCode(` H`[,` Name`],` F`)`

  `CheckMatCode` returns a linear code with check matrix H. H must be a matrix over Galois field F. Name can contain a short description of the code. The parity check matrix is the transposed of the nullmatrix of the generator matrix of the code. Therefore, c*H T = 0 where c is an element of the code. If H is a r*n-matrix, the code has word length n, redundancy r and dimension n-r.

  If the check matrix does not have full row rank, the linearly dependent rows are removed. This is done by the function `BaseMat` (see BaseMat) and results in an equal code. The check matrix can be retrieved with the function `CheckMat` (see CheckMat).

      gap> G := Z(3)^0 * [[1,0,1,2,0],[0,1,2,1,1],[0,0,1,2,1]];;
      gap> C1 := CheckMatCode( G, GF(3) );
      a linear [5,2,1..2]2..3 code defined by check matrix over GF(3)
      gap> CheckMat(C1);
      [ [ Z(3)^0, 0*Z(3), Z(3)^0, Z(3), 0*Z(3) ],
        [ 0*Z(3), Z(3)^0, Z(3), Z(3)^0, Z(3)^0 ],
        [ 0*Z(3), 0*Z(3), Z(3)^0, Z(3), Z(3)^0 ] ]
      gap> C2 := CheckMatCode( IdentityMat( 5, GF(2) ), GF(2) );
      a cyclic [5,0,5]5 code defined by check matrix over GF(2)

- `HammingCode(` r`,` F`)`

  `HammingCode` returns a Hamming code with redundancy r over F. A Hamming code is a single-error-correcting code. The parity check matrix of a Hamming code has all nonzero vectors of length r in its columns, except for a multiplication factor. The decoding algorithm of the Hamming code (see Decode) makes use of this property.

  If q is the size of its field F, the returned Hamming code is a linear [(qr -1)/(q-1), (qr -1)/(q-1) - r , 3] code.

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

- `ReedMullerCode(` r`,` k`)`

  `ReedMullerCode` returns a binary Reed-Muller code R(r , k ) with dimension k and order r. This is a code with length 2k and minimum distance 2k -r . By definition, the r th order binary Reed-Muller code of length n=2m , for 0 £ r £ m , is the set of all vectors f, where f is a Boolean function which is a polynomial of degree at most r.

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

- `AlternantCode(` r`,` Y`,` F`)`
- `AlternantCode(` r`,` Y`,` alpha`,` F`)`

  `AlternantCode` returns an alternant code, with parameters r, Y and alpha (optional). r is the design redundancy of the code. Y and alpha are both vectors of length n from which the parity check matrix is constructed. The check matrix has entries of the form aij yi. If no alpha is specified, the vector [1, a, a2, ·., an-1] is used, where a is a primitive element of a Galois field F.

      gap> Y := [ 1, 1, 1, 1, 1, 1, 1];; a := PrimitiveUnityRoot( 2, 7 );;
      gap> alpha := List( [0..6], i -> a^i );;
      gap> C := AlternantCode( 2, Y, alpha, GF(8) );
      a linear [7,3,3..4]3..4 alternant code over GF(8)

- `GoppaCode(` G`,` L`)`

  `GoppaCode` returns a Goppa code from Goppa polynomial G, having coefficients in a Galois Field GF(qm). L must be a list of elements in GF(qm), that are not roots of G. The word length of the code is equal to the length of L. The parity check matrix contains entries of the form aij G(ai), ai in L. The function `VerticalConversionFieldMat` converts this matrix to a matrix with entries in GF(q) (see VerticalConversionFieldMat).

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

- `GoppaCode(` G`,` n`)`

  When called with parameter n, GUAVA constructs a list L of length n, such that no element of L is a root of G.

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

- `GeneralizedSrivastavaCode(` a`,` w`,` z`,` F`)`
- `GeneralizedSrivastavaCode(` a`,` w`,` z`,` t`,` F`)`

  `GeneralizedSrivastavaCode` returns a generalized Srivastava code with parameters a, w, z, t. a = a1, ·.·, an and w = w1, ·.·, ws are lists of n+s distinct elements of F =GF(qm), z is a list of length n of nonzero elements of GF(qm). The parameter t determines the designed distance: d ³ st + 1. The parity check matrix of this code has entries of the form

  | zi (ai - wl)k |

  `VerticalConversionFieldMat` converts this matrix to a matrix with entries in GF(q) (see VerticalConversionFieldMat). The default for t is 1. The original Srivastava codes (see SrivastavaCode) are a special case t=1, zi=aim for some m.

      gap> a := Filtered( AsSSortedList( GF(2^6) ), e -> e in GF(2^3) );;
      gap> w := [ Z(2^6) ];; z := List( [1..8], e -> 1 );;
      gap> C := GeneralizedSrivastavaCode( a, w, z, 1, GF(64) );
      a linear [8,2,2..5]3..4 generalized Srivastava code over GF(2)

- `SrivastavaCode(` a`,` w`,` F`)`
- `SrivastavaCode(` a`,` w`,` mu`,` F`)`

  `SrivastavaCode` returns a Srivastava code with parameters a, w, mu. a = a1, ·.·, an and w = w1, ·.·, ws are lists of n+s distinct elements of F =GF(qm). The default for mu is 1. The Srivastava code is a generalized Srivastava code (see GeneralizedSrivastavaCode), in which zi = aimu for some mu and t=1.

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

- `CordaroWagnerCode(` n`)`

  `CordaroWagnerCode` returns a binary Cordaro-Wagner code. This is a code of length n and dimension 2 having the best possible minimum distance d. This code is just a little bit less trivial than `RepetitionCode` (see RepetitionCode).

      gap> C := CordaroWagnerCode( 11 );
      a linear [11,2,7]5 Cordaro-Wagner code over GF(2)
      gap> AsSSortedList(C);
      [ [ 0 0 0 0 0 0 0 0 0 0 0 ], [ 0 0 0 0 1 1 1 1 1 1 1 ],
        [ 1 1 1 1 0 0 0 1 1 1 1 ], [ 1 1 1 1 1 1 1 0 0 0 0 ] ]

- `RandomLinearCode(` n`,` k`,` F`)`

  `RandomLinearCode` returns a random linear code with word length n, dimension k over field F.

  To create a random unrestricted code, use `RandomCode` (see RandomCode).

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

- `BestKnownLinearCode(` n`,` k`,` F`)`

  `BestKnownLinearCode` returns the best known linear code of length n, dimension k over field F. The function uses the tables described in section BoundsMinimumDistance to construct this code.

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

- `BestKnownLinearCode(` rec`)`

  In this form, rec must be a record containing the fields `lowerBound`, `upperBound` and `construction`. It uses the information in this field to construct a code. This form is meant to be used together with the function `BoundsMinimumDistance` (see BoundsMinimumDistance), if the bounds are already calculated.

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

  ## 4.3 Golay Codes

- `BinaryGolayCode()`

  `BinaryGolayCode` returns a binary Golay code. This is a perfect [23,12,7] code. It is also cyclic, and has generator polynomial g(x)=1+x2+x4+x5+x6+x10+x11. Extending it results in an extended Golay code (see ExtendedBinaryGolayCode). There's also the ternary Golay code (see TernaryGolayCode).

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

- `ExtendedBinaryGolayCode( )`

  `ExtendedBinaryGolayCode` returns an extended binary Golay code. This is a [24,12,8] code. Puncturing in the last position results in a perfect binary Golay code (see BinaryGolayCode). The code is self-dual (see IsSelfDualCode).

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

- `TernaryGolayCode()`

  `TernaryGolayCode` returns a ternary Golay code. This is a perfect [11,6,5] code. It is also cyclic, and has generator polynomial g(x)=2+x2+2x3+x4+x5. Extending it results in an extended Golay code (see ExtendedTernaryGolayCode). There's also the binary Golay code (see BinaryGolayCode).

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

- `ExtendedTernaryGolayCode( )`

  `ExtendedTernaryGolayCode` returns an extended ternary Golay code. This is a [12,6,6] code. Puncturing this code results in a perfect ternary Golay code (see TernaryGolayCode). The code is self-dual (see IsSelfDualCode).

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

  ## 4.4 Generating Cyclic Codes

  The elements of a cyclic code C are all multiples of a polynomial g(x), where calculations are carried out modulo xn-1. Therefore, the elements always have a degree less than n. A cyclic code is an ideal in the ring of polynomials modulo xn - 1. The polynomial g(x) is called the generator polynomial of C. This is the unique monic polynomial of least degree that generates C. It is a divisor of the polynomial xn -1.

  The check polynomial is the polynomial h(x) with g(x)*h(x) = xn-1. Therefore it is also a divisor of xn-1. The check polynomial has the property that c(x)*h(x) = 0 (mod (xn-1)) for every codeword c(x).

  The first two functions described generate cyclic codes from a given generator or check polynomial. All cyclic codes can be constructed using these functions.

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

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

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

- `GeneratorPolCode(` g`,` n`[,` Name`],` F`)`

  `GeneratorPolCode` creates a cyclic code with a generator polynomial g, word length n, over F. Name can contain a short description of the code.

  If g is not a divisor of xn -1, it cannot be a generator polynomial. In that case, a code is created with generator polynomial gcd( g , xn -1 ), i.e. the greatest common divisor of g and xn -1. This is a valid generator polynomial that generates the ideal (g). See Generating Cyclic Codes.

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

- `CheckPolCode(` h`,` n`[,` Name`],` F`)`

  `CheckPolCode` creates a cyclic code with a check polynomial h, word length n, over F. Name can contain a short description of the code.

  If h is not a divisor of xn -1, it cannot be a check polynomial. In that case, a code is created with check polynomial gcd( h , xn -1 ), i.e. the greatest common divisor of h and xn -1. This is a valid check polynomial that yields the same elements as the ideal (h). See Generating Cyclic Codes.

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

- `RootsCode(` n`,` list`)`

  This is the generalization of the BCH, Reed-Solomon and quadratic residue codes (see BCHCode, ReedSolomonCode and QRCode). The user can give a length of the code n and a prescribed set of zeros. The argument list must be a valid list of primitive n th roots of unity in a splitting field GF(qm). The resulting code will be over the field GF(q). The function will return the largest possible cyclic code for which the list list is a subset of the roots of the code. From this list, GUAVA calculates the entire set of roots.

      gap> a := PrimitiveUnityRoot( 3, 14 );
      Z(3^6)^52
      gap> C1 := RootsCode( 14, [ a^0, a, a^3 ] );
      a cyclic [14,7,3..6]3..7 code defined by roots over GF(3)
      gap> MinimumDistance( C1 );
      4
      gap> b := PrimitiveUnityRoot( 2, 15 );
      Z(2^4)
      gap> C2 := RootsCode( 15, [ b, b^2, b^3, b^4 ] );
      a cyclic [15,7,5]3..5 code defined by roots over GF(2)
      gap> C2 = BCHCode( 15, 5, GF(2) );
      true

- `RootsCode(` n`,` list`,` F`)`

  In this second form, the second argument is a list of integers, ranging from 0 to n-1. The resulting code will be over a field F. GUAVA calculates a primitive n th root of unity, a, in the extension field of F. It uses the set of the powers of a in the list as a prescribed set of zeros.

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

- `BCHCode(` n`,` d`,` F`)`
- `BCHCode(` n`,` b`,` d`,` F`)`

  The function `BCHCode` returns a Bose-Chaudhuri-Hockenghem code (or BCH code for short). This is the largest possible cyclic code of length n over field F, whose generator polynomial has zeros

  ab ,ab +1, ·.·, ab +d -2,

  where a is a primitive nth root of unity in the splitting field GF(qm), b is an integer > 1 and m is the multiplicative order of q modulo n. Default value for b is 1. The length n of the code and the size q of the field must be relatively prime. The generator polynomial is equal to the product of the minimal polynomials of Xb , Xb +1, ·.·, Xb +d -2.

  Special cases are b =1 (resulting codes are called narrow-sense BCH codes), and n =qm-1 (known as primitive BCH codes). GUAVA calculates the largest value of d&facute;or which the BCH code with designed distance dćoincides with the BCH code with designed distance d. This distance is called the Bose distance of the code. The true minimum distance of the code is greater than or equal to the Bose distance.

  Printed are the designed distance (to be precise, the Bose distance) `delta`, and the starting power `b`.

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

- `ReedSolomonCode(` n`,` d`)`

  `ReedSolomonCode` returns a Reed-Solomon code of length n, designed distance d. This code is a primitive narrow-sense BCH code over the field GF(q), where q=n +1. The dimension of an RS code is n -d +1. According to the Singleton bound (see UpperBoundSingleton) the dimension cannot be greater than this, so the true minimum distance of an RS code is equal to d and the code is maximum distance separable (see IsMDSCode).

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

- `QRCode(` n`,` F`)`

  `QRCode` returns a quadratic residue code. If F is a field GF(q), then q must be a quadratic residue modulo n. That is, an x exists with x2=q (mod n ). Both n and q must be primes. Its generator polynomial is the product of the polynomials x-ai. a is a primitive n th root of unity, and i is an integer in the set of quadratic residues modulo n.

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

- `FireCode(` G`,` b`)`

  `FireCode` constructs a (binary) Fire code. G is a primitive polynomial of degree m, factor of xr-1. b an integer 0 £ b £ m not divisible by r, that determines the burst length of a single error burst that can be corrected. The argument G can be a polynomial with base ring GF(2), or a list of coefficients in GF(2). The generator polynomial is defined as the product of G and x2b-1+1.

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

- `WholeSpaceCode(` n`,` F`)`

  `WholeSpaceCode` returns the cyclic whole space code of length n over F. This code consists of all polynomials of degree less than n and coefficients in F.

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

- `NullCode(` n`,` F`)`

  `NullCode` returns the zero-dimensional nullcode with length n over F. This code has only one word: the all zero word. It is cyclic though!

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

- `RepetitionCode(` n`,` F`)`

  `RepetitionCode` returns the cyclic repetition code of length n over F. The code has as many elements as F, because each codeword consists of a repetition of one of these elements.

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

- `CyclicCodes(` n`,` F`)`

  `CyclicCodes` returns a list of all cyclic codes of length n over F. It constructs all possible generator polynomials from the factors of xn-1. Each combination of these factors yields a generator polynomial after multiplication.

- `NrCyclicCodes(` n`,` F`)`

  The function `NrCyclicCodes` calculates the number of cyclic codes of length n over field F.

      gap> NrCyclicCodes( 23, GF(2) );
      8
      gap> codelist := CyclicCodes( 23, GF(2) );
      [ a cyclic [23,23,1]0 enumerated code over GF(2),
        a cyclic [23,22,1..2]1 enumerated code over GF(2),
        a cyclic [23,11,1..8]4..7 enumerated code over GF(2),
        a cyclic [23,0,23]23 enumerated code over GF(2),
        a cyclic [23,11,1..8]4..7 enumerated code over GF(2),
        a cyclic [23,12,1..7]3 enumerated code over GF(2),
        a cyclic [23,1,23]11 enumerated code over GF(2),
        a cyclic [23,12,1..7]3 enumerated code over GF(2) ]
      gap> BinaryGolayCode() in codelist;
      true
      gap> RepetitionCode( 23, GF(2) ) in codelist;
      true
      gap> CordaroWagnerCode( 23 ) in codelist;
      false    # This code is not cyclic

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