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.
GAP 3.4.4