4 Generating Codes

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 ] ]

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*I_n, 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 A_n (by replacing the 1s by 0s and the -1s by 1s).

The first kind (t=1) is created by using the rows of A_n 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 A_n (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 = 2^r, 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) 

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 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*H^T = ((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 

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 returns an (n, q², 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 q² 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 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)ⁿ.

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 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 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 

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) 

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 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 q^k.

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 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 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 [(q^r -1)/(q-1), (q^r -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 returns a binary Reed-Muller code R(r , k ) with dimension k and order r. This is a code with length 2^k and minimum distance 2^{k -r} . By definition, the r ^th order binary Reed-Muller code of length n=2^m , 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 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 a_i^j y_i. If no alpha is specified, the vector [1, a, a², ·., a^n-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 returns a Goppa code from Goppa polynomial G, having coefficients in a Galois Field GF(q^m). L must be a list of elements in GF(q^m), 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 a_i^j G(a_i), a_i 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) 

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 returns a generalized Srivastava code with parameters a, w, z, t. a = a₁, ·.·, a_n and w = w₁, ·.·, w_s are lists of n+s distinct elements of F =GF(q^m), z is a list of length n of nonzero elements of GF(q^m). 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, z_i=a_i^m 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 returns a Srivastava code with parameters a, w, mu. a = a₁, ·.·, a_n and w = w₁, ·.·, w_s are lists of n+s distinct elements of F =GF(q^m). The default for mu is 1. The Srivastava code is a generalized Srivastava code (see GeneralizedSrivastavaCode), in which z_i = a_i^mu 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 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 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 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 

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 returns a binary Golay code. This is a perfect [23,12,7] code. It is also cyclic, and has generator polynomial g(x)=1+x²+x⁴+x⁵+x⁶+x¹⁰+x¹¹. 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 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 returns a ternary Golay code. This is a perfect [11,6,5] code. It is also cyclic, and has generator polynomial g(x)=2+x²+2x³+x⁴+x⁵. 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 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 xⁿ-1. Therefore, the elements always have a degree less than n. A cyclic code is an ideal in the ring of polynomials modulo xⁿ - 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 xⁿ -1.

The check polynomial is the polynomial h(x) with g(x)*h(x) = xⁿ-1. Therefore it is also a divisor of xⁿ-1. The check polynomial has the property that c(x)*h(x) = 0 (mod (xⁿ-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 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 xⁿ -1, it cannot be a generator polynomial. In that case, a code is created with generator polynomial gcd( g , xⁿ -1 ), i.e. the greatest common divisor of g and xⁿ -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 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 xⁿ -1, it cannot be a check polynomial. In that case, a code is created with check polynomial gcd( h , xⁿ -1 ), i.e. the greatest common divisor of h and xⁿ -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

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(q^m). 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 

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 

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 n^th root of unity in the splitting field GF(q^m), 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 X^b , X^{b +1}, ·.·, X^{b +d -2}.

Special cases are b =1 (resulting codes are called narrow-sense BCH codes), and n =q^m-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 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 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 x²=q (mod n ). Both n and q must be primes. Its generator polynomial is the product of the polynomials x-aⁱ. 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 constructs a (binary) Fire code. G is a primitive polynomial of degree m, factor of x^r-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 x^2b-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 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 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 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 returns a list of all cyclic codes of length n over F. It constructs all possible generator polynomials from the factors of xⁿ-1. Each combination of these factors yields a generator polynomial after multiplication.

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]