GAP (guava) - Chapter 4: Codes

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

In GUAVA, codes can be a set specified by its elements (this will be called an unrestricted code), by a generator matrix listing a set of basis elements (for a linear code) or by a generator polynomial (for 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 (except in the case where the code is a random linear codes, where these are not printed for efficiency reasons). So

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> C := ElementsCode(["1100", "1010", "0001"], "example code", GF(2) );
a (4,3,1..4)2..4 example code over GF(2) 
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. By definition, the rows of the generator matrix is a basis for the code (as a vector space over \(GF(q)\)). By definition, the rows of the parity check matrix is a basis for the dual space 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 codewords (regarded as \(n\)-tuples) are again codewords, the code is called cyclic. All elements of a cyclic code are multiples of the monic polynomial modulo a polynomial \(x^n -1\), where \(n\) is the word length of the code. Such a polynomial is called a generator polynomial The generator polynomial must divide \(x^n-1\) and its quotient is called a check polynomial. Multiplying a codeword in a cyclic code by the check polynomial yields zero (modulo the polynomial \(x^n -1\)). In GUAVA, a cyclic code can be defined by either its generator polynomial or check polynomial.

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 in fact linear. This situation occurs for example when a code is generated from a list of elements with the function ElementsCode (see ElementsCode (5.1-1)). By calling the function IsLinearCode (see IsLinearCode (4.3-4)), 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
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 actually are cyclic.

Codes are printed simply by giving a small description of their parameters, the word length, size or dimension and perhaps the minimum distance, followed by a short description and the base field of the code. The function 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 functions Decode or Decodeword. For more information about encoding and decoding, see sections 4.2 and 4.10-1.

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 4.1 and 4.2 describe the operations that are available for codes. Section 4.3 describe the functions that tests whether an object is a code and what kind of code it is (see IsCode, IsLinearCode (4.3-4) and IsCyclicCode) and various other boolean functions for codes. Section 4.4 describe functions about equivalence and isomorphism of codes (see IsEquivalent (4.4-1), CodeIsomorphism (4.4-2) and AutomorphismGroup (4.4-3)). Section 4.5 describes functions that work on domains (see Chapter "Domains and their Elements" in the GAP Reference Manual). Section 4.6 describes functions for printing and displaying codes. Section 4.7 describes functions that return the matrices and polynomials that define a code (see GeneratorMat (4.7-1), CheckMat (4.7-2), GeneratorPol (4.7-3), CheckPol (4.7-4), RootsOfCode (4.7-5)). Section 4.8 describes functions that return the basic parameters of codes (see WordLength (4.8-1), Redundancy (4.8-2) and MinimumDistance (4.8-3)). Section 4.9 describes functions that return distance and weight distributions (see WeightDistribution (4.9-2), InnerDistribution (4.9-3), OuterDistribution (4.9-5) and DistancesDistribution (4.9-4)). Section 4.10 describes functions that are related to decoding (see Decode (4.10-1), Decodeword (4.10-2), Syndrome (4.10-8), SyndromeTable (4.10-9) and StandardArray (4.10-10)). In Chapters 5. and 6. which follow, we describe functions that generate and manipulate codes.

4.1 Comparisons of Codes

4.1-1 \=

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

The equality operator is also denoted EQ, and Eq(C1,C2) is the same as C1 = C2. There is also an inequality operator, < >, or not EQ.

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

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 (4.4-1)). By the way, this called CodeIsomorphism. For the current version of GUAVA, unless one of the codes is unrestricted, this calls Leon's C program (which only works for binary linear codes and only on a unix/linux computer).

4.2 Operations for Codes

4.2-1 \+

The operator `+' evaluates to the direct sum of the codes C1 and C2. See DirectSumCode (6.2-1).

gap> C1:=RandomLinearCode(10,5);
a  [10,5,?] randomly generated code over GF(2)
gap> C2:=RandomLinearCode(9,4);
a  [9,4,?] randomly generated code over GF(2)
gap> C1+C2;
a linear [10,9,1]0..10 unknown linear code over GF(2)

4.2-2 \*

The operator `*' evaluates to the direct product of the codes C1 and C2. See DirectProductCode (6.2-3).

gap> C1 := GeneratorMatCode( [ [1, 0,0,0], [0, 1,0,0] ], GF(2) );
a linear [4,2,1]1..2 code defined by generator matrix over GF(2)
gap> C2 := GeneratorMatCode( [ [0,0,1, 1], [0,0,0, 1] ], GF(2) );
a linear [4,2,1]1..2 code defined by generator matrix over GF(2)
gap> C1*C2;
a linear [16,4,1]4..12 direct product code

4.2-3 \*

The operator m*C evaluates to the element of C belonging to information word ('message') m. Here m 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 m by the generator polynomial of C. If C is a linear code, it is equal to the multiplication of an information vector m by a generator matrix of C.

To invert this, use the function InformationWord (see InformationWord (4.2-4), which simply calls the function Decode).

gap> C := GeneratorMatCode( [ [1, 0,0,0], [0, 1,0,0] ], GF(2) );
a linear [4,2,1]1..2 code defined by generator matrix over GF(2)
gap> m:=Codeword("11");
[ 1 1 ]
gap> m*C;
[ 1 1 0 0 ]

4.2-4 InformationWord

Here C is a linear code and c is a codeword in it. The command InformationWord returns the message word (or 'information digits') \(m\) satisfying c=m*C. This command simply calls Decode, provided c in C is true. Otherwise, it returns an error.

gap> C:=HammingCode(3);
a linear [7,4,3]1 Hamming (3,2) code over GF(2)
gap> c:=Random(C);
[ 0 0 0 1 1 1 1 ]
gap> InformationWord(C,c);
[ 0 1 1 1 ]
gap> c:=Codeword("1111100");
[ 1 1 1 1 1 0 0 ]
gap> InformationWord(C,c);
Error, ERROR: codeword must belong to code
gap> C:=NordstromRobinsonCode();
a (16,256,6)4 Nordstrom-Robinson code over GF(2)
gap> c:=Random(C);
[ 0 0 0 1 0 0 0 1 0 0 1 0 1 1 0 1 ]
gap> InformationWord(C,c);
"ERROR: code must be linear"

4.3 Boolean Functions for Codes

4.3-1 in

The command c in C 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

4.3-2 IsSubset

