IncreaseCoveringRadiusLowerBound( code [, stopdistance ] [, startword ] )
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)^n
(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.
InfoCoveringRadius can be set to
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
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
The only way to find out the best value of
CRMemSize is by
Previous Up Top Next