7 Extensions to GUAVA

CoveringRadius is a function that already appeared in earlier versions of GUAVA, but it is changed to reflect the implementation of new functions for the covering radius.

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), is 1, then the value in

code.boundsCoveringRadius

is returned. Otherwise, the function

code.operations.CoveringRadius

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

If you want to overrule this restriction, you might want to execute

code.operations.CoveringRadius

yourself. However, this algorithm might also issue a warning that it cannot be executed, but this warning is sometimes issued too late, resulting in GAP exiting with an memory error. If it does run, it can only be stopped by pressing ctrl-C twice, thereby quitting GAP. It will not enter the usual break-loop. Therefore it is recommended to save your work before trying code.operations.CoveringRadius.

gap> CoveringRadius( BCHCode( 17, 3, GF(2) ) );
3
gap> CoveringRadius( HammingCode( 5, GF(2) ) );
1
gap> code := ReedMullerCode( 1, 9 );;
gap> CoveringRadius( code );
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 ]

BoundsCoveringRadius returns a list of integers. The first entry of this list is the maximum of some lower bounds for the covering radius of code, the last entry the minimum of some upper bounds of code.

If the covering radius of code is known, a list of length 1 is returned.

BoundsCoveringRadius makes use of the functions GeneralLowerBoundCoveringRadius and GeneralUpperBoundCoveringRadius.

gap> BoundsCoveringRadius( BCHCode( 17, 3, GF(2) ) );
[ 3 .. 4 ]
gap> BoundsCoveringRadius( HammingCode( 5, GF(2) ) );
[ 1 ] 

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> code := BCHCode( 17, 3, GF(2) );;
gap> BoundsCoveringRadius( code );
[ 3 .. 4 ]
gap> SetCoveringRadius( code, [ 2 .. 3 ] );
gap> BoundsCoveringRadius( code );
[ [ 2 .. 3 ] ]

IncreaseCoveringRadiusLowerBound tries to increase the lower bound of the covering radius of code. It does this by means of a probabilistic algorithm. This algorithm takes a random word in GF(q)ⁿ (or startword if it is specified), and, by changing random coordinates, tries to get as far from code as possible. If changing a coordinate finds a word that has a larger distance to the code than the previous one, the change is made permanent, and the algorithm starts all over again. If changing a coordinate does not find a coset leader that is further away from the code, then the change is made permanent with a chance of 1 in 100, if it gets the word closer to the code, or with a chance of 1 in 10, if the word stays at the same distance. Otherwise, the algorithm starts again with the same word as before.

If the algorithm did not allow changes that decrease the distance to the code, it might get stuck in a sub-optimal situation (the coset leader corresponding to such a situation (i.e. no coordinate of this coset leader can be changed in such a way that we get at a larger distance from the code) is called an orphan).

If the algorithm finds a word that has distance stopdistance to the code, it ends and returns that word, which can be used for further investigations.

The variable InfoCoveringRadius can be set to Print to print the maximum distance reached so far every 1000 runs. The alogrithm can be interrupted with ctrl-C, allowing the user to look at the word that is currently being examined (called current), or to change the chances that the new word is made permanent (these are called staychance and downchance). If one of these variables is i, then it corresponds with a i in 100 chance.

At the moment, the algorithm is only useful for codes with small dimension, where small means that the elements of the code fit in the memory. It works with larger codes, however, but when you use it for codes with large dimension, you should be very patient. If running the algorithm quits GAP (due to memory problems), you can change the global variable CRMemSize to a lower value. This might cause the algorithm to run slower, but without quitting GAP. The only way to find out the best value of CRMemSize is by experimenting.

ExhaustiveSearchCoveringRadius does an exhaustive search to find the covering radius of code. Every time a coset leader of a coset with weight w is found, the function tries to find a coset leader of a coset with weight w+1. It does this by enumerating all words of weight w+1, and checking whether a word is a coset leader. The start weight is the current known lower bound on the covering radius.

GeneralLowerBoundCoveringRadius returns a lower bound on the covering radius of code. It uses as many functions which names start with LowerBoundCoveringRadius as possible to find the best known lower bound (at least that GUAVA knows of) together with tables for the covering radius of binary linear codes with length not greater than 64.

GeneralUpperBoundCoveringRadius returns an upper bound on the covering radius of code. It uses as many functions which names start with UpperBoundCoveringRadius as possible to find the best known upper bound (at least that GUAVA knows of).

If the last argument of LowerBoundCoveringRadiusSphereCovering is false, then it returns a lower bound for the covering radius of a code of size M and length n. Otherwise, it returns a lower bound for the size of a code of length n and covering radius r.

