65.146 IncreaseCoveringRadiusLowerBound

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.

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.

Previous Up Top Next
Index

GAP 3.4.4
April 1997