Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I recently came across Dan Piponi's blog post An End to Coding Theory and it left me very confused. The relevant portion is:

But in the sixties Robert Gallager looked at generating random sparse syndrome matrices and found that the resulting codes, called Low Density Parity Check (LDPC) codes, were good in the sense that they allowed messages to be transmitted at rates near the optimum rate found by Shannon - the so-called Shannon limit. Unfortunately the computers of the day weren't up to the task of finding the most likely element of M from a given element of C. But now they are. We now have near-optimal error correcting codes and the design of these codes is ridiculously simply. There was no need to use exotic mathematics, random matrices are as good as almost anything else. The past forty years of coding theory has been, more or less, a useless excursion. Any further research in the area can only yield tiny improvements.

In summary, he states that the rate of LDPC codes is very near channel capacity—so near that further improvements would not be worth the while.

So, my question is: What does modern research in error-correcting codes entail? I noticed that Dan did not mention what channel the rate of LDPC codes approach the capacity of, so maybe there exist channels that LDPC codes don't work well on? What other directions does modern research in the field explore?

share|improve this question
    
See also this MO question. –  Jyrki Lahtonen Oct 24 '12 at 7:17

3 Answers 3

up vote 6 down vote accepted
+200

This is largely true in the sense that long LDPC codes are within a fraction of a dB of the Shannon limit in AWGN channel. Their design (by a process called density evolution - don't look at me, I don't know the math) also seems to be relatively simple. It depends on stochastic math as opposed to algebra/combinatorics of finite fields/rings.

My limited experience only allows me to make the following remarks:

  1. The block length of an LDPC code needs to be relatively large. This is one of the reasons they were not chosen to LTE standard (European/Asian 4G cellular standard). My understanding about the `best' code in a radio channel is (as a function of the block length): less than 100 bits => use an algebraic block code, 40-400 bits => use a convolutional code, 300-20000 bits => use a turbo code, 5000 bits+ => use an LDPC code (the intervals overlap as I am not willing to bet the family fortune on any one of them). IIRC this is how it is done in LTE, except that in that cellular standard the longest data block has 6144 bits (so handled with a turbo code).
  2. The design of an LDPC code needs to take into account that it is usually not practical to base it on a random Tanner graph with the prescribed weight distribution. In particular, when it is supposed to be used on a handheld device. The routing problem of the belief propagation algorithm becomes prohibitive otherwise. So the LDPC codes specified for radio communication standards a few year back (DVB-S/T2 in Europe, Mediaflo in the US) were designed around a particular decoding circuitry, or rather the Tanner graphs had to come from a certain kind of a family. I have never been truly up to speed with these aspects, so some progress may have been made.
  3. When higher order modulation is used there are further problems and considerations that need to be taken into account. It is not entirely obvious that we should stick to LDPC codes based on bits alone in that case, because the channel will create dependencies among the LLRs of individual bits. But the BP algorithm becomes very complicated, if we want to feed something other than LLRs of individual bits to it.
  4. Getting rid of the error floors is still a challenge. Alas, I'm not up to speed with that either. Possible workarounds involve using catenated code with a light weight algebraic outer code handling the residual errors.

Caveat: I have only studied this cursorily (enough to implement an LDPC code and analyze some of them). These are recollections and impressions rather than hard facts. You can get the minutes of the relevant meetings of workgroup in charge of this within LTE from the web pages of 3GPP (=third generation partnership project).

Other types of codes will remain to be useful for specific purposes. There is no substitute to RS (or AG, if you need longer blocks), when you only have hard byte errors. LDPC (and Turbo) codes are designed with soft bit errors (=reliability estimates of received bits) in mind. This is a valid assumption in all wireless communication. Also network coding appears to be a hot topic currently. There the code operates at the level of data packets that may or may not arrive at all. Also look up Raptor code, if this type of problems are of interest to you.

Algebraic coding theory is not dead yet, but it does concentrate on problems other than designing ECCs for bulk data transmission. An algebraic machinery yielding LDPC code designs guaranteed to have very low error floors (= high minimum Hamming distance) may be out there, but I don't know what it would be.

share|improve this answer

To make a long story short: No, there is no end to coding theory! Yes, there exist many codes, which will operate (at least for simple channel models) in within a fraction of dB of the Shannon limit. To mention a few: turbo-codes, LDPC codes, and others.

Just recently, Arikan invented so called "polar codes" which are (theoretically) proven to reach the Shannon limit for infinitely long code words. These are the first codes, for which such a proof is given. The decoding of these polar codes is performed by (for example) successive interference cancellation (SIC) decoder or belief propagation (BP) decoder.

The drawback of polar codes relies in their code construction, i.e. finding the position of the so called "frozen bits" (code bit positions). For BEC and BSC channels, this can be solved in a short period of time. (Of course, only for finite code word lengths!) For other channel models with a binary input and continuous output distribution, the finding of the frozen positions is not trivial!

To sum up everything: In my opinion, we now have a code (polar code), which is proven to reach the Shannon limit for infinitely long code words. But, practically this code needs large code word lengths to even come close to the performance of other codes (LDPC and others). In (for example) wireless communication, large code word lengths are of no use, as the channel changes during the time and the delays in an ARQ-process are getting larger. Thus, fairly good codes for small codes word lengths are (practically) needed.

My 2 cents.

share|improve this answer

I can't say I'm an expert in error correction, but I know some things.

If I recall correctly, decoding an LDPC can be pretty challenging if you want to operate near full capacity in a noisy channel with high bandwidth. And latency can be an issue if you need to use long codes.

Also, again IIRC, LDPC's are good for uniform noise, but noise isn't always uniform. In many channels, noise comes in bursts, so there is some challenge in designing error correction schemes that efficiently protect against bursts of noise.

And, of course, the math involved in designing ECC applies to tasks other than communicating across a channel. Some mathematical problems can be set up in a way that they can be solved directly by various sorts of codes. Also, I believe much of the development in efficient finite field arithmetic and polynomial algorithms was motivated by research into efficient error correction.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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