# Minimum distance of a code

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 ?

• 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. May 5, 2019 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.

• 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.
– Root
May 5, 2019 at 4:13

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.