The command IsSubset(C1,C2) returns `true' if C2 is a subcode of C1, i.e. if C1 contains 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

4.3-3 IsCode

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

4.3-4 IsLinearCode

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

4.3-5 IsCyclicCode

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

4.3-6 IsPerfectCode

IsPerfectCode(C) returns `true' if C is a perfect code. If \(C\subset GF(q)^n\) then, by definition, this means that for some positive integer \(t\), the space \(GF(q)^n\) is covered by non-overlapping spheres of (Hamming) radius \(t\) centered at the codewords in C. 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 "trivially perfect" (the binary repetition codes of odd length, the codes consisting of one word, and the codes consisting of the whole vector space), and does not have the parameters of a Hamming or Golay code, cannot be perfect (see section 1.12 in [HP03]).

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

4.3-7 IsMDSCode

IsMDSCode(C) returns true if C is a maximum distance separable (MDS) code. 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 (7.1-1)). 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 );  # verify it is an MDS code, as 6-3+1 = 4
true
gap> IsMDSCode( QRCode( 23, GF(2) ) );
false

4.3-8 IsSelfDualCode

IsSelfDualCode(C) returns `true' if C is self-dual, i.e. when C is equal to its dual code (see also DualCode (6.1-14)). A code is self-dual if it contains all vectors that its elements are orthogonal to. If a code is self-dual, it automatically is self-orthogonal (see IsSelfOrthogonalCode (4.3-9)).

If C is a non-linear code, it cannot be self-dual (the dual code is always linear), so `false' is returned. A linear code can only be self-dual when its dimension \(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

4.3-9 IsSelfOrthogonalCode

IsSelfOrthogonalCode(C) 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.)

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

4.3-10 IsDoublyEvenCode

IsDoublyEvenCode(C) returns `true' if C is a binary linear code which has codewords of weight divisible by 4 only. According to [HP03], a doubly-even code is self-orthogonal and every row in its generator matrix has weight that is divisible by 4.

gap> C:=BinaryGolayCode();
a cyclic [23,12,7]3 binary Golay code over GF(2)
gap> WeightDistribution(C);
[ 1, 0, 0, 0, 0, 0, 0, 253, 506, 0, 0, 1288, 1288, 0, 0, 506, 253, 0, 0, 0, 0, 0, 0, 1 ]
gap> IsDoublyEvenCode(C);  
false
gap> C:=ExtendedCode(C);  
a linear [24,12,8]4 extended code
gap> WeightDistribution(C);
[ 1, 0, 0, 0, 0, 0, 0, 0, 759, 0, 0, 0, 2576, 0, 0, 0, 759, 0, 0, 0, 0, 0, 0, 0, 1 ]
gap> IsDoublyEvenCode(C);  
true

4.3-11 IsSinglyEvenCode

IsSinglyEvenCode(C) returns `true' if C is a binary self-orthogonal linear code which is not doubly-even. In other words, C is a binary self-orthogonal code which has codewords of even weight.

gap> x:=Indeterminate(GF(2));                     
x_1
gap> C:=QuasiCyclicCode( [x^0, 1+x^3+x^5+x^6+x^7], 11, GF(2) );
a linear [22,11,1..6]4..7 quasi-cyclic code over GF(2)
gap> IsSelfDualCode(C);  # self-dual is a restriction of self-orthogonal
true
gap> IsDoublyEvenCode(C);
false
gap> IsSinglyEvenCode(C);
true

4.3-12 IsEvenCode

IsEvenCode(C) returns `true' if C is a binary linear code which has codewords of even weight--regardless whether or not it is self-orthogonal.

gap> C:=BinaryGolayCode();
a cyclic [23,12,7]3 binary Golay code over GF(2)
gap> IsSelfOrthogonalCode(C);
false
gap> IsEvenCode(C);
false
gap> C:=ExtendedCode(C);
a linear [24,12,8]4 extended code
gap> IsSelfOrthogonalCode(C);
true
gap> IsEvenCode(C);
true
gap> C:=ExtendedCode(QRCode(17,GF(2)));
a linear [18,9,6]3..5 extended code
gap> IsSelfOrthogonalCode(C);
false
gap> IsEvenCode(C);
true

4.3-13 IsSelfComplementaryCode

gap> IsSelfComplementaryCode( HammingCode( 3, GF(2) ) );
true
gap> IsSelfComplementaryCode( EvenWeightSubcode(
> HammingCode( 3, GF(2) ) ) );
false

4.3-14 IsAffineCode

IsAffineCode returns `true' if C is an affine code. A code is called affine if it is an affine space. In other words, a code is affine if it is a coset of a linear code.

gap> IsAffineCode( HammingCode( 3, GF(2) ) );
true
gap> IsAffineCode( CosetCode( HammingCode( 3, GF(2) ),
> Codeword([ 1, 0, 0, 0, 0, 0, 0 ]) ) );
true
gap> IsAffineCode( NordstromRobinsonCode() );
false

4.3-15 IsAlmostAffineCode

