65.142 Some functions for the covering radius

Together with the new code constructions, the new functions for computing (the bounds of) the covering radius are the most important additions to GUAVA.

These additions required a change in the fields of a code record. In previous versions of GUAVA, the covering radius field was an integer field, called coveringRadius. To allow the code-record to contain more information about the covering radius, this field has been replaced by a field called boundsCoveringRadius. This field contains a vector of possible values of the covering radius of the code. If the value of the covering radius is known, then the length of this vector is one.

This means that every instance of coveringRadius in the previous version had to be changed to boundsCoveringRadius. There is also an advantage to this: if bounds for a specific type of code are known, they can be implemented (and they have been). This has been especially useful for the Reed-Muller codes.

Of course, the main covering radius function dispatcher, CoveringRadius, had to be changed to incorporate these changes. Previously, this dispatcher called
code.operations.CoveringRadius. Problem with these functions is that they only work if the redundancy is not too large. Another problem is that the algorithm for linear and cyclic codes is written in C (in the kernel of GAP). This does not allow the user to interrupt the function, except by pressing ctrl-C twice, which exits GAP altogether. For more information, check the section on the (new) CoveringRadius (CoveringRadius) function.

Perhaps the most interesting new covering radius function is
IncreaseCoveringRadiusLowerBound (IncreaseCoveringRadiusLowerBound). It uses a probabilistic algorithm that tries to find better lower bounds of the covering radius of a code. It works best when the dimension is low, thereby giving a sort of complement function to CoveringRadius. When the dimension is about half the length of a code, neither algorithm will work, although IncreaseCoveringRadiusLowerBound is specifically designed to avoid memory problems, unlike CoveringRadius.

The function ExhaustiveSearchCoveringRadius (ExhaustiveSearchCoveringRadius) tries to find the covering radius of a code by exhaustively searching the space in which the code lies for coset leaders.

A number of bounds for the covering radius in general have been implemented, including some well known bounds like the sphere-covering bound, the redundancy bound and the Delsarte bound. These function all start with LowerBoundCoveringRadius (sections LowerBoundCoveringRadiusSphereCovering, LowerBoundCoveringRadiusVanWee1, LowerBoundCoveringRadiusVanWee2, LowerBoundCoveringRadiusCountingExcess, LowerBoundCoveringRadiusEmbedded1, LowerBoundCoveringRadiusEmbedded2, LowerBoundCoveringRadiusInduction, LowerBoundCoveringRadiusSphereCovering) or UpperBoundCoveringRadius (sections UpperBoundCoveringRadiusRedundancy, UpperBoundCoveringRadiusDelsarte, UpperBoundCoveringRadiusStrength, UpperBoundCoveringRadiusGriesmerLike, UpperBoundCoveringRadiusCyclicCode).

The functions GeneralLowerBoundCoveringRadius (GeneralLowerBoundCoveringRadius) and
GeneralUpperBoundCoveringRadius (GeneralUpperBoundCoveringRadius) try to find the best known bounds for a given code. BoundsCoveringRadius (BoundsCoveringRadius) uses these functions to return a vector of possible values for the covering radius.

To allow the user to enter values in the .boundsCoveringRadius record herself, the function SetCoveringRadius is provided.

Previous Up Top Next
Index

GAP 3.4.4
April 1997