F is the field over which the code is defined. If F is omitted, it is assumed that the code is over GF(2).

The bound is computed according to the sphere covering bound:

M Vq(n,r) ³ qn

where V_q(n,r) is the size of a sphere of radius r in GF(q)n.

If the last argument of LowerBoundCoveringRadiusVanWee1 is false, then it returns a lower bound for the covering radius of a code of size M and length n. Otherwise, it returns a lower bound for the size of a code of length n and covering radius r.

F is the field over which the code is defined. If F is omitted, it is assumed that the code is over GF(2).

The Van Wee bound is an improvement of the sphere covering bound:

M ì ï ï í ï ï î Vq(n,r) - æ è n r ö ø é  n-r r+1 ù æ è é ê  n+1 r+1 ù ú -  n+1 r+1 ö ø ü ï ï ý ï ï þ ³ qn

If the last argument of LowerBoundCoveringRadiusVanWee2 is false, then it returns a lower bound for the covering radius of a code of size M and length n. Otherwise, it returns a lower bound for the size of a code of length n and covering radius r.

This bound only works for binary codes. It is based on the following inequality:

M æ è æ è V2(n,2) -  1 2 (r+2)(r-1) ö ø V2(n,r) + eV2(n,r-2) ö ø (V2(n,2) -  1 2 (r+2)(r-1) + e) ³ 2n,

where

e = æ è r+2 2 ö ø é ê æ è n-r+1 2 ö ø / æ è r+2 2 ö ø ù ú - æ è n-r+1 2 ·

If the last argument of LowerBoundCoveringRadiusCountingExcess is false, then it returns a lower bound for the covering radius of a code of size M and length n. Otherwise, it returns a lower bound for the size of a code of length n and covering radius r.

This bound only works for binary codes. It is based on the following inequality:

M ( rV2(n,r) + eV2(n,r-1) ) ³ (r+ e) 2n,

where

e = (r+1) é ê  n+1 r+1 ù ú - (n+1)

and

r = ì ï ï í ï ï î n-3+  2 n if r = 2 n-r-1 if r ³ 3

If the last argument of LowerBoundCoveringRadiusEmbedded1 is false, then it returns a lower bound for the covering radius of a code of size M and length n. Otherwise, it returns a lower bound for the size of a code of length n and covering radius r.

This bound only works for binary codes. It is based on the following inequality:

M æ è V2(n,r) - æ è 2r r ö ø ö ø ³ 2n - A( n, 2r+1 ) æ è 2r r ö ø ,

where A(n,d) denotes the maximal cardinality of a (binary) code of length n and minimum distance d. The function UpperBound is used to compute this value.

Sometimes LowerBoundCoveringRadiusEmbedded1 is better than LowerBoundCoveringRadiusEmbedded2, sometimes it is the other way around.

If the last argument of LowerBoundCoveringRadiusEmbedded2 is false, then it returns a lower bound for the covering radius of a code of size M and length n. Otherwise, it returns a lower bound for the size of a code of length n and covering radius r.

This bound only works for binary codes. It is based on the following inequality:

M æ è V2(n,r) -  3 2 æ è 2r r ö ø ö ø ³ 2n - 2A( n, 2r+1 ) æ è 2r r ö ø ,

where A(n,d) denotes the maximal cardinality of a (binary) code of length n and minimum distance d. The function UpperBound is used to compute this value.

Sometimes LowerBoundCoveringRadiusEmbedded1 is better than LowerBoundCoveringRadiusEmbedded2, sometimes it is the other way around.

LowerBoundCoveringRadiusInduction returns a lower bound for the size of a code with length n and covering radius r.

If n = 2r+2 and r ³ 1, the returned value is 4.

If n = 2r+3 and r ³ 1, the returned value is 7.

If n = 2r+4 and r ³ 4, the returned value is 8.

Otherwise, 0 is returned.

UpperBoundCoveringRadiusRedundancy returns the redundancy of code as an upper bound for the covering radius of code. code must be a linear code.

UpperBoundCoveringRadiusDelsarte returns an upper bound for the covering radius of code. This upperbound is equal to the external distance of code, this is the minimum distance of the dual code, if code is a linear code.

UpperBoundCoveringRadiusStrength returns an upper bound for the covering radius of code.

First the code is punctured at the zero coordinates (i.e. the coordinates where all codewords have a zero). If the remaining code has strength 1 (i.e. each coordinate contains each element of the field an equal number of times), then it returns [(q-1)/(q)]m + (n-m) (where q is the size of the field and m is the length of punctured code), otherwise it returns n. This bound works for all codes.