IsAlmostAffineCode returns `true' if C is an almost affine code. A code is called almost affine if the size of any punctured code of C is \(q^r\) for some \(r\), where \(q\) is the size of the alphabet of the code. Every affine code is also almost affine, and every code over \(GF(2)\) and \(GF(3)\) that is almost affine is also affine.

gap> code := ElementsCode( [ [0,0,0], [0,1,1], [0,2,2], [0,3,3],
>                             [1,0,1], [1,1,0], [1,2,3], [1,3,2],
>                             [2,0,2], [2,1,3], [2,2,0], [2,3,1],
>                             [3,0,3], [3,1,2], [3,2,1], [3,3,0] ],
>                             GF(4) );;
gap> IsAlmostAffineCode( code );
true
gap> IsAlmostAffineCode( NordstromRobinsonCode() );
false

4.4 Equivalence and Isomorphism of Codes

4.4-1 IsEquivalent

We say that C1 is permutation equivalent to C2 if C1 can be obtained from C2 by carrying out column permutations. IsEquivalent returns true if C1 and C2 are equivalent codes. At this time, IsEquivalent only handles binary codes. (The external unix/linux program desauto from J. S. Leon is called by IsEquivalent.) Of course, if C1 and C2 are equal, they are also equivalent.

More generally, we say that C1 is equivalent to C2 if C1 can be obtained from C2 by carrying out column permutations and a permutation of the alphabet.

gap> x:= Indeterminate( GF(2) );; pol:= x^3+x+1; 
x_1^3+x_1+Z(2)^0
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

# verify that H is equivalent to a Hamming code
gap> IsEquivalent(H, HammingCode(3, GF(2)));
true
gap> CodeIsomorphism(H, HammingCode(3, GF(2)));
(3,4)(5,6,7)

4.4-2 CodeIsomorphism

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

At this time, IsEquivalent only computes isomorphisms between binary codes on a linux/unix computer (since it calls Leon's C program desauto).

gap> x:= Indeterminate( GF(2) );; pol:= x^3+x+1; 
x_1^3+x_1+Z(2)^0
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

4.4-3 AutomorphismGroup

AutomorphismGroup returns the automorphism group of a linear code C. For a binary code, the automorphism group is the largest permutation group of degree \(n\) such that each permutation applied to the columns of C again yields C. GUAVA calls the external program desauto written by J. S. Leon, if it exists, to compute the automorphism group. If Leon's program is not compiled on the system (and in the default directory) then it calls instead the much slower program PermutationAutomorphismGroup.

See Leon [Leo82] for a more precise description of the method, and the guava/src/leon/doc subdirectory for for details about Leon's C programs.

The function PermutedCode permutes the columns of a code (see PermutedCode (6.1-4)).

gap> R := RepetitionCode(7,GF(2));
a cyclic [7,1,7]3 repetition code over GF(2)

# verify that every permutation keeps R identical, that is, the
# automorphism group is Sym(7)
gap> AutomorphismGroup(R);
Sym( [ 1 .. 7 ] )
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

4.4-4 PermutationAutomorphismGroup

PermutationAutomorphismGroup returns the permutation automorphism group of a linear code C. This is the largest permutation group of degree \(n\) such that each permutation applied to the columns of C again yields C. It is written in GAP, so is much slower than AutomorphismGroup.

When C is binary PermutationAutomorphismGroup does not call AutomorphismGroup, even though they agree mathematically in that case. This way PermutationAutomorphismGroup can be called on any platform which runs GAP.

The older name for this command, PermutationGroup, will become obsolete in the next version of GAP.

gap> R := RepetitionCode(3,GF(3));
a cyclic [3,1,3]2 repetition code over GF(3)
gap> G:=PermutationAutomorphismGroup(R);;
gap> G=SymmetricGroup(3);
true

4.5 Domain Functions for Codes

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

4.5-1 IsFinite

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

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

4.5-2 Size

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 \(q^k\), 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

4.5-3 LeftActingDomain

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 \(F^n\). 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)

4.5-4 Dimension

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

4.5-5 AsSSortedList

AsSSortedList (as strictly sorted list) returns an immutable, duplicate free list of the elements of C. For a finite field \(GF(q)\) generated by powers of \(Z(q)\), the ordering on

is that determined by the exponents \(i\). These elements are of the type codeword (see Codeword (3.1-1)). 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 (3.1-2)).

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

4.6 Printing and Displaying Codes

4.6-1 Print

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

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.

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

Except for codes produced by RandomLinearCode, if d is not yet known, it is displayed in the form

and if r is not yet known, it is displayed in the same way. For certain ranges of \(n\), the values of lowerbound and upperbound are obtained from tables.

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

4.6-2 String

String returns information about C in a string. This function is used by Print.

gap> x:= Indeterminate( GF(3) );; pol:= x^2+1;
x_1^2+Z(3)^0
gap> Factors(pol);
[ x_1^2+Z(3)^0 ]
gap> H := GeneratorPolCode( pol, 8, GF(3));
a cyclic [8,6,1..2]1..2 code defined by generator polynomial over GF(3)
gap> String(H);
"a cyclic [8,6,1..2]1..2 code defined by generator polynomial over GF(3)"

4.6-3 Display

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 (4.6-1)).

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)

4.6-4 DisplayBoundsInfo

DisplayBoundsInfo prints the method of construction of the code \(C\) indicated in bds:= BoundsMinimumDistance( n, k, GF(q) ).

gap> bounds := BoundsMinimumDistance( 20, 17, GF(4) );
gap> DisplayBoundsInfo(bounds);
an optimal linear [20,17,d] code over GF(4) has d=3
--------------------------------------------------------------------------------------------------
Lb(20,17)=3, by shortening of:
Lb(21,18)=3, by applying construction B to a [81,77,3] code
Lb(81,77)=3, by shortening of:
Lb(85,81)=3, reference: Ham
--------------------------------------------------------------------------------------------------
Ub(20,17)=3, by considering shortening to:
Ub(7,4)=3, by considering puncturing to:
Ub(6,4)=2, by construction B applied to:
Ub(2,1)=2, repetition code
--------------------------------------------------------------------------------------------------
Reference Ham:
%T this reference is unknown, for more info
%T contact A.E. Brouwer (aeb@cwi.nl)

4.7 Generating (Check) Matrices and Polynomials

4.7-1 GeneratorMat

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.

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> Display(last);
 1 1 1 . . . .
 1 . . 1 1 . .
 . 1 . 1 . 1 .
 1 1 . 1 . . 1
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) ) );
[  ]

4.7-2 CheckMat

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.

gap> CheckMat( HammingCode(3, GF(2) ) );
[ [ 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0, Z(2)^0, Z(2)^0, Z(2)^0 ], 
  [ 0*Z(2), Z(2)^0, Z(2)^0, 0*Z(2), 0*Z(2), Z(2)^0, Z(2)^0 ],
  [ Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0 ] ]
gap> Display(last);
 . . . 1 1 1 1
 . 1 1 . . 1 1
 1 . 1 . 1 . 1
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) ) );
[  ]

4.7-3 GeneratorPol

GeneratorPol returns the generator polynomial of C. The code consists of all multiples of the generator polynomial modulo \(x^{n}-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.

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

4.7-4 CheckPol

CheckPol returns the check polynomial of C. The code consists of all polynomials \(f\) with

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.

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

4.7-5 RootsOfCode

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(q^m)\), \(m\) is the multiplicative order of the size of the base field of the code, modulo the word length.

The reverse process, constructing a code from a set of roots, can be carried out by the function RootsCode (see RootsCode (5.5-3)).

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

4.8 Parameters of Codes

4.8-1 WordLength

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 \(x^{n}-1\).

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

4.8-2 Redundancy

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

4.8-3 MinimumDistance

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 (3.6-2)) 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] \neq 0\), where \(w=(w[1],w[2],...,w[n])\) is the weight distribution of C (see WeightDistribution (4.9-2)). For unrestricted codes, \(d\) is the smallest positive value with \(w[d+1] \neq 0\), where \(w\) is the inner distribution of C (see InnerDistribution (4.9-3)).

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

For linear codes C, the algorithm used is the following: After replacing C by a permutation equivalent C', one may assume the generator matrix has the following form \(G=(I_{k} \, | \, A)\), for some \(k\times (n-k)\) matrix \(A\). If \(A=0\) then return \(d(C)=1\). Next, find the minimum distance of the code spanned by the rows of \(A\). Call this distance \(d(A)\). Note that \(d(A)\) is equal to the the Hamming distance \(d(v,0)\) where \(v\) is some proper linear combination of \(i\) distinct rows of \(A\). Return \(d(C)=d(A)+i\), where \(i\) is as in the previous step.

This command may also be called using the syntax MinimumDistance(C, w). In this form, MinimumDistance returns the minimum distance of a codeword w to the code C, also called the distance from w 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] \neq 0\), where \(D\) is the distance distribution of w to C (see DistancesDistribution (4.9-4)).

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

See also the GUAVA commands relating to bounds on the minimum distance in section 7.1.

4.8-4 MinimumDistanceLeon

MinimumDistanceLeon returns the ``probable'' minimum distance \(d_{Leon}\) of a linear binary code C, using an implementation of Leon's probabilistic polynomial time algorithm. Briefly: Let C be a linear code of dimension \(k\) over \(GF(q)\) as above. The algorithm has input parameters \(s\) and \(\rho\), where \(s\) is an integer between \(2\) and \(n-k\), and \(\rho\) is an integer between \(2\) and \(k\).

(See for example J. S. Leon, [Leo88] for more details.) Sometimes (as is the case in GUAVA) this probabilistic algorithm is repeated several times and the most commonly occurring value is taken. (This function actually has two optional arguments: p and num. The command MinimumDistanceLeon(C,p,num) allows a bit more flexibility for the user - see the GAP code in codeops.gi for details.)

gap> C:=RandomLinearCode(50,22,GF(2));
a  [50,22,?] randomly generated code over GF(2)
gap> MinimumDistanceLeon(C); time;
6
211
gap> MinimumDistance(C); time;
6
1204

4.8-5 MinimumWeight

MinimumWeight returns the minimum Hamming weight of a linear code C. At the moment, this function works for binary and ternary codes only. The MinimumWeight function relies on an external executable program which is written in C language. As a consequence, the execution time of MinimumWeight function is faster than that of MinimumDistance (4.8-3) function.

The MinimumWeight function implements Chen's [Che69] algorithm if C is cyclic, and Zimmermann's [Zim96] algorithm if C is a general linear code. This function has a built-in check on the constraints of the minimum weight codewords. For example, for a self-orthogonal code over GF(3), the minimum weight codewords have weight that is divisible by 3, i.e. 0 mod 3 congruence. Similarly, self-orthogonal codes over GF(2) have codeword weights that are divisible by 4 and even codes over GF(2) have codewords weights that are divisible by 2. By taking these constraints into account, in many cases, the execution time may be significantly reduced. Consider the minimum Hamming weight enumeration of the \([151,45]\) binary cyclic code (second example below). This cyclic code is self-orthogonal, so the weight of all codewords is divisible by 4. Without considering this constraint, the computation will finish at information weight \(10\), rather than \(9\). We can see that, this 0 mod 4 constraint on the codeword weights, has allowed us to avoid enumeration of \(b(45,10) = 3,190,187,286\) additional codewords, where \(b(n,k)=n!/((n-k)!k!)\) is the binomial coefficient of integers \(n\) and \(k\).

Note that the C source code for this minimum weight computation has not yet been optimised, especially the code for GF(3), and there are chances to improve the speed of this function. Your contributions are most welcomed.

If you find any bugs on this function, please report it to ctjhai@plymouth.ac.uk.

gap> # Extended ternary quadratic residue code of length 48
gap> n := 47;;
gap> x := Indeterminate(GF(3));;
gap> F := Factors(x^n-1);;
gap> v := List([1..n], i->Zero(GF(3)));;
gap> v := v + MutableCopyMat(VectorCodeword( Codeword(F[2]) ));;
gap> G := CirculantMatrix(24, v);;
gap> for i in [1..Size(G)] do; s:=Zero(GF(3));
> for j in [1..Size(G[i])] do; s:=s+G[i][j]; od; Append(G[i], [ s ]);
> od;;
gap> C := GeneratorMatCodeNC(G, GF(3));
a  [48,24,?] randomly generated code over GF(3)
gap> MinimumWeight(C);
[48,24] linear code over GF(3) - minimum weight evaluation
Known lower-bound: 1
There are 2 generator matrices, ranks : 24 24 
The weight of the minimum weight codeword satisfies 0 mod 3 congruence
Enumerating codewords with information weight 1 (w=1)
    Found new minimum weight 15
Number of matrices required for codeword enumeration 2
Completed w= 1, 48 codewords enumerated, lower-bound 6, upper-bound 15
Termination expected with information weight 6 at matrix 1
-----------------------------------------------------------------------------
Enumerating codewords with information weight 2 (w=2) using 2 matrices
Completed w= 2, 1104 codewords enumerated, lower-bound 6, upper-bound 15
Termination expected with information weight 6 at matrix 1
-----------------------------------------------------------------------------
Enumerating codewords with information weight 3 (w=3) using 2 matrices
Completed w= 3, 16192 codewords enumerated, lower-bound 9, upper-bound 15
Termination expected with information weight 6 at matrix 1
-----------------------------------------------------------------------------
Enumerating codewords with information weight 4 (w=4) using 2 matrices
Completed w= 4, 170016 codewords enumerated, lower-bound 12, upper-bound 15
Termination expected with information weight 6 at matrix 1
-----------------------------------------------------------------------------
Enumerating codewords with information weight 5 (w=5) using 2 matrices
Completed w= 5, 1360128 codewords enumerated, lower-bound 12, upper-bound 15
Termination expected with information weight 6 at matrix 1
-----------------------------------------------------------------------------
Enumerating codewords with information weight 6 (w=6) using 1 matrices
Completed w= 6, 4307072 codewords enumerated, lower-bound 15, upper-bound 15
-----------------------------------------------------------------------------
Minimum weight: 15
15
gap> 

gap> # Binary cyclic code [151,45,36]
gap> n := 151;;
gap> x := Indeterminate(GF(2));;
gap> F := Factors(x^n-1);;
gap> C := CheckPolCode(F[2]*F[3]*F[3]*F[4], n, GF(2));
a cyclic [151,45,1..50]31..75 code defined by check polynomial over GF(2)
gap> MinimumWeight(C);
[151,45] cyclic code over GF(2) - minimum weight evaluation
Known lower-bound: 1
The weight of the minimum weight codeword satisfies 0 mod 4 congruence
Enumerating codewords with information weight 1 (w=1)
    Found new minimum weight 56
    Found new minimum weight 44
Number of matrices required for codeword enumeration 1
Completed w= 1, 45 codewords enumerated, lower-bound 8, upper-bound 44
Termination expected with information weight 11
-----------------------------------------------------------------------------
Enumerating codewords with information weight 2 (w=2) using 1 matrix
Completed w= 2, 990 codewords enumerated, lower-bound 12, upper-bound 44
Termination expected with information weight 11
-----------------------------------------------------------------------------
Enumerating codewords with information weight 3 (w=3) using 1 matrix
   Found new minimum weight 40
   Found new minimum weight 36
Completed w= 3, 14190 codewords enumerated, lower-bound 16, upper-bound 36
Termination expected with information weight 9
-----------------------------------------------------------------------------
Enumerating codewords with information weight 4 (w=4) using 1 matrix
Completed w= 4, 148995 codewords enumerated, lower-bound 20, upper-bound 36
Termination expected with information weight 9
-----------------------------------------------------------------------------
Enumerating codewords with information weight 5 (w=5) using 1 matrix
Completed w= 5, 1221759 codewords enumerated, lower-bound 24, upper-bound 36
Termination expected with information weight 9
-----------------------------------------------------------------------------
Enumerating codewords with information weight 6 (w=6) using 1 matrix
Completed w= 6, 8145060 codewords enumerated, lower-bound 24, upper-bound 36
Termination expected with information weight 9
-----------------------------------------------------------------------------
Enumerating codewords with information weight 7 (w=7) using 1 matrix
Completed w= 7, 45379620 codewords enumerated, lower-bound 28, upper-bound 36
Termination expected with information weight 9
-----------------------------------------------------------------------------
Enumerating codewords with information weight 8 (w=8) using 1 matrix
Completed w= 8, 215553195 codewords enumerated, lower-bound 32, upper-bound 36
Termination expected with information weight 9
-----------------------------------------------------------------------------
Enumerating codewords with information weight 9 (w=9) using 1 matrix
Completed w= 9, 886163135 codewords enumerated, lower-bound 36, upper-bound 36
-----------------------------------------------------------------------------
Minimum weight: 36
36

4.8-6 DecreaseMinimumDistanceUpperBound

DecreaseMinimumDistanceUpperBound is an implementation of the algorithm for the minimum distance of a linear binary code C by Leon [Leo88]. This algorithm tries to find codewords with small minimum weights. The parameter t is at least \(1\) and less than the dimension of C. The best results are obtained if it is close to the dimension of the code. The parameter m gives the number of runs that the algorithm will perform.

The result returned is a record with two fields; the first, mindist, gives the lowest weight found, and word gives the corresponding codeword. (This was implemented before MinimumDistanceLeon but independently. The older manual had given the command incorrectly, so the command was only found after reading all the *.gi files in the GUAVA library. Though both MinimumDistance and MinimumDistanceLeon often run much faster than DecreaseMinimumDistanceUpperBound, DecreaseMinimumDistanceUpperBound appears to be more accurate than MinimumDistanceLeon.)

gap> C:=RandomLinearCode(5,2,GF(2));
a  [5,2,?] randomly generated code over GF(2)
gap> DecreaseMinimumDistanceUpperBound(C,1,4);
rec( mindist := 3, word := [ 0*Z(2), Z(2)^0, Z(2)^0, 0*Z(2), Z(2)^0 ] )
gap> MinimumDistance(C);
3
gap> C:=RandomLinearCode(8,4,GF(2));
a  [8,4,?] randomly generated code over GF(2)
gap> DecreaseMinimumDistanceUpperBound(C,3,4);
rec( mindist := 2,
  word := [ Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0 ] )
gap> MinimumDistance(C);
2

4.8-7 MinimumDistanceRandom

MinimumDistanceRandom returns an upper bound for the minimum distance \(d_{random}\) of a linear binary code C, using a probabilistic polynomial time algorithm. Briefly: Let C be a linear code of dimension \(k\) over \(GF(q)\) as above. The algorithm has input parameters \(num\) and \(s\), where \(s\) is an integer between \(2\) and \(n-1\), and \(num\) is an integer greater than or equal to \(1\).

This probabilistic algorithm is repeated num times (with different random permutations of the rows of \(G\) each time) and the weight and codeword of the lowest occurring weight is taken.

gap> C:=RandomLinearCode(60,20,GF(2));
a  [60,20,?] randomly generated code over GF(2)
gap> #mindist(C);time;
gap> #mindistleon(C,10,30);time; #doesn't work well
gap> a:=MinimumDistanceRandom(C,10,30);time; # done 10 times -with fastest time!!

 This is a probabilistic algorithm which may return the wrong answer.
[ 12, [ 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 
        1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 ] ]
130
gap> a[2] in C;
true
gap> b:=DecreaseMinimumDistanceUpperBound(C,10,1); time; #only done once!
rec( mindist := 12, word := [ 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 
      Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 
      0*Z(2), Z(2)^0, Z(2)^0, 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2), 
      Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 
      0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 
      0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), 
      0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2) ] )
649
gap> Codeword(b!.word) in C;
true
gap> MinimumDistance(C);time;
12
196
gap> c:=MinimumDistanceLeon(C);time;
12
66
gap> C:=RandomLinearCode(30,10,GF(3));
a  [30,10,?] randomly generated code over GF(3)
gap> a:=MinimumDistanceRandom(C,10,10);time;

 This is a probabilistic algorithm which may return the wrong answer.
[ 13, [ 0 0 0 1 0 0 0 0 0 0 1 0 2 2 1 1 0 2 2 0 1 0 2 1 0 0 0 1 0 2 ] ]
229
gap> a[2] in C;
true
gap> MinimumDistance(C);time;
9
45
gap> c:=MinimumDistanceLeon(C);
Code must be binary. Quitting.
0
gap> a:=MinimumDistanceRandom(C,1,29);time;

 This is a probabilistic algorithm which may return the wrong answer.
[ 10, [ 0 0 1 0 2 0 2 0 1 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 2 2 2 0 ] ]
53

4.8-8 CoveringRadius

CoveringRadius returns the covering radius of a linear code C. This is the smallest number \(r\) with the property that each element \(v\) of the ambient vector space of C has at most a distance \(r\) to the code C. So for each vector \(v\) there must be an element \(c\) of C with \(d(v,c) \leq r\). The smallest covering radius of any \([n,k]\) binary linear code is denoted \(t(n,k)\). A binary linear code with reasonable small covering radius is called a covering code.

If C is a perfect code (see IsPerfectCode (4.3-6)), the covering radius is equal to \(t\), the number of errors the code can correct, where \(d = 2t+1\), with \(d\) the minimum distance of C (see MinimumDistance (4.8-3)).

If there exists a function called SpecialCoveringRadius in the `operations' field of the code, then this function will be called to compute the covering radius of the code. At the moment, no code-specific functions are implemented.

