<p>The problem for an arbitrary binary code is NP-hard. </p>

<p><a href="https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=641542" rel="noreferrer">Reference:</a> Alexander Vardy, &ldquo;The Intractability of Computing
the Minimum Distance of a Code,&rdquo; <em>IEEE Trans. Inf. Thy.,</em> <strong>Vol. 43</strong> pp. 1757--1766.</p>

CC BY-SA 4.0
2019-05-05T04:13:59.413Z
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
CC BY-SA 4.0
2019-05-03T19:24:03.860Z
2019-05-03T19:24:03.860Z
Peter Shor 
<p>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.</p>

CC BY-SA 4.0
2020-06-26T15:24:32.927Z
2020-06-26T15:24:32.927Z
esabo
<p>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 <span class="math-container">$d$</span> such that there exists <span class="math-container">$d$</span> linearly dependant columns. I am looking in particular to find minimum distance of binary (codes over <span class="math-container">$\mathbb{F}_{2^l}$</span>) quasi-cyclic  of rate q/q+1. Parity check matrix for such codes have a structure
<span class="math-container">$H=[I|C_1|C_2|...|C_m]$</span> where each <span class="math-container">$C_¡$</span> 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 ?</p>

CC BY-SA 4.0
2019-05-05T01:20:01.083Z
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.
Peter Shor 
<coding-theory>
Minimum distance of a code
Root
# Minimum distance of a code

(Asked by: username_0 on 2019-04-03)

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 ?

**Tags:** coding-theory
> **Comments:**
> **username_1**: 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.  

---

## 2 answers

### Answer by username_1 on 2019-05-03. Score: 7

The problem for an arbitrary binary code is NP-hard.

[Reference:](https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=641542) Alexander Vardy, “The Intractability of Computing
the Minimum Distance of a Code,” *IEEE Trans. Inf. Thy.,* **Vol. 43** pp. 1757--1766.

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_2 on 2020-06-26. Score: 2

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.


---

