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
    $\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 Shor May 5 '19 at 1:20

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.

  • $\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$ – Root May 5 '19 at 4:13

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.