4 Codes

4.3
Boolean Functions for Codes

4.3-1 in

4.3-2 IsSubset

4.3-3 IsCode

4.3-4 IsLinearCode

4.3-5 IsCyclicCode

4.3-6 IsPerfectCode

4.3-7 IsMDSCode

4.3-8 IsSelfDualCode

4.3-9 IsSelfOrthogonalCode

4.3-10 IsDoublyEvenCode

4.3-11 IsSinglyEvenCode

4.3-12 IsEvenCode

4.3-13 IsSelfComplementaryCode

4.3-14 IsAffineCode

4.3-15 IsAlmostAffineCode

4.3-1 in

4.3-2 IsSubset

4.3-3 IsCode

4.3-4 IsLinearCode

4.3-5 IsCyclicCode

4.3-6 IsPerfectCode

4.3-7 IsMDSCode

4.3-8 IsSelfDualCode

4.3-9 IsSelfOrthogonalCode

4.3-10 IsDoublyEvenCode

4.3-11 IsSinglyEvenCode

4.3-12 IsEvenCode

4.3-13 IsSelfComplementaryCode

4.3-14 IsAffineCode

4.3-15 IsAlmostAffineCode

4.10
Decoding Functions

4.10-1 Decode

4.10-2 Decodeword

4.10-3 GeneralizedReedSolomonDecoderGao

4.10-4 GeneralizedReedSolomonListDecoder

4.10-5 BitFlipDecoder

4.10-6 NearestNeighborGRSDecodewords

4.10-7 NearestNeighborDecodewords

4.10-8 Syndrome

4.10-9 SyndromeTable

4.10-10 StandardArray

4.10-11 PermutationDecode

4.10-12 PermutationDecodeNC

4.10-1 Decode

4.10-2 Decodeword

4.10-3 GeneralizedReedSolomonDecoderGao

4.10-4 GeneralizedReedSolomonListDecoder

4.10-5 BitFlipDecoder

4.10-6 NearestNeighborGRSDecodewords

4.10-7 NearestNeighborDecodewords

4.10-8 Syndrome

4.10-9 SyndromeTable

4.10-10 StandardArray

4.10-11 PermutationDecode

4.10-12 PermutationDecodeNC

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

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

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

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

\[ C^* = \{ v \in GF(q)^n\ |\ v\cdot c = 0,\ for \ all\ c \in C \}. \]

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-1 \=`

`‣ \=` ( C1, C2 ) | ( method ) |

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-1 \+`

`‣ \+` ( C1, C2 ) | ( method ) |

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 \*`

`‣ \*` ( C1, C2 ) | ( method ) |

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 \*`

`‣ \*` ( m, C ) | ( method ) |

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 ]

`‣ InformationWord` ( C, c ) | ( function ) |

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.

To invert this, use the encoding function `*`

(see `\*`

(4.2-3)).

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"

`‣ in` ( c, C ) | ( function ) |

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

`‣ IsSubset` ( C1, C2 ) | ( function ) |

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

`‣ IsCode` ( obj ) | ( function ) |

`IsCode`

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

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

`‣ IsLinearCode` ( obj ) | ( function ) |

`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

`‣ IsCyclicCode` ( obj ) | ( function ) |

`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

`‣ IsPerfectCode` ( C ) | ( function ) |

`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

`‣ IsMDSCode` ( C ) | ( function ) |

`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

`‣ IsSelfDualCode` ( C ) | ( function ) |

`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

`‣ IsSelfOrthogonalCode` ( C ) | ( function ) |

`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

`‣ IsDoublyEvenCode` ( C ) | ( function ) |

`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

`‣ IsSinglyEvenCode` ( C ) | ( function ) |

`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

`‣ IsEvenCode` ( C ) | ( function ) |

`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

`‣ IsSelfComplementaryCode` ( C ) | ( function ) |

`IsSelfComplementaryCode`

returns `true' if

\[ v \in C \Rightarrow 1 - v \in C, \]

where \(1\) is the all-one word of length \(n\).

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

`‣ IsAffineCode` ( C ) | ( function ) |

`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

`‣ IsAlmostAffineCode` ( C ) | ( function ) |

`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

`‣ IsEquivalent` ( C1, C2 ) | ( function ) |

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.

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

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)

`‣ CodeIsomorphism` ( C1, C2 ) | ( function ) |

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

`‣ AutomorphismGroup` ( C ) | ( function ) |

`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

`‣ PermutationAutomorphismGroup` ( C ) | ( function ) |

`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

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

`‣ IsFinite` ( C ) | ( function ) |

`IsFinite`

is an implementation of the GAP domain function `IsFinite`

. It returns true for a code `C`.

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

`‣ Size` ( C ) | ( function ) |

`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

`‣ LeftActingDomain` ( C ) | ( function ) |

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

`‣ Dimension` ( C ) | ( function ) |

`Dimension`

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

then returns an error.

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

`‣ AsSSortedList` ( C ) | ( function ) |

`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

\[ GF(q)=\{ 0 , Z(q)^0, Z(q), Z(q)^2, ...Z(q)^{q-2} \} \]

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

`‣ Print` ( C ) | ( function ) |

`Print`

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

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

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

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

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

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

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

Except for codes produced by `RandomLinearCode`

