NOISE is the blight of the information age. It can be far more than an annoyance: if you send instructions to an interplanetary spacecraft, and the message gets scrambled going through the ionosphere, your probe might fire its engines at the wrong time. But now noise has met its match, in the form of two miraculous methods for pulling clear messages out of what was previously considered to be undecipherable static. It鈥檚 like hearing a whisper in a thunderstorm or reading road signs in a blizzard.
These static-bashing technologies, called turbo codes and LDPC codes, are already on their way into your home, programmed into digital TV receivers and computers with third-generation wireless. They are also on their way to Mercury and will soon be used on spaceships bound for Mars.
鈥淭hese codes will be serving the human race for as long as it鈥檚 on the Earth鈥�
Advertisement
The new codes are very close to a perfect technology. No matter how much faster computers become, the codes they use to send data will never get significantly better. You might compare them to the wheel: although it is possible to dress up the wheel in different ways or make it from different materials, you will never improve on its basic shape. 鈥淭hese kinds of codes will be serving the human race for as long as it鈥檚 on the Earth,鈥� says Michael Tanner, a pioneer of LDPC codes who is now the provost of the University of Illinois at Chicago.
Turbo and LDPC codes have nothing to do with spies or security. Quite the opposite: they are designed to preserve data rather than to hide it. They exist to fix an inevitable problem with communication. No communication channel is free of errors: analogue phone lines hiss with noise, radio reception is plagued with static and even the internet loses packets of information from time to time.
But for some applications, perfect fidelity is critical. In other cases it may be less important, but we have got used to it. When you download a photo or a music file over the internet, you expect it not to be corrupted.
Fortunately, perfect communication is possible even over a noisy line. The key is forward error correction 鈥� preparing for errors before they happen by adding redundancy to a message. A military commander does this when calling for 鈥淏ravo company鈥� instead of 鈥淏 company鈥� over a staticky radio channel. It isn鈥檛 an affectation invented for war movies; there鈥檚 a practical reason. Background noise might make 鈥淏鈥� sound a lot like 鈥淐鈥�, but no one can confuse 鈥淏ravo鈥� with 鈥淐harlie鈥�.
Forward error correction works in a similar way. If you send a string of bits through a modem, noise in the phone lines could change the message, say from 鈥�1, 1, 0, 1鈥� to 鈥�1, 0, 0, 1鈥�. It鈥檚 like confusing 鈥淏鈥� with 鈥淐鈥�. The solution is to add redundant information, like the extra syllables in 鈥淏ravo鈥� and 鈥淐harlie鈥�. In digital communication, this could be achieved by sending each bit many times over, so that a moderate amount of noise will leave the message clear. But there are more efficient means than that.
For instance, you might group the string into blocks of four bits and add four 鈥渃heck digits鈥� that are related to the four information bits by four different mathematical formulae. The whole set of eight bits forms a code 鈥渨ord鈥�. If the receiver can find the set among a list of valid code words, it will assume that the message came through cleanly. If it receives an invalid word, it can substitute the nearest valid word. The first to realise the power of this method was Claude Shannon, an engineer at Bell Labs in New Jersey, who established modern information theory in a 1948 paper.
But there is a price to pay for perfection. Shannon also showed that there are two factors controlling the speed at which you can transmit data. One is the bandwidth of your channel. The other is the signal-to-noise ratio. The more noise, the more check digits you must add to each code word to make it understood. Instead of saying 鈥淏ravo鈥� and 鈥淐harlie鈥�, you might have to say 鈥淏ravissimo鈥� and 鈥淐harlemagne鈥�. And the more check digits you are transmitting, the less actual information you can send per second.
Shannon derived a formula for how much information you can send with essentially perfect fidelity at a given signal-to-noise ratio. That formula is now called the Shannon limit, and it is inviolable. If you try to send your data with too few check digits, it will be corrupted. Whatever coding scheme you use, the decoder on the receiving end is bound to confuse some code words with others.
Shannon鈥檚 discovery is as fundamental to the information age as the speed of light is to physics, setting a limit on the speed and performance of all the communication devices we use today. Unfortunately, just as the theory of relativity does not tell you how to build a spacecraft that can approach the speed of light, Shannon鈥檚 formulae do not describe how to approach his limit.
So what error-correcting codes do you need? 鈥淚f you鈥檝e been in this field for very long, you have certainly heard the code designer鈥檚 lament: 鈥楢ll codes are good except the ones we know about鈥�,鈥� says Keith Chugg, an electrical engineer at the University of Southern California in Los Angeles.
For many years, engineers couldn鈥檛 even get close to the Shannon limit. Indeed, photographs from early space missions had some truly horrible blemishes. By the time the two Voyager spacecraft were launched in the late 1970s, things had improved a great deal. But data transmission has continued to be a bottleneck on NASA missions, with the rate limited by the power of the transmitter. Even with the best available codes of the day, when the Jupiter-bound spacecraft Galileo was launched in 1992, it required 60 per cent more power to achieve error-free transmission than it would have needed with a perfect code. To put this into perspective, when NASA spent $80 million to upgrade the Deep Space Network, which is used to receive signals from such spacecraft, the signal-to-noise ratio improved by 25 per cent. A code that let you communicate at the Shannon limit would get you twice that improvement for free.
Before 1993, engineers didn鈥檛 think that was possible. Then came what Robert McEliece of Caltech calls 鈥渢he earthquake鈥�. Claude Berrou of the French National School of Telecommunications in Brest and his collaborator Alain Glavieux announced that they had found a way to get within 10 per cent of the Shannon limit, using what they called a turbo code.
At first nobody believed them. 鈥淚t took us many months to be convinced,鈥� says Fabrizio Pollara of the Jet Propulsion Laboratory in California, who works on NASA鈥檚 communications systems.
An aftershock came later in the decade, when three separate groups of researchers realised that a similar code had been invented way back in 1963. That year, a graduate student at the Massachusetts Institute of Technology, named Robert Gallager, invented what he called low-density parity check (LDPC) codes. They were impractical for the computers of the time, so they passed by almost unnoticed.
These new codes represent an entirely different way of thinking about coding. Instead of focusing on the code words themselves and how to make them as distinctive as possible, Berrou and Glavieux worked on the encoding and decoding process. They replaced 鈥渉ard鈥� decisions with 鈥渟oft鈥� ones, such as 鈥渢here is a 75 per cent chance that this bit is a 1鈥� rather than 鈥渢his bit is a 1鈥�. They also turned the decoding process into a conversation between several decoders, rather than a unilateral decision by one decoder.
And in a break with tradition, they did not prove mathematically that their method worked. 鈥淭he paradigm in coding theory was very mathematical,鈥� says Tanner. 鈥淵ou had to provide proofs.鈥� To this day, there is no formal proof that turbo codes come so close to the Shannon limit. They just do.
The secret to both turbo codes and LDPC codes is a technique called belief propagation. You could liken it to solving a crossword puzzle. Often there will be words or letters that you aren鈥檛 quite sure of. A clue may lead you to think that a letter is probably a B, so you pencil that into the square. As you solve more of the puzzle, your beliefs about the solutions to other clues propagate back to your pencilled-in answer. They may confirm it, giving you the confidence to ink it in, or they may conflict with your earlier belief, prompting you to change the B to a C, say.
One innovation of the new codes was their use of a decoder 鈥減encil鈥� rather than a 鈥減en鈥�. The decoder doesn鈥檛 have to decide outright whether a particular bit is a 1 or a 0. Instead, it can assign a probability that the bit is a 1.
An even more important difference is that there is more than one decoder. Turbo codes use two or more separate decoders, each given a shuffled version of the code word so that if one decoder doesn鈥檛 catch a particular error another one should.
LDPC codes have a huge network of decoders 鈥� one for each bit in a code word (see Diagram). These processors talk to each other, exchanging messages about the likelihood that each bit is a 1. LDPC codes were impractical in Gallager鈥檚 day because you couldn鈥檛 fit enough processors on a chip: a typical LDPC code might have 8192 data bits and 4096 check bits in each code word, which means 12,288 decoders connected in a vast network.
Perhaps most surprisingly, LDPC codes work best when the connections between processors are somewhat random. For years, coding theorists had struggled along with highly structured, non-random sets of code words, the better to make them distinct from one another. The Reed-Solomon code used in CD and DVD players is of this type. But they were barking up the wrong tree: randomness will get you closer to the Shannon limit than mathematical ingenuity.
The list of applications for the new codes is growing. 鈥淥ften our customers are stunned at the improvements,鈥� says Chugg, who co-founded a company called TrellisWare in San Diego. 鈥淚n one example, we demonstrated a turbo-like code over a live satellite link for a large US contractor. During a conference call with the contractor, they kept turning down the transmit power, expecting to break the link, and were truly shocked when they were unable to do so.鈥�
The two kinds of code are now battling it out to dominate communications technology. LDPC codes use less computing power to decode than turbo codes do, so they can be used at higher data rates. But turbo codes had a head start, having been invented four years before LDPC codes were rediscovered. NASA now uses them for such ventures as the Messenger mission to Mercury, which launched last year. LDPC codes will take a few more years to catch up, but Pollara thinks both types will be used eventually.
The standard codes used in commercial applications are not as good as NASA鈥檚, so the improvement will be even greater. The new codes will extend the range of your mobile phone or wireless computer, because they will make up for a weaker signal as you wander away from the transmitter.
Of course, it is no good if your satellite speaks one code and my satellite dish speaks another. Turbo codes鈥� head start has given them an edge in becoming industry standards and they will soon be used in cellphone and next-generation wireless networks. But LDPC codes have some advantages: they are less complicated and less encumbered by patents, as France Telecom patented turbo codes even before Berrou and Glavieux announced them to the world. In 2003, an LDPC code beat six turbo codes to become the new standard for the satellite transmission of digital television.
The techniques used in both codes may have a future outside the communications business. The idea of belief propagation in networks is actually quite old: David MacKay, a coding theorist at the University of Cambridge, traces it back to a 19th-century astronomer and statistician named Thorvald Thiele. Since then, MacKay says, 鈥淚t has been discovered about 10 times over, once for each of 10 fields.鈥� But belief propagation was always believed to be theoretically unsound if the networks had loops in them, because a loop can generate self-reinforcing delusions.
However, the turbo and LDPC codes allow loops. In a randomly wired network, it鈥檚 impossible to avoid them, so Berrou and Glavieux brazenly charged in where, for decades, engineers had feared to tread. Loops didn鈥檛 matter. Somehow the efficiency of the network more than compensates for its rare inaccuracies. 鈥淭he algorithm, albeit invalid, actually works extremely well,鈥� MacKay says.
鈥淏errou and Glavieux brazenly charged in where for decades engineers had feared to tread鈥�
So loopy message-passing may come into vogue in fields other than coding. For example, speech-recognition software might use belief propagation to navigate the ambiguities of human speech. And image processing can be souped up by connecting the pixels of a digital image like the nodes in an LDPC decoder: in 2000, computer scientist Bill Freeman of Mitsubishi Electronic Research Labs demonstrated the use of loopy message-passing to sharpen a blurred picture of a tiger. A similar method could be used to convert old television programmes from low-resolution analogue to high-definition digital formats.
And yet, for all their potential, McEliece thinks that LDPC and turbo codes will eventually be seen as just the final stroke to Shannon鈥檚 original masterpiece. A thousand years from now, he imagines, the Galactic Encyclopedia will read: 鈥淪hannon formulated the notion of channel capacity in AD 1948. Within several decades, mathematicians and engineers had devised practical ways to communicate reliably at data rates within 1 per cent of the Shannon limit鈥︹��
