Algorithms

Currently, when GAP is calculating the minimum distance, it examines the weight of every possible linear combination of rows in $G$. The following algorithm is much faster.

Algorithm 1  

1. After replacing $C$ by a permutation equivalent $C'$, one may assume the generator matrix has the following form $G=(I_{k} \, \vert \, A)$, for some $k \times (n-k)$ matrix $A$.

2. Find the minimum distance of the code spanned by the rows of $A$. Call this distance $d(A)$. Note that $d(A)$ is equal to the $d({\bf v},{\bf0})$ where ${\bf v}$ is some proper²linear combination of $i$ distinct rows of $A$.

3. $d(C)=d(A)+i$, where $i$ is as in step (2).

Though this is still an exponential time algorithm problem, the vectors being compared are of length $n-k$ rather than length $n$. There was an increase in speed by a factor over 1000 in some examples³. Additionally, this algorithm works for all Galois fields of order $q\geq 2$.

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:

Algorithm 2   Let $q$ be a power of a prime $p$ and let $C$ be a linear code of dimension $k$ over $GF(q)$ as above. This algorithm has input parameters $s$ and $\rho$, where $s$ is an integer between $2$ and $n-k$, and $\rho$ is an integer between $2$ and $k$.

(1)

Find a generator matrix $G$ of $C$.

(2)

Randomly permute the columns of $G$.

(3)

Perform Gaussian elimination on the permuted matrix to obtain a new matrix of the following form:

$$G=(I_{k} \, \vert \, Z \, \vert \, B)$$ (3)

with $Z$ a $k\times s$ matrix.

(4)

Search $(I \, \vert \, Z)$ for at most $\rho$ rows that lead to codewords of weight less than $\rho$.

(5)

For these codewords, compute the weight of the whole word.

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 $(I \, \vert \, A)$.

Here is a faster version of Leon's algorithm that was discovered jointly with my advisor in the process of working on this project.

Algorithm 3   Notation as in Algorithm 2.

(1)

Replace, if necessary, $C$ by a permutation equivalent code $C'$ with a generator matrix in standard form, $G=(I_{k} \, \vert \, A)$.

(2)

Select $s$ columns at random from the matrix $A$ and call the resulting $k\times s$ matrix $Z$.

(3)

For each $i\leq \rho$, find the linear combination of exactly $i$ rows of $(I \, \vert \, Z)$ for vectors of smallest weight.

(4)

For these vectors, compute the weight of the associated codeword.

(5)

Find the minimum weight of the codewords from (4). Call this $d_Z$.

(6)

Repeat this algorithm some multiple $m$ times and return the most commonly occurring value of $d_Z$.

Chabaud [CHA] and Barg [BARG] have discussed finding optimal values for $\rho$, $s$, and $m$. We have selected $m$ to be $7$, $\rho$ to be 3, and $s$ to be $n-k$ since those values seem optimal for codes of length less that $100$.

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 $\rho$ row combinations. A relatively fast implementation (in GAP) of this algorithm has been written in the binary case. However, for codes over $GF(q)$, especially if $q>2$ 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.