Currently, when GAP is calculating the minimum distance, it examines the weight of every possible linear combination of rows in . The following algorithm is much faster.
Though this is still an exponential time algorithm problem, the vectors being compared are of length rather than length . There was an increase in speed by a factor over 1000 in some examples3. Additionally, this algorithm works for all Galois fields of order .
The probabilistic algorithm used to reduce this to polynomial time was initially proposed by J. S. Leon [LEO] and later modified by F. Chabaud [CHA]. One iteration of the algorithm given in Chabaud's paper is as follows:
However, sometimes step (3) is impossible because gaussian elimination does not always produce a matrix in standard form. For example, take any code with generator matrix in row reduced echelon form which is not of the form .
Here is a faster version of Leon's algorithm that was discovered jointly with my advisor in the process of working on this project.
Chabaud [CHA] and Barg [BARG] have discussed finding optimal values for , , and . We have selected to be , to be 3, and to be since those values seem optimal for codes of length less that .
To perform step (4), the row numbers and coefficients must be saved from step (3). However, the standard command in GAP (written in the C programming language and part of the GAP kernel) for searching through row combinations for a weight does not return this data. In the binary case, an algorithm for finding minimum weight is simply a matter of examining the sum of up to row combinations. A relatively fast implementation (in GAP) of this algorithm has been written in the binary case. However, for codes over , especially if is moderately large, a fast implementation of this algorithm requires modifying the standard GAP command. Since this command is part of the kernel, it will also be necessary to recompile GAP before it can be used in any implementation. This coding in the C programming language has not yet been implemented.