This function returns an upper bound for the covering radius of code, which must be linear, in a Griesmer-like fashion. It returns

n - k å i=1  é ê  d qi ù ú

This function returns an upper bound for the covering radius of code, which must be a cyclic code. It returns

n - k + 1 - é ê  w(g(x)) 2 ù ú ,

where g(x) is the generator polynomial of code.

7.2 New code constructions

In this section we describe some new constructions for codes. The first constructions are variations on the direct sum construction, most of the time resulting in better codes than the direct sum.

The piecewise constant code construction stands on its own. Using this construction, some good codes have been obtained.

The last five constructions yield linear binary codes with fixed minimum distances and covering radii. These codes can be arbitrary long.

The extended direct sum construction is described in an article by Graham and Sloane. The resulting code consists of m copies of L, extended by repeating the codewords of B m times.

Suppose L is an [n_L, k_L]r_L code, and B is an [n_L, k_B]r_B code (non-linear codes are also permitted). The length of B must be equal to the length of L. The length of the new code is n = m n_L, the dimension (in the case of linear codes) is k £ m k_L + k_B, and the covering radius is r £ ëm Y( L, B ) û, with

Y( L, B ) = max u Î F2nL   1 2kB å v Î B  d( L, v + u )·

However, this computation will not be executed, because it may be too time consuming for large codes.

If L Í B , and L and B are linear codes, the last copy of L is omitted. In this case the dimension is k = m k_L + (k_B - k_L).

gap> c := HammingCode( 3, GF(2) );
a linear [7,4,3]1 Hamming (3,2) code over GF(2)
gap> d := WholeSpaceCode( 7, GF(2) );
a cyclic [7,7,1]0 whole space code over GF(2)
gap> e := ExtendedDirectSumCode( c, d, 3 );
a linear [21,15,1..3]2 3-fold extended direct sum code

AmalgatedDirectSumCode returns the amalgated direct sum of the codes c₁ and c₂. The amalgated direct sum code consists of all codewords of the form (u  ||  0  ||  v) if (u  ||  0) Î c₁ and (0  ||  v) Î c₂ and all codewords of the form (u  ||  1  ||  v) if (u  ||  1) Î c₁ and (1  ||  v) Î c₂. The result is a code with length n = n₁ + n₂ - 1 and size M < = M₁ ·M₂ / 2 .

If both codes are linear, they will first be standardized, with information symbols in the last and first coordinates of the first and second code, respectively.

If c₁ is a normal code with the last coordinate acceptable, and c₂ is a normal code with the first coordinate acceptable, then the covering radius of the new code is r < = r₁ + r₂ . However, checking whether a code is normal or not is a lot of work, and almost all codes seem to be normal. Therefore, an option check can be supplied. If check is true, then the codes will be checked for normality. If check is false or omitted, then the codes will not be checked. In this case it is assumed that they are normal. Acceptability of the last and first coordinate of the first and second code, respectively, is in the last case also assumed to be done by the user.

gap> c := HammingCode( 3, GF(2) );
a linear [7,4,3]1 Hamming (3,2) code over GF(2)
gap> d := ReedMullerCode( 1, 4 );
a linear [16,5,8]6 Reed-Muller (1,4) code over GF(2)
gap> e := DirectSumCode( c, d );
a linear [23,9,3]7 direct sum code
gap> f := AmalgatedDirectSumCode( c, d );;
gap> MinimumDistance( f );;
gap> CoveringRadius( f );; # takes some time
gap> f;
a linear [22,8,3]7 amalgated direct sum code

BlockwiseDirectSumCode returns a subcode of the direct sum of c₁ and c₂. The fields of c₁ and c₂ should be same. l₁ and l₂ are two equally long lists with elements from the spaces where c₁ and c₂ are in, respectively, orl₁ and l₂ are two equally long lists containing codes. The union of the codes in l₁ and l₂ must be c₁ and c₂, respectively.

In the first case, the blockwise direct sum code is defined as

bds = È 1 £ i £ l  ( c1 + (l1)i ) Å( c2 + (l2)i ),

where l is the length of l₁ and l₂, and Å is the direct sum.

In the second case, it is defined as

bds = È 1 £ i £ l  ( (l1)i Å(l2)i )·

The length of the new code is n = n₁ + n₂ .

gap> c := HammingCode( 3, GF(2) );;
gap> d := EvenWeightSubcode( WholeSpaceCode( 6, GF(2) ) );;
gap> BlockwiseDirectSumCode( c, [[ 0,0,0,0,0,0,0 ],[ 1,0,1,0,1,0,0 ]],
> d, [[ 0,0,0,0,0,0 ],[ 1,0,1,0,1,0 ]] );
a (13,1024,1..13)1..2 blockwise direct sum code

