Is there a way to compute minimum distance of a code given a systematic parity check matrix? I know that min dist is smallest number $d$ such that there exists $d$ linearly dependant columns. I am looking in particular to find minimum distance of binary (codes over $\mathbb{F}_{2^l}$) quasi-cyclic of rate q/q+1. Parity check matrix for such codes have a structure $H=[I|C_1|C_2|...|C_m]$ where each $C_¡$ is a from class of circulant matrices. It may be useful that one can treat these codes as modules. Or even if there are any approximate algoruihms for this ?
1
-
1$\begingroup$ Since you can take any code, and find a systematic parity check matrix for an equivalent code, the complexity class of this problem doesn't depend on whether there's a systematic parity check matrix or not. $\endgroup$– Peter ShorCommented May 5, 2019 at 1:20
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
The problem for an arbitrary binary code is NP-hard.
Reference: Alexander Vardy, “The Intractability of Computing the Minimum Distance of a Code,” IEEE Trans. Inf. Thy., Vol. 43 pp. 1757--1766.
answered May 3, 2019 at 19:24
-
$\begingroup$ Shot anything in particular for QC codes or may be an approximate algorithm for finding minimum distance. What I am looking for is a way to construct QC codes with high minimum distance. So even algorithms giving lower bounds (non-trivial) are worth a try. $\endgroup$– RootCommented May 5, 2019 at 4:13
$\begingroup$
$\endgroup$
I hate to reopen an old topic but I just want to add for future searches that there is no way to do this in general unless you can logic-out the weight enumerators, but for a specific instance of a code in the family the Brouwer-Zimmermann algorithm gives you what you want. This is built-in to many coding theory programming libraries.
