Efficient computation of the minimum distance of a binary linear code

Question

I need to find parameters $n$, $k$ and $d$ of a binary linear code from its Generator Matrix.

How can I find parameter $d$ efficiently?

I know the method that compute all the codewords and take minimum non-zero weight code will be the minimum distance. but it's an exponential time algorithm. Is there any efficient algorithm to do the same?

Answer 1

Finding the minimum distance $d$ of a linear code is equivalent to finding its minimum weight. According to On the inherent intractability of certain coding problems, given the check matrix, determining whether or not there exists a codeword of some fixed weight $w$ is a NP-complete problem for binary linear codes.

As Gerry commented, you can easily find the minimum distance for particular codes. For example:

1. If you have a Reed-Solomon code of length $n$ and dimension $k$, its minimum distance is $n-k+1$.

2. If you have a Hamming code, its minimum distance is $3$.

Answer 2

As pointed out by Snowball, the problem is inherently hard, see here and also here.

However, it can be done much faster in general than generating all the codewords. The best practical method known is the Brouwer-Zimmermann algorithm.

I explain the idea for linear $[n,k]$ codes $C$ with $n = 2k$. First, we construct two generator matrices $G_1 = (I\mid A)$ and $G_2 = (B\mid I)$ of $C$ where $I$ is the $(k\times k)$ unit matrix and $A,B$ are two $(k\times k)$ matrices. This is only possible if the positions $1,\ldots,k$ and $k+1,\ldots n$ form two information sets of $C$. If this is not the case, we have to find a suitable coordinate permutation first.

Now a codeword of weight $w$ has weight at most $\lfloor w/2\rfloor$ either in the first or in the second $n$ coordinates. Thus, we can find all codewords of weight $\leq w$ among the codewords $x G_1 = (x \mid xA)$ and $x G_2 = (Bx \mid x)$, where $x$ is a vector of length $k$ and Hamming weight at most $\lfloor w/2\rfloor$. So we can find the minimum distance $d$ of $C$ if we do this iteratively for all $w = 1,2,3,\ldots, d$.

In this way, you have to generate only a small fraction of all the codewords to find the minimum distance, and the idea can be generalized to any linear code. The first step then is to find a covering of the coordinates with information sets. However, the algorithm is still exponential, of course.

To my knowledge, the algorithm has been discovered by Andries Brouwer for self-dual codes (where we are in the case $n = 2k$ and moreover, by self-duality we can take $B = -A^\top$) and generalized by Karl-Heinz Zimmermann to general linear codes. The earliest published source of this algorithm I'm aware of is on pages 30–33 in the (German) book

Anton Betten, Harald Fripertinger, Adalbert Kerber, Alfred Wassermann, Karl-Heinz Zimmermann: Codierungstheorie: Konstruktion und Anwendung linearer Codes, Spinger, 1998, ISBN 3-540-64502-0, link

A few more comments:

• All non-zero scalar multiples of a codeword have the same weight and thus, it is enough to touch a single representative in the enumeration. For $q$-ary linear codes, this is a speedup by the factor $q-1$ (and hence only relevant for non-binary linear codes).

• If the investigated code has nontrivial automorphisms (for instance cyclic codes), these may be used to further reduce the number of codewords in the enumeration.

• If the code $C$ has large dimension, such that the dimension of $C^\perp$ is small, it might be better not to use the Brouwer-Zimmermann algorithm. Instead, enumerate all codewords of $C^\perp$ to determine the weight enumerator of $C^\perp$ and apply the MacWilliams identitites to get the weight enumerator (and in particular the minimum distance) of $C$.

• The webpage codetables.de is a valuable source for bounds on the best known minimum distances for fixed $q$, $n$ and $k$.