2
$\begingroup$

I know that to determine the minimum distance of a code given its basis we can follow this procedure:

Let $\{ c_1, \ldots, c_k \}$ be a basis for a code of length $n$ and dimension $k$. Then the generator matrix is $B$ whose rows are $c_i$. I know that row ops on $B$ do not change the code so we can assume that $B = (P | I_k)$. Now the parity check matrix is given by $A = (P^\top | I_{n-k})$ and the minimum distance of the code is the minimum number of columns of $A$ that are linearly dependent.

The problem is that this approach can be very tedious for large codes as we have to reduce $B$ to echelon form, so my question are:

1) Is there in general an easier approach? Eg. looking at the weight of the codewords in the basis.

2) If $C$ is cyclic should I also follow the same approach?

$\endgroup$
4
  • 1
    $\begingroup$ 1) There is and its implemented in Magma. 2) For specific codes like BCH codes there are better methods due to the structure of the codes. $\endgroup$
    – Wuestenfux
    May 5, 2020 at 15:58
  • $\begingroup$ What is Magma?? $\endgroup$
    – john
    May 5, 2020 at 16:05
  • $\begingroup$ magma.maths.usyd.edu.au/magma $\endgroup$
    – Riccardo
    May 5, 2020 at 16:07
  • $\begingroup$ Computer algebra system. $\endgroup$
    – Wuestenfux
    May 5, 2020 at 16:07

1 Answer 1

Reset to default
3
$\begingroup$

See the paper "The intractability of computing the minimum distance of a code" by Alexander Vardy in the IEEE Transactions on Information Theory, vol. 43, November 1997. Since this is behind a paywall, I quote the abstract below.

Abstract: It is shown that the problem of computing the minimum distance of a binary linear code is NP-hard, and the corresponding decision problem is NP-complete. This result constitutes a proof of the conjecture of Berlekamp, McEliece, and van Tilborg (1978). Extensions and applications of this result to other problems in coding theory are discussed.

$\endgroup$
2
  • $\begingroup$ Thanks for the exact quote. I am favoriting this question so that (hopefully) I can retrieve it the next time this question gets asked. $\endgroup$
    – Jyrki Lahtonen
    May 5, 2020 at 20:54
  • $\begingroup$ @JyrkiLahtonen Thanks. Seven years ago, you edited this question whose answers also reference the Vardy paper. $\endgroup$
    – Dilip Sarwate
    May 6, 2020 at 16:16

Your Answer

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

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