Where can I find examples of error correcting codes of the following types?

Question

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) 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.

Answer 1

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. 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. The earliest constructions can be found here and here (although they only give you $m = \rm{poly}(n)$).