If the length of BoundsCoveringRadius (see BoundsCoveringRadius (7.2-1)), is 1, then the value in

is executed, unless the redundancy of C is too large. In the last case, a warning is issued.

The algorithm used to compute the covering radius is the following. First, CosetLeadersMatFFE is used to compute the list of coset leaders (which returns a codeword in each coset of \(GF(q)^n/C\) of minimum weight). Then WeightVecFFE is used to compute the weight of each of these coset leaders. The program returns the maximum of these weights.

gap> H := RandomLinearCode(10, 5, GF(2));
a  [10,5,?] randomly generated code over GF(2)
gap> CoveringRadius(H);
3
gap> H := HammingCode(4, GF(2));; IsPerfectCode(H);
true
gap> CoveringRadius(H);
1                       # Hamming codes have minimum distance 3
gap> CoveringRadius(ReedSolomonCode(7,4));
3 
gap> CoveringRadius( BCHCode( 17, 3, GF(2) ) );
3
gap> CoveringRadius( HammingCode( 5, GF(2) ) );
1
gap> C := ReedMullerCode( 1, 9 );;
gap> CoveringRadius( C );
CoveringRadius: warning, the covering radius of
this code cannot be computed straightforward.
Try to use IncreaseCoveringRadiusLowerBound( code ).
(see the manual for more details).
The covering radius of code lies in the interval:
[ 240 .. 248 ]