PiecewiseConstantCode returns a code with length n = ån_i, where part =[ n₁, ..., n_k ]. weights is a list of constraints, each of length k. The default field is GF(2).

A constraint is a list of integers, and a word c = ( c₁, ..., c_k ) (according to part) is in the resulting code if and only if ||c_i|| = w_i^(l) for all 1 £ i £ k for some constraint w^(l) Î constraints .

An example might make things clearer:

gap> PiecewiseConstantCode( [ 2, 3 ],
> [ [ 0, 0 ], [ 0, 3 ], [ 1, 0 ], [ 2, 2 ] ],
> GF(2) );
a (5,7,1..5)1..5 piecewise constant code over GF(2)
gap> AsSSortedList(last);
[ [ 0 0 0 0 0 ], [ 0 0 1 1 1 ], [ 0 1 0 0 0 ], [ 1 0 0 0 0 ], [ 1 1 0 1 1 ], 
  [ 1 1 1 0 1 ], [ 1 1 1 1 0 ] ]

The first constraint is satisfied by codeword 1, the second by codeword 2, the third by codewords 3 and 4, and the fourth by codewords 5, 6 and 7.

7.3 Gabidulin codes

These five codes are derived from an article by Gabidulin, Davydov and Tombak GDT91. These five codes are defined by check matrices. Exact definitions can be found in the article.

The Gabidulin code, the enlarged Gabidulin code, the Davydov code, the Tombak code, and the enlarged Tombak code, correspond with theorem 1, 2, 3, 4, and 5, respectively in the article.

These codes have fixed minimum distance and covering radius, but can be arbitrarily long. They are defined through check matrices.

GabidulinCode yields a code of length 5 ·2^m-2-1, redundancy 2m-1, minimum distance 3 and covering radius 2. w1 and w2 should be elements of GF(2m-2).

EnlargedGabidulinCode yields a code of length 7 ·2^m-2-2, redundancy 2m, minimum distance 3 and covering radius 2. w1 and w2 are elements of GF(2m-2). e is an element of GF(2m). The core of an enlarged Gabidulin code consists of a Gabidulin code.

DavydovCode yields a code of length 2^v + 2^r-v - 3, redundancy r, minimum distance 4 and covering radius 2. v is an integer between 2 and r-2. ei and ej are elements of GF(2v) and GF(2r-v), respectively.

TombakCode yields a code of length 15 ·2^m-3 - 3, redundancy 2m, minimum distance 4 and covering radius 2. e is an element of GF(2m). beta and gamma are elements of GF(2m-1). w1 and w2 are elements of GF(2m-3).

EnlargedTombakCode yields a code of length 23 ·2^m-4 - 3, redundancy 2m-1, minimum distance 4 and covering radius 2. The parameters m, e, beta, gamma, w1 and w2 are defined as in TombakCode. u is an element of GF(2m-1). The code of an enlarged Tombak code consists of a Tombak code.

gap> GabidulinCode( 4, Z(4)^0, Z(4)^1 );
a linear [19,12,3]2 Gabidulin code (m=4) over GF(2)
gap> EnlargedGabidulinCode( 4, Z(4)^0, Z(4)^1, Z(16)^11 );
a linear [26,18,3]2 enlarged Gabidulin code (m=4) over GF(2)
gap> DavydovCode( 6, 3, Z(8)^1, Z(8)^5 );
a linear [13,7,4]2 Davydov code (r=6, v=3) over GF(2)
gap> TombakCode( 5, Z(32)^6, Z(16)^14, Z(16)^10, Z(4)^0, Z(4)^1 );
a linear [57,47,4]2 Tombak code (m=5) over GF(2)
gap> EnlargedTombakCode( 6, Z(32)^6, Z(16)^14, Z(16)^10,
> Z(4)^0, Z(4)^0, Z(32)^23 );
a linear [89,78,4]2 enlarged Tombak code (m=6) over GF(2)

7.4 Some functions related to the norm of a code

In this section, some functions that can be used to compute the norm of a code and to decide upon its normality are discussed.

CoordinateNorm returns the norm of code with respect to coordinate coord. If C_a = { c Î code || c_coord = a }, then the norm of code with respect to coord is defined as

max v Î GF(q)n  q å a=1  d(x,Ca),

with the convention that d(x,C_a) = n if C_a is empty.

gap> CoordinateNorm( HammingCode( 3, GF(2) ), 3 );
3 

