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
To allow the code-record to contain more information about the
covering radius, this field has been replaced by a
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
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
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
ctrl-C twice, which exits GAP altogether.
For more information, check the section on the (new)
Perhaps the most interesting new covering radius function is
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
When the dimension is about half the length of a code,
neither algorithm will work, although
is specifically designed to avoid memory problems,
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
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
To allow the user to enter values in the
record herself, the function
SetCoveringRadius is provided.
Previous Up Top Next