First, let us compare GUAVA's minimum distance command MinimumDistance with an implementation of Algorithm 1, called MinDist. The first output is the minimum distance, the second is the internal GAP time it takes for the computation.

gap> Read("/home/wdj/gapfiles/codes/foster_mindist8.gap");
#I  Package ``GUAVA'': the C code programs are not compiled.
#I  Some GUAVA functions, e.g. `ConstantWeightSubcode', will be unavailable.
#I  See ?Installing GUAVA
Loading  GUAVA 1.82 (GUAVA Coding Theory Package)
by Jasper Cramwinckel,
   Erik Roijackers,
   Reinald Baart,
   Eric Minkes,
   Lea Ruscio, and
   David Joyner (http://web.usna.navy.mil/~wdj/homepage.html).
gap> C:=RandomLinearCode(20,15,GF(3));
a linear [20,15,1..3]2..5 random linear code over GF(3)
gap> MinimumDistance(C);time;
gap> MinDist(C);time;

Next, let us compare an implementation of Algorithm 3, called MinDistLeon, to GUAVA's minimum distance function. The 0 indicates that it finished almost instantly. The 5 elements of the array are the minimum distances found in each of 5 trials. The second and third arguments are $ \rho$ and $ s$, respectively.

gap> Read("/home/wdj/gapfiles/codes/foster_mindist6.gap");
gap> C:=RandomLinearCode(40,20,GF(2));
a linear [40,20,1..7]6..20 random linear code over GF(2)
gap> MinimumDistance(C);time;
gap> MinDistLeon(C,3,3,5);time;
[ 5, 5, 5, 5, 6 ]

Concluding Remarks In the process of writing this code, my advisor and I discovered that GAP had an error in one of it's kernel functions. In fact, this was a known error that the developers were not able to track down until we provided them with code that caused GAP to crash. This enabled the developers to patch the kernel. Not essential to this project, but a nice benefit.

The essential parts of the project were writing MinimumDistance and MinimumDistanceLeon. The GAP code for these programs are attached as Appendices.

The improved algorithm presented here is included in version 1.9 of GUAVA (released 4-2004).

Next: Application to McEliece Public Up: foster_final_report Previous: Algorithms   Contents
David Joyner 2004-04-27