See also the GUAVA commands relating to bounds on the minimum distance in section 7.2.

4.8-9 SetCoveringRadius

SetCoveringRadius enables the user to set the covering radius herself, instead of letting GUAVA compute it. If intlist is an integer, GUAVA will simply put it in the `boundsCoveringRadius' field. If it is a list of integers, however, it will intersect this list with the `boundsCoveringRadius' field, thus taking the best of both lists. If this would leave an empty list, the field is set to intlist. Because some other computations use the covering radius of the code, it is important that the entered value is not wrong, otherwise new results may be invalid.

gap> C := BCHCode( 17, 3, GF(2) );;
gap> BoundsCoveringRadius( C );
[ 3 .. 4 ]
gap> SetCoveringRadius( C, [ 2 .. 3 ] );
gap> BoundsCoveringRadius( C );
[ [ 2 .. 3 ] ]

4.9 Distributions

4.9-1 MinimumWeightWords

This does not call the very fast function MinimumWeight (see MinimumWeight (4.8-5)).

gap> C:=HammingCode(3,GF(2));
a linear [7,4,3]1 Hamming (3,2) code over GF(2)
gap> MinimumWeightWords(C);
[ [ 1 0 0 0 0 1 1 ], [ 0 1 0 1 0 1 0 ], [ 0 1 0 0 1 0 1 ], [ 1 0 0 1 1 0 0 ], [ 0 0 1 0 1 1 0 ],
  [ 0 0 1 1 0 0 1 ], [ 1 1 1 0 0 0 0 ] ]

