0
$\begingroup$

The minimum distance is easy to compute, and so determine the error correcting/detection capabilities of a code, by enumerating all possible pairs of codewords and computing the hamming distance between them.

This procedure is not practical when the codes are very large, as it amounts to a brute force search. How can I know the error correcting capabilities of a large random code?

$\endgroup$
2
  • 2
    $\begingroup$ The short answer is: You cannot. $\endgroup$ Jun 29 '16 at 12:14
  • 2
    $\begingroup$ If the code is linear, then the minimum distance equals the minimum Hamming weight, making brute force search somewhat less brutal. $\endgroup$ Jun 29 '16 at 12:50
1
$\begingroup$

I repeat what the comments say: There is not a general efficient way to compute the minimum distance of a code. For the linear codes (practically all real codes) it's slightly simpler, as it equals the minimum Hamming weights of all codewords (excepting the zero codeword, of course).

Another property is: the minimum code equals the minimum number of columns of $H$ (parity check matrix) such that they sum up to zero. This property does not usually help to compute the distance, it instead can help to compute the code (especially Hammming codes).

For convolutional codes, the minimum distance is related to the minimum length path that (in the state transition diagram) starts from the zero state and returns to it.

But I want to stress this: you say that $d_{min}$, the minimum distance

determine the error correcting/detection capabilities of a code

That needs some clarification; $d_{min}$ only bounds the maximum number of bits in block that can be corrected/detected. But that's not the holy grail. I mean that that parameter is not necessarily what we are primarily interested; in general, what we really want is to minimize the overall probability of error. And this is not a function of $d_{min}$, it's more complex. Even more, MacKay (see chapter 13) argues that the "obsession with distance" (his words) was detrimental for the progress towards better codes. It does not really matter if the distance is small for a few codewords, if by paying that price we attain a good average distance and hence a low probability of error.

$\endgroup$
1
  • $\begingroup$ Thank you @leonbloy. I will consult the chapter you cited. $\endgroup$
    – user154230
    Jul 1 '16 at 10:39
0
$\begingroup$

While it is indeed hard to calculate minimum distance exactly, but if the code is large and random, the minimum distance is very likely to be concentrated around a certain point, governed by the Gilbert-Varmashov bound

$$n-k \approx \log_q \sum_{j=0}^{d-2}\binom{n-1}{j}(q-1)^j.$$

See http://www.cs.cmu.edu/~venkatg/teaching/codingtheory/notes/notes2.pdf for instance.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy