Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
4  
In general, I think not. In particular examples, there is often some trick available. –  Gerry Myerson Apr 14 '13 at 6:47
    
this seems to be a web page to compute it, see bounds on minimum distance of linear codes by Grassl –  vzn Jan 4 at 19:15
    
@vzn: The homepage of Grassl (which I also linked in my answer) is for collecting the best known minimum distances of linear codes of fixed length and dimension. In most of the cases, also generator matrices of those codes are provided. But as far as I see, the page doesn't provide means for the computation of the minimum distance of an arbitrary linear code. –  azimut Jan 5 at 0:06
add comment

2 Answers

As pointed out by Snowball, the problem is inherently hard, see also this paper.

However, it can be done much faster in general than generating all the codewords.

I explain the idea for linear $[n,k]$ codes $C$ with $n = 2k$. First, we construct two generator matrices $G_1 = (I\ A)$ and $G_2 = (B\ 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, xA)$ and $x G_2 = (Bx, 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.

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

share|improve this answer
    
the paper seems to be by Vardy based on url but is not accessible [maybe not a eprint available]. another published citation would be ideal. maybe this ref? (found in another paper) Alexander Vardy. The intractability of computing the minimum distance of a code. IEEE Trans. Inform. Theory, 43(6):1757–1766, 1997. –  vzn Jan 4 at 19:11
    
@vzn: Looks like the link is dead. Yes, it is the 1997 Vardy paper. I've updated the link to the IEEE homepage. –  azimut Jan 5 at 0:02
add comment

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.