<p>If you just need any code $E : \{0,1\}^n \to \{0,1\}^m$ where $m=O(n)$ and where the distance is linear in $m$, then what you are looking for is called an "asymptotically good code". There are many explicit constructions of such codes, and you can find the basic ones in lecture notes of courses about coding theory. For example, you can find a description of a classic construction in Lecture 7 <a href="http://people.csail.mit.edu/madhu/ST13/" rel="noreferrer">here</a>. Another example of a construction is expander codes, which are described in Lecture 14 there.</p>

<p>If you are looking specifically for codes where the distance between any two codewords is close to $\frac{m}{2}$, and in particular is <em>upper</em> bounded by $(1+\delta)\cdot \frac{m}{2}$, then things are a bit more complicated. Such codes are tightly related to objects called "$\epsilon$-biased sets", which have been studied for quite a while in TCS. You can find a very recent construction of such codes <a href="https://eccc.weizmann.ac.il/report/2017/041/" rel="noreferrer">here</a>. The earliest constructions can be found <a href="http://www.wisdom.weizmann.ac.il/~naor/PAPERS/bias.pdf" rel="noreferrer">here</a> and <a href="http://www.tau.ac.il/~nogaa/PDFS/aghp4.pdf" rel="noreferrer">here</a> (although they only give you $m = \rm{poly}(n)$).</p>

CC BY-SA 3.0
2017-03-07T23:05:14.407Z
Very helpful, thank you. I'm still a little too unfamiliar with the territory to extract precisely what I need, but this is a very good starting point to learn from.
JMAA
CC BY-SA 3.0
2017-03-06T17:10:06.253Z
2017-03-08T20:00:01.250Z
2017-03-08T20:00:01.250Z
Or Meir
<p>First, apologies if this question is in appropriate or trivial for this site. I'm a physicist looking for some help outside his comfort zone.</p>

<p>In <a href="https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.87.167902" rel="noreferrer">PRL 87 167902 (2001)</a> it is claimed that </p>

<p>"...for an arbitrarily small $\delta&gt;0$ there exists an error-correcting code $E: \{0,1\}^n \rightarrow \{0,1\}^m$ with $m\leq n / \delta^c$ (for some constant $c$) such that the Hamming distance between any two distinct code words $E(x)$ and $E(y)$ is between $(1 - \delta)m/2$ and $(1 + \delta)m/2$." </p>

<p>In the paper, this is known because of non-constructive proofs of existence. I would like to know if any explicit examples of such codes (or similar ones, or even better ones) exist, given that paper was 16 years ago.</p>

<p>In particular, I'm interested in codes $E: \{0,1\}^n \rightarrow \{0,1\}^m$ where $m = O(n)$ and the Hamming distance between two distinct code words has a lower bound at least linear in $m$ (I'm pretty flexible about the behaviour with $\delta$, as I just need the $\delta = 1/2$ case).</p>

<p>I ask here becuse I'm sure this will be a very easy question to the correct person, but I am not that person and I'm not sure where best to start looking. Any hints of where to look would be much appreciated.</p>

<reference-request><lower-bounds><quantum-information>
Where can I find examples of error correcting codes of the following types?
JMAA
# Where can I find examples of error correcting codes of the following types?

(Asked by: username_0 on 2017-02-26)

First, apologies if this question is in appropriate or trivial for this site. I'm a physicist looking for some help outside his comfort zone.

In [PRL 87 167902 (2001)](https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.87.167902) it is claimed that

"...for an arbitrarily small $\delta>0$ there exists an error-correcting code $E: \{0,1\}^n \rightarrow \{0,1\}^m$ with $m\leq n / \delta^c$ (for some constant $c$) such that the Hamming distance between any two distinct code words $E(x)$ and $E(y)$ is between $(1 - \delta)m/2$ and $(1 + \delta)m/2$."

In the paper, this is known because of non-constructive proofs of existence. I would like to know if any explicit examples of such codes (or similar ones, or even better ones) exist, given that paper was 16 years ago.

In particular, I'm interested in codes $E: \{0,1\}^n \rightarrow \{0,1\}^m$ where $m = O(n)$ and the Hamming distance between two distinct code words has a lower bound at least linear in $m$ (I'm pretty flexible about the behaviour with $\delta$, as I just need the $\delta = 1/2$ case).

I ask here becuse I'm sure this will be a very easy question to the correct person, but I am not that person and I'm not sure where best to start looking. Any hints of where to look would be much appreciated.

**Tags:** reference-request, lower-bounds, quantum-information


---

## 1 answers

### Answer by username_1 on 2017-03-06. Score: 9 | Accepted answer

If you just need any code $E : \{0,1\}^n \to \{0,1\}^m$ where $m=O(n)$ and where the distance is linear in $m$, then what you are looking for is called an "asymptotically good code". There are many explicit constructions of such codes, and you can find the basic ones in lecture notes of courses about coding theory. For example, you can find a description of a classic construction in Lecture 7 [here](http://people.csail.mit.edu/madhu/ST13/). Another example of a construction is expander codes, which are described in Lecture 14 there.

If you are looking specifically for codes where the distance between any two codewords is close to $\frac{m}{2}$, and in particular is *upper* bounded by $(1+\delta)\cdot \frac{m}{2}$, then things are a bit more complicated. Such codes are tightly related to objects called "$\epsilon$-biased sets", which have been studied for quite a while in TCS. You can find a very recent construction of such codes [here](https://eccc.weizmann.ac.il/report/2017/041/). The earliest constructions can be found [here](http://www.wisdom.weizmann.ac.il/~naor/PAPERS/bias.pdf) and [here](http://www.tau.ac.il/~nogaa/PDFS/aghp4.pdf) (although they only give you $m = \rm{poly}(n)$).

> **Comments:**
> **username_0**: Very helpful, thank you. I'm still a little too unfamiliar with the territory to extract precisely what I need, but this is a very good starting point to learn from.  

---

