Slashdot Mirror
Turbo Codes Promise Better Wireless Transmission
captain igor writes "IEEE is running a story about two French professors that have created a new class of encoding, called 'Turbo Codes,' that will allow engineers to pass almost twice as much data through a given communications channel, or equivalently, the same amount of data at half the power. The new codes allow the Shannon Limit (the theoretical maximum capacity of a channel) to be approached to, currently, within .5 dB. Scientists hope that this breakthrough will revolutionize wireless communications, especially with the coming reclamation of large swaths of the EM spectrum." As the article points out, such codes are in use now, but seem poised for much wider implementation.
I live in a rural area, where we are sometimes lucky that we have a signal, let alone a good one. This could improve the reception for us a lot. Either that, or it doubles the battery life of the cell phones. Either way, I am happy. Although I wonder if this coding could be used in wireless devices as well. Hopefully this could somehow be used to help limit the battery drain of WiFi on a laptop/PDA.
Could turbo codes be used with a 56K modem giving somewhere around 80kbps of bandwidth?
Is there a similar Law to Moores law (or a combination of such) that could be applied to this compression of data and the effective use of the spectrum? As time goes I feel we are going to see the need for the available ammount of wireless transmission medium to increase. How long before we hit the theoretical limit of data transmission and the planet is saturated?
Just interested...
Does it go on forever?
Briefly, the big problem in data communication is achieving the Shannon limit, which is the maximum theoretical data rate at which information can be transmitted with arbitrarily low probability of error. Shannon proved his result in 1948, but until the Turbo guys, nobody knew how to achieve it.
The main problem is that optimal decoding of any non-trivial code is NP-hard, which has been known for about 30 years now (i.e., the only known algorithm has exponential complexity in the code length). The Turbo breakthrough was to show that a suboptimal decoder with O(n) complexity for code length n could nonetheless achieve excellent results. This is the so-called "Turbo principle".
There is an even "newer" class of codes called Low-Density Parity-Check Codes that can beat turbo codes. Turbo codes have a small gap to the Shannon limit, and these new codes can potentially eliminate the gap. Small gains are a big deal; the rule of thumb is that 1 dB of gain is equal to a million dollars of annual revenue for a wireless provider.
The twist is that these LDPC codes were actually proposed in a 1963 PhD thesis, but were disregarded as beyond the computational abilities of the time. They were only "rediscovered" in 1996, after the Turbo code furore.
Toronto-area transit rider? Rate your ride.
It's odd that "turbo code" in the satellite biz means one particular code patented by France Telecom.
It's more odd "turbo code" has been claimed to be only one instance of a class of
Low Density Parity Checking (LDPC) codes.
It's greatly odd we don't refer to all instances of this class of coding as "Gallager Codes".
If the demodulator is recursive, then it's a Gallager code?!
Lots of /.ers have been quick to point out that turbo codes have been around since 1993. However, the IEEE article points out that LDPC ( low density parity check) codes were invented in the early 1960s. Researchers have gotten the LDPC codes to outperform the turbo codes, and to top it off, the LDPC patents have all expired, meaning no royalty fees like turbo codes.
My first slashdot post ... be gentle!!!
The neat thing about Turbo codes is that they're being used in the 3G cell phone standards (along with various other codes.) Turbo codes are powerful because they are iterative: they make several approximations at the information sent across the wire (or lack of wire, heh).
This allows the system to do a good job of guessing what the original message is quickly. If you're interested in Turbo Codes, one of my former professors has done a lot of work with them, and has links to other turbo code sites on his website:
http://www.csee.wvu.edu/~mvalenti
Click on the turbo code link.
Actually, as someone above pointed out, it is slightly similar to a turbo exhaust. You take the output of the decoder (its guesses basically) and feed it back into the decoder for another pass. As you iterate over the data block in different dimensions, thus after correcting one section in one axis, you might be able to correct a different section in another axis that previously had too many errors to correct.
Back to the point, it is somewhat similar to a turbo, more so than most things that use the name.
nosphalot is correct: The Turbo breakthrough was that they determined that by using feedback, just as in an engine turbo, you could get arbitrarily close to Shannons limit.
;.)
The key idea is that this feedback gives you an infinite impulse response, i.e. in theory all bits ever transmitted through such a channel will continue to affect it for ever after.
Even if you do limit the feedback time to more reasonable levels, you can still get a very useful increase in channel capacity.
It is also important to notice that such a channel must have significant delay, i.e. here's another reason to complain about being lagged.
Terje
"almost all programming can be viewed as an exercise in caching"