Asymptotically good codes

Question

In short my question is what are all known explicit constructions of asymptotically good codes over finite alphabet?

In more details: A sequence of codes codes $C_i: F^{k_i}\rightarrow F^{n_i}$ with distances $d_i$ is asymptotically good iff exists constants $R,\delta$ such that $\frac{k_i}{n_i}\geq R, \frac{d_i}{n_i}\geq \delta$. My question is what are all known ways to construct such asymptotically good codes. (Note the question is about finite alphabets)

I can give two examples:

1) Goppa AG codes: http://en.wikipedia.org/wiki/Goppa_code

2) Expander codes: http://en.wikipedia.org/wiki/Expander_code

3) Justesen codes: http://en.wikipedia.org/wiki/Justesen_code

I would like to know an other examples of asymptotically good codes.

Answer 1

Usually the question is interesting for constant alphabet sizes, since otherwise Reed-Solomon codes obviously achieve the Singleton bound.

For constant (but still large) alphabet sizes, there are explicit codes that "approximately" achieve the Singleton bound, and are thus also asymptotically good. See

Venkatesan Guruswami and Piotr Indyk. Linear time encodable and list decodable codes Proceedings of STOC 2003.

Also there are several flavors of Expander and Concatenated Codes (rather than the famous constructions) that are asymptotically good. For example see

"Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs" by Alon et al.

Also there are more sophisticated "concatenated-like" constructions that achieve much more than asymptotic-goodness, for example:

V. Guruswami and A. Smith. Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate, FOCS 2010.

Finally, any construction of codes for stochastic errors (that is, the channel BSC(p)) that achieves constant rate and exponentially small error must be asymptotically good. However, I'm not aware of any such explicit constructions other than concatenated codes (Forney/Justesen and similar variations).

Answer 2

To answer your question, I'd say Asymptotically "good" codes, as defined by the Coding Theory community, are those that can achieve arbitrarily very low probability of incorrect decoding, when decoded OPTIMALLY(which is an NP complete problem) with any value of R(as defined in the question) below the Capacity(as defined by Shannon). This was a definition accepted when MacKay wrote his first paper which gave to the re-birth of Low Density parity Check codes.

The ones that are "Very Good" are those that can achieve the same even at Capacity. MacKay further shows that there can be code constructions that can come very close to the "Very Good" codes even if not decoded optimally i.e. using Iterative Decoding or Message Passsing. Under this class fall all the Modern Codes, the answer to your question:

1. Low Density Parity Check Codes(LDPC, originally invented by Robert Gallagher in 1963)
2. Tornado Codes
3. Fountain Codes
4. Luby Transform Codes

and all the sorts. Basically all of these are interrelated. Most of them are just codes on Graphs. Almost all Modern Codes(Modern codes revolution started with Turbo Codes) fall under the answer to your question.

Turbo Codes is one pretty good exception because it is not a code on Graphs yet it achieves performance very close to Capacity. You can look up all the papers of all these Codes and I'm sure I'd have left out a few of them which may have been discovered but not have become practical because there is one very important criterion for anything to be useful: *Encoding and Decoding algorithms should be Linear in time.