4.9-2 WeightDistribution

WeightDistribution returns the weight distribution of C, as a vector. The \(i^{th}\) 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 (4.9-3)). If \(w\) is the weight distribution of a linear code C, it must have the zero codeword, so \(w[1] = 1\) (one word of weight 0).

Some codes, such as the Hamming codes, have precomputed weight distributions. For others, the program WeightDistribution calls the GAP program DistancesDistributionMatFFEVecFFE, which is written in C. See also CodeWeightEnumerator.

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 ]

4.9-3 InnerDistribution

InnerDistribution returns the inner distribution of C. The \(i^{th}\) 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 (4.9-2)).

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] \neq 0\), because a distance between zero and \(d\) never occurs. See MinimumDistance (4.8-3).

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 ]

4.9-4 DistancesDistribution

DistancesDistribution returns the distribution of the distances of all elements of C to a codeword w in the same vector space. The \(i^{th}\) 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] \neq 0\), is defined as the distance to C (see MinimumDistance (4.8-3)).

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

4.9-5 OuterDistribution

The function OuterDistribution returns a list of length \(q^n\), where \(q\) is the size of the base field of C and \(n\) is the word length. The elements of the list consist of pairs, the first coordinate being an element of \(GF(q)^n\) (this is a codeword type) and the second coordinate being a 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 (4.9-4)) 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

4.10 Decoding Functions

4.10-1 Decode

Decode decodes r (a 'received word') with respect to code C and returns the `message word' (i.e., the information digits associated to the codeword \(c \in C\) closest to r). Here r can be a GUAVA codeword or a list of codewords. First, possible errors in r are corrected, then the codeword is decoded to an information codeword \(m\) (and not an element of C). If the code record has a field `specialDecoder', this special algorithm is used to decode the vector. Hamming codes, cyclic codes, and generalized Reed-Solomon have such a special algorithm. (The algorithm used for BCH codes is the Sugiyama algorithm described, for example, in section 5.4.3 of [HP03]. A special decoder has also being written for the generalized Reed-Solomon code using the interpolation algorithm. For cyclic codes, the error-trapping algorithm is used.) If C is linear and no special decoder field has been set then syndrome decoding is used. Otherwise (when C is non-linear), the nearest neighbor decoding algorithm is used (which is very slow).

The function uses the arguments C (the code record itself) and r (a vector of the codeword type) to decode r to an information vector. A normal decoder would take a codeword r of the same word length and field as C, and would return an information vector 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

4.10-2 Decodeword