CodeNorm returns the norm of code. The norm of a code is defined as the minimum of the norms for the respective coordinates of the code. In effect, for each coordinate CoordinateNorm is called, and the minimum of the calculated numbers is returned.

gap> CodeNorm( HammingCode( 3, GF(2) ) );
3 

IsCoordinateAcceptable returns true if coordinate coord of code is acceptable. A coordinate is called acceptable if the norm of the code with respect to that coordinate is not more than two times the covering radius of the code plus one.

gap> IsCoordinateAcceptable( HammingCode( 3, GF(2) ), 3 );
true 

GeneralizedCodeNorm returns the k-norm of code with respect to k subcodes.

gap> c := RepetitionCode( 7, GF(2) );;
gap> ham := HammingCode( 3, GF(2) );;
gap> d := EvenWeightSubcode( ham );;
gap> e := ConstantWeightSubcode( ham, 3 );;
gap> GeneralizedCodeNorm( ham, c, d, e );
4 

IsNormalCode returns true if code is normal. A code is called normal if the norm of the code is not more than two times the covering radius of the code plus one. Almost all codes are normal, however some (non-linear) abnormal codes have been found.

Often, it is difficult to find out whether a code is normal, because it involves computing the covering radius. However, IsNormalCode uses much information from the literature about normality for certain code parameters.

gap> IsNormalCode( HammingCode( 3, GF(2) ) );
true 

DecreaseMinimumDistanceLowerBound is an implementation of the algorithm for the minimum distance by Leon Leon91. This algorithm tries to find codewords with small minimum weights. The parameter s is described in the article, the best results are obtained if it is close to the dimension of the code. The parameter iterations 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.

7.5 New miscellaneous functions

In this section, some new miscellaneous functions are described, including weight enumerators, the MacWilliams-transform and affinity and almost affinity of codes.

CodeWeightEnumerator returns a polynomial of the following form:

f(x) = n å i=0  Ai xi,

where A_i is the number of codewords in code with weight i.

gap> CodeWeightEnumerator( ElementsCode( [ [ 0,0,0 ], [ 0,0,1 ],
> [ 0,1,1 ], [ 1,1,1 ] ], GF(2) ) );
x^3 + x^2 + x + 1
gap> CodeWeightEnumerator( HammingCode( 3, GF(2) ) );
x^7 + 7*x^4 + 7*x^3 + 1 

CodeDistanceEnumerator returns a polynomial of the following form:

f(x) = n å i=0  Bi xi,

where B_i is the number of codewords with distance i to word.

If word is a codeword, then CodeDistanceEnumerator returns the same polynomial as CodeWeightEnumerator.

gap> CodeDistanceEnumerator( HammingCode( 3, GF(2) ),[0,0,0,0,0,0,1] );
x^6 + 3*x^5 + 4*x^4 + 4*x^3 + 3*x^2 + x
gap> CodeDistanceEnumerator( HammingCode( 3, GF(2) ),[1,1,1,1,1,1,1] );
x^7 + 7*x^4 + 7*x^3 + 1 # `[1,1,1,1,1,1,1]' $\in$ `HammingCode( 3, GF(2 ) )'

CodeMacWilliamsTransform returns a polynomial of the following form:

f(x) = n å i=0  Ci xi,

where C_i is the number of codewords with weight i in the dual code of code.

gap> CodeMacWilliamsTransform( HammingCode( 3, GF(2) ) );
7*x^4 + 1 

IsSelfComplementaryCode returns true if

v Î code Þ 1 - v Î code,

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 returns true if code is an affine code. A code is called affineif 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) ),
> [ 1, 0, 0, 0, 0, 0, 0 ] ) );
true
gap> IsAffineCode( NordstromRobinsonCode() );
false 

IsAlmostAffineCode returns true if code is an almost affine code. A code is called almost affineif the size of any punctured code of code 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 

IsGriesmerCode returns true if code, which must be a linear code, is Griesmer code, and false otherwise.

A code is called Griesmer if its length satisfies

n = g[k,d] = k-1 å i=0  é  d qi ù·

gap> IsGriesmerCode( HammingCode( 3, GF(2) ) );
true
gap> IsGriesmerCode( BCHCode( 17, 2, GF(2) ) );
false 

CodeDensity returns the densityof code. The density of a code is defined as

M ·Vq(n,t) qn ,

where M is the size of the code, V_q(n,t) is the size of a sphere of radius t in qⁿ, t is the covering radius of the code and n is the length of the code.

gap> CodeDensity( HammingCode( 3, GF(2) ) );
1
gap> CodeDensity( ReedMullerCode( 1, 4 ) );
14893/2048 

[Up] [Previous] [Index]