, if `d` is not yet known, it is displayed in the form

lowerbound..upperbound

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

The function `Display`

gives more information. See `Display`

(4.6-3).

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

`‣ String` ( C ) | ( function ) |

`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)"

`‣ Display` ( C ) | ( function ) |

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

`‣ DisplayBoundsInfo` ( bds ) | ( function ) |

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

`‣ GeneratorMat` ( C ) | ( function ) |

`GeneratorMat`

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

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

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

gap> GeneratorMat( HammingCode( 3, GF(2) ) ); [ [ an immutable GF2 vector of length 7], [ an immutable GF2 vector of length 7], [ an immutable GF2 vector of length 7], [ an immutable GF2 vector of length 7] ] gap> 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) ) ); [ ]

`‣ CheckMat` ( C ) | ( function ) |

`CheckMat`

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

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

gap> CheckMat( HammingCode(3, GF(2) ) ); [ [ 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) ) ); [ ]

`‣ GeneratorPol` ( C ) | ( function ) |

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

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

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

`‣ CheckPol` ( C ) | ( function ) |

`CheckPol`

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

\[ f\cdot h \equiv 0 \ ({\rm mod}\ x^n-1), \]

where \(h\) is the check polynomial, and \(n\) is the word length of `C`. The check polynomial is computed from the generator polynomial, the generator or parity check matrix or the elements of `C` (if possible), whichever is available.

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

gap> CheckPol(GeneratorMatCode([[1, 1, 0], [0, 1, 1]], GF(2))); 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

`‣ RootsOfCode` ( C ) | ( function ) |

`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

`‣ WordLength` ( C ) | ( function ) |

`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

`‣ Redundancy` ( C ) | ( function ) |

`Redundancy`

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

returns an error.

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

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

`‣ MinimumDistance` ( C ) | ( function ) |

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

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

`‣ MinimumDistanceLeon` ( C ) | ( function ) |

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

Find a generator matrix \(G\) of \(C\).

Randomly permute the columns of \(G\).

Perform Gaussian elimination on the permuted matrix to obtain a new matrix of the following form:

\[ G=(I_{k} \, | \, Z \, | \, B) \]

with \(Z\) a \(k\times s\) matrix. If \((Z,B)\) is the zero matrix then return \(1\) for the minimum distance. If \(Z=0\) but not \(B\) then either choose another permutation of the rows of

`C`or return `method fails'.Search \(Z\) for at most \(\rho\) rows that lead to codewords of weight less than \(\rho\).

For these codewords, compute the weight of the whole word in

`C`. Return this weight.

(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

`‣ MinimumWeight` ( C ) | ( function ) |

`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

`‣ DecreaseMinimumDistanceUpperBound` ( C, t, m ) | ( function ) |

`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

`‣ MinimumDistanceRandom` ( C, num, s ) | ( function ) |

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

Find a generator matrix \(G\) of \(C\).

Randomly permute the columns of \(G\), written \(G_p\)..

\[ G=(A, B) \]

with \(A\) a \(k\times s\) matrix. If \(A\) is the zero matrix then return `method fails'.

Search \(A\) for at most \(5\) rows that lead to codewords, in the code \(C_A\) with generator matrix \(A\), of minimum weight.

For these codewords, use the associated linear combination to compute the weight of the whole word in

`C`. Return this weight and codeword.

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

`‣ CoveringRadius` ( C ) | ( function ) |

`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

C.boundsCoveringRadius

is returned. Otherwise, the function

C.operations.CoveringRadius

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.

`‣ SetCoveringRadius` ( C, intlist ) | ( function ) |

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

`‣ MinimumWeightWords` ( C ) | ( function ) |

`MinimumWeightWords`

returns the list of minimum weight codewords of `C`.

This algorithm is written in GAP is slow, so is only suitable for small codes.

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

`‣ WeightDistribution` ( C ) | ( function ) |

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

`‣ InnerDistribution` ( C ) | ( function ) |

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

`‣ DistancesDistribution` ( C, w ) | ( function ) |

`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

`‣ OuterDistribution` ( C ) | ( function ) |

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

`‣ Decode` ( C, r ) | ( function ) |

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

A special decoder can be created by defining a function

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

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.

Encoding is done by multiplying the information vector with the code (see 4.2).

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

`‣ Decodeword` ( C, r ) | ( function ) |

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

`‣ GeneralizedReedSolomonDecoderGao` ( C, r ) | ( function ) |

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

`‣ GeneralizedReedSolomonListDecoder` ( C, r, tau ) | ( function ) |

`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

`‣ BitFlipDecoder` ( C, r ) | ( function ) |

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 ]

`‣ NearestNeighborGRSDecodewords` ( C, v, dist ) | ( function ) |

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

`‣ NearestNeighborDecodewords` ( C, v, dist ) | ( function ) |

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

`‣ Syndrome` ( C, v ) | ( function ) |

`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

`‣ SyndromeTable` ( C ) | ( function ) |

`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

`‣ StandardArray` ( C ) | ( function ) |

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

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

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

`‣ PermutationDecode` ( C, v ) | ( function ) |

`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

`‣ PermutationDecodeNC` ( C, v, P ) | ( function ) |

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

generated by GAPDoc2HTML