Decodeword decodes r (a 'received word') with respect to code C and returns the codeword \(c \in C\) closest to r. Here r can be a GUAVA codeword or a list of codewords. If the code record has a field `specialDecoder', this special algorithm is used to decode the vector. Hamming codes, generalized Reed-Solomon codes, and BCH codes have such a special algorithm. (The algorithm used for BCH codes is the Sugiyama algorithm described, for example, in section 5.4.3 of [HP03]. The algorithm used for generalized Reed-Solomon codes is the ``interpolation algorithm'' described for example in chapter 5 of [JH04].) If C is linear and no special decoder field has been set then syndrome decoding is used. Otherwise, when C is non-linear, the nearest neighbor algorithm has been implemented (which should only be used for small-sized 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> Decodeword(C, c);                     # decoding
[ 1 0 1 1 0 1 0 ]
gap> R:=PolynomialRing(GF(11),["t"]);
GF(11)[t]
gap> P:=List([1,3,4,5,7],i->Z(11)^i);
[ Z(11), Z(11)^3, Z(11)^4, Z(11)^5, Z(11)^7 ]
gap> C:=GeneralizedReedSolomonCode(P,3,R);
a linear [5,3,1..3]2  generalized Reed-Solomon code over GF(11)
gap> MinimumDistance(C);
3
gap> c:=Random(C);
[ 0 9 6 2 1 ]
gap> v:=Codeword("09620");
[ 0 9 6 2 0 ]
gap> GeneralizedReedSolomonDecoderGao(C,v);
[ 0 9 6 2 1 ]
gap> Decodeword(C,v); # calls the special interpolation decoder
[ 0 9 6 2 1 ]
gap> G:=GeneratorMat(C);
[ [ Z(11)^0, 0*Z(11), 0*Z(11), Z(11)^8, Z(11)^9 ],
  [ 0*Z(11), Z(11)^0, 0*Z(11), Z(11)^0, Z(11)^8 ],
  [ 0*Z(11), 0*Z(11), Z(11)^0, Z(11)^3, Z(11)^8 ] ]
gap> C1:=GeneratorMatCode(G,GF(11));
a linear [5,3,1..3]2 code defined by generator matrix over GF(11)
gap> Decodeword(C,v); # calls syndrome decoding
[ 0 9 6 2 1 ]

4.10-3 GeneralizedReedSolomonDecoderGao

GeneralizedReedSolomonDecoderGao decodes r (a 'received word') to a codeword \(c \in C\) in a generalized Reed-Solomon code C (see GeneralizedReedSolomonCode (5.6-2)), closest to r. Here r must be a GUAVA codeword. If the code record does not have name `generalized Reed-Solomon code' then an error is returned. Otherwise, the Gao decoder [Gao03] is used to compute \(c\).

For long codes, this method is faster in practice than the interpolation method used in Decodeword.

gap> R:=PolynomialRing(GF(11),["t"]);
GF(11)[t]
gap> P:=List([1,3,4,5,7],i->Z(11)^i);
[ Z(11), Z(11)^3, Z(11)^4, Z(11)^5, Z(11)^7 ]
gap> C:=GeneralizedReedSolomonCode(P,3,R);
a linear [5,3,1..3]2  generalized Reed-Solomon code over GF(11)
gap> MinimumDistance(C);
3
gap> c:=Random(C);
[ 0 9 6 2 1 ]
gap> v:=Codeword("09620");
[ 0 9 6 2 0 ]
gap> GeneralizedReedSolomonDecoderGao(C,v); 
[ 0 9 6 2 1 ]

4.10-4 GeneralizedReedSolomonListDecoder

GeneralizedReedSolomonListDecoder implements Sudans list-decoding algorithm (see section 12.1 of [JH04]) for ``low rate'' Reed-Solomon codes. It returns the list of all codewords in C which are a distance of at most tau from r (a 'received word'). C must be a generalized Reed-Solomon code C (see GeneralizedReedSolomonCode (5.6-2)) and r must be a GUAVA codeword.

gap> F:=GF(16);
GF(2^4)
gap> a:=PrimitiveRoot(F);; b:=a^7;; b^4+b^3+1; 
0*Z(2)
gap> Pts:=List([0..14],i->b^i);
[ Z(2)^0, Z(2^4)^7, Z(2^4)^14, Z(2^4)^6, Z(2^4)^13, Z(2^2), Z(2^4)^12, Z(2^4)^4,
  Z(2^4)^11, Z(2^4)^3, Z(2^2)^2, Z(2^4)^2, Z(2^4)^9, Z(2^4), Z(2^4)^8 ]
gap> x:=X(F);;
gap> R1:=PolynomialRing(F,[x]);;
gap> vars:=IndeterminatesOfPolynomialRing(R1);;
gap> y:=X(F,vars);;
gap> R2:=PolynomialRing(F,[x,y]);;
gap> C:=GeneralizedReedSolomonCode(Pts,3,R1); 
a linear [15,3,1..13]10..12  generalized Reed-Solomon code over GF(16)
gap> MinimumDistance(C); ## 6 error correcting
13
gap> z:=Zero(F);;
gap> r:=[z,z,z,z,z,z,z,z,b^6,b^2,b^5,b^14,b,b^7,b^11];; 
gap> r:=Codeword(r);
[ 0 0 0 0 0 0 0 0 a^12 a^14 a^5 a^8 a^7 a^4 a^2 ]
gap> cs:=GeneralizedReedSolomonListDecoder(C,r,2); time;
[ [ 0 a^9 a^3 a^13 a^6 a^10 a^11 a a^12 a^14 a^5 a^8 a^7 a^4 a^2 ],
  [ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ] ]
250
gap> c1:=cs[1]; c1 in C;
[ 0 a^9 a^3 a^13 a^6 a^10 a^11 a a^12 a^14 a^5 a^8 a^7 a^4 a^2 ]
true
gap> c2:=cs[2]; c2 in C;
[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
true
gap> WeightCodeword(c1-r);
7
gap> WeightCodeword(c2-r);
7

4.10-5 BitFlipDecoder

The iterative decoding method BitFlipDecoder must only be applied to LDPC codes. For more information on LDPC codes, refer to Section 5.8. For these codes, BitFlipDecoder decodes very quickly. (Warning: it can give wildly wrong results for arbitrary binary linear codes.) The bit flipping algorithm is described for example in Chapter 13 of [JH04].

gap> C:=HammingCode(4,GF(2));
a linear [15,11,3]1 Hamming (4,2) code over GF(2)
gap> c:=Random(C);
[ 0 0 0 1 0 0 1 0 0 1 1 0 1 0 1 ]
gap> v:=List(c);
[ 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2),
  Z(2)^0, Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0 ]
gap> v[1]:=Z(2)+v[1]; # flip 1st bit of c to create an error
Z(2)^0
gap> v:=Codeword(v);
[ 1 0 0 1 0 0 1 0 0 1 1 0 1 0 1 ]
gap> BitFlipDecoder(C,v);
[ 0 0 0 1 0 0 1 0 0 1 1 0 1 0 1 ]

4.10-6 NearestNeighborGRSDecodewords

NearestNeighborGRSDecodewords finds all generalized Reed-Solomon codewords within distance dist from v and the associated polynomial, using ``brute force''. Input: v is a received vector (a GUAVA codeword), C is a GRS code, dist > 0 is the distance from v to search in C. Output: a list of pairs \([c,f(x)]\), where \(wt(c-v)\leq dist-1\) and \(c = (f(x_1),...,f(x_n))\).

gap> F:=GF(16);
GF(2^4)
gap> a:=PrimitiveRoot(F);; b:=a^7; b^4+b^3+1;
Z(2^4)^7
0*Z(2)
gap> Pts:=List([0..14],i->b^i);
[ Z(2)^0, Z(2^4)^7, Z(2^4)^14, Z(2^4)^6, Z(2^4)^13, Z(2^2), Z(2^4)^12,
  Z(2^4)^4, Z(2^4)^11, Z(2^4)^3, Z(2^2)^2, Z(2^4)^2, Z(2^4)^9, Z(2^4),
  Z(2^4)^8 ]
gap> x:=X(F);;
gap> R1:=PolynomialRing(F,[x]);;
gap> vars:=IndeterminatesOfPolynomialRing(R1);;
gap> y:=X(F,vars);;
gap> R2:=PolynomialRing(F,[x,y]);;
gap> C:=GeneralizedReedSolomonCode(Pts,3,R1);
a linear [15,3,1..13]10..12  generalized Reed-Solomon code over GF(16)
gap> MinimumDistance(C); # 6 error correcting
13
gap> z:=Zero(F);
0*Z(2)
gap> r:=[z,z,z,z,z,z,z,z,b^6,b^2,b^5,b^14,b,b^7,b^11];; # 7 errors
gap> r:=Codeword(r);
[ 0 0 0 0 0 0 0 0 a^12 a^14 a^5 a^8 a^7 a^4 a^2 ]
gap> cs:=NearestNeighborGRSDecodewords(C,r,7);
[ [ [ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ], 0*Z(2) ],
  [ [ 0 a^9 a^3 a^13 a^6 a^10 a^11 a a^12 a^14 a^5 a^8 a^7 a^4 a^2 ], x_1+Z(2)^0 ] ]

4.10-7 NearestNeighborDecodewords

NearestNeighborDecodewords finds all codewords in a linear code C within distance dist from v, using ``brute force''. Input: v is a received vector (a GUAVA codeword), C is a linear code, dist > 0 is the distance from v to search in C. Output: a list of \(c \in C\), where \(wt(c-v)\leq dist-1\).

gap> F:=GF(16);
GF(2^4)
gap> a:=PrimitiveRoot(F);; b:=a^7; b^4+b^3+1;
Z(2^4)^7
0*Z(2)
gap> Pts:=List([0..14],i->b^i);
[ Z(2)^0, Z(2^4)^7, Z(2^4)^14, Z(2^4)^6, Z(2^4)^13, Z(2^2), Z(2^4)^12,
  Z(2^4)^4, Z(2^4)^11, Z(2^4)^3, Z(2^2)^2, Z(2^4)^2, Z(2^4)^9, Z(2^4),
  Z(2^4)^8 ]
gap> x:=X(F);;
gap> R1:=PolynomialRing(F,[x]);;
gap> vars:=IndeterminatesOfPolynomialRing(R1);;
gap> y:=X(F,vars);;
gap> R2:=PolynomialRing(F,[x,y]);;
gap> C:=GeneralizedReedSolomonCode(Pts,3,R1);
a linear [15,3,1..13]10..12  generalized Reed-Solomon code over GF(16)
gap> MinimumDistance(C);
13
gap> z:=Zero(F);
0*Z(2)
gap> r:=[z,z,z,z,z,z,z,z,b^6,b^2,b^5,b^14,b,b^7,b^11];;
gap> r:=Codeword(r);
[ 0 0 0 0 0 0 0 0 a^12 a^14 a^5 a^8 a^7 a^4 a^2 ]
gap> cs:=NearestNeighborDecodewords(C,r,7);
[ [ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ], 
  [ 0 a^9 a^3 a^13 a^6 a^10 a^11 a a^12 a^14 a^5 a^8 a^7 a^4 a^2 ] ]

4.10-8 Syndrome

Syndrome returns the syndrome of word v with respect to a linear code C. v is a codeword in the ambient vector space of C. If v 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 (4.10-9)) that is needed to correct an error in \(v\).

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

4.10-9 SyndromeTable

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 v with Syndrome (see Syndrome (4.10-8)), the error vector needed to correct v can be found in the syndrome table. Subtracting this vector from v 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

4.10-10 StandardArray

StandardArray returns the standard array of a code C. This is a matrix with elements of the codeword type. It has \(q^r\) rows and \(q^k\) columns, where \(q\) is the size of the base field of C, \(r=n-k\) 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 (4.10-8)).

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

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

4.10-11 PermutationDecode

PermutationDecode performs permutation decoding when possible and returns original vector and prints 'fail' when not possible.

This uses AutomorphismGroup in the binary case, and (the slower) PermutationAutomorphismGroup otherwise, to compute the permutation automorphism group \(P\) of C. The algorithm runs through the elements \(p\) of \(P\) checking if the weight of \(H(p\cdot v)\) is less than \((d-1)/2\). If it is then the vector \(p\cdot v\) is used to decode \(v\): assuming C is in standard form then \(c=p^{-1}Em\) is the decoded word, where \(m\) is the information digits part of \(p\cdot v\). If no such \(p\) exists then ``fail'' is returned. See, for example, section 10.2 of Huffman and Pless [HP03] for more details.

gap> C0:=HammingCode(3,GF(2));
a linear [7,4,3]1 Hamming (3,2) code over GF(2)
gap> G0:=GeneratorMat(C0);;
gap> G := List(G0, ShallowCopy);;
gap> PutStandardForm(G);
()
gap> Display(G);
 1 . . . . 1 1
 . 1 . . 1 . 1
 . . 1 . 1 1 .
 . . . 1 1 1 1
gap> H0:=CheckMat(C0);;
gap> Display(H0);
 . . . 1 1 1 1
 . 1 1 . . 1 1
 1 . 1 . 1 . 1
gap> c0:=Random(C0);
[ 0 0 0 1 1 1 1 ]
gap> v01:=c0[1]+Z(2)^2;;
gap> v1:=List(c0, ShallowCopy);;
gap> v1[1]:=v01;;
gap> v1:=Codeword(v1);
[ 1 0 0 1 1 1 1 ]
gap> c1:=PermutationDecode(C0,v1);
[ 0 0 0 1 1 1 1 ]
gap> c1=c0;
true

4.10-12 PermutationDecodeNC

Same as PermutationDecode except that one may enter the permutation automorphism group P in as an argument, saving time. Here P is a subgroup of the symmetric group on \(n\) letters, where \(n\) is the word length of C.

4 Codes