4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Or Meir Jul 31 '13 at 20:12
  • $\begingroup$ Oh, sorry I didn't realize that. I'll take my answer down in case the two definitions can mean drastically different things. But in a general setting I assumed if you can bound the Minimum distance(relative to Blocklength) by a value that you want, then you'd want that distance to satisfy the Error correction and detection bounds. Now my answer gives an insight into codes that you may not see in terms of relative distance, but these codes operate equivalently even though you don't view their performances just with Relative distance as metric as there are more to them. $\endgroup$ – Sudarsan Jul 31 '13 at 21:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.