# Asymptotically good codes

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.

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

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)
• I believe Klim referred to a different definition of "asymptotically good codes" - the one commonly used when discussing the adversarial noise setting: A family of codes ${C_k}_k$ is asymptotically good if all the codes in the family have rate and relative distance that are lower bounded by a constant that is independent of k, and have alphabet whose size is a constant that is independent of k. Jul 31 '13 at 20:12