Discovery From Moonbounce to Hard Drives: Correcting More Errors Than Previously Thought Possible
What does a Nobel laureate need to bounce a radio signal off the moon? A good errorcorrecting code, for one thing. Now, a breakthrough errorcorrection method has turned almost 40 years of conventional wisdom in digital communications on its head.
August 11, 2004
Princeton University's Joseph Taylor, ham radio operator and recipient of the 1993 Nobel Prize in Physics, bounces radio signals off the moon. Amateur radio operators use such moonbounce signals to make longdistance contacts, pushing the limits of radio communications, and Taylor has developed a computer program to get better reception of digital messages encoded in the extremely weak signals.
Moonbounce contact "is the Mount Everest of ham radio  so of course some people want to do it," Taylor said. "At the power levels permitted to amateur radio operators, and with the sort of antennas that can be built by an amateur, moonbounce is possible  but only barely."
Now, thanks to two pairs of NSFsupported scientists whose breakthroughs turned almost 40 years of conventional wisdom in communications theory on its head, Taylor's program can detect messages in moonbounce signals nearly two times fainter than before.
All this might be just a theoretical curiosity except that the very same errorcorrecting codes used in Taylor's program are used millions of times every minute for reading data from computer hard drives, listening to CDs and even viewing images sent back by space probes.
In 1960, Irving Reed and Gustave Solomon achieved immortality by inventing a scheme for catching and correcting errors in digital messages. And in 1968, Elwyn Berlekamp devised an efficient decoding algorithm that made it possible to apply the socalled ReedSolomon codes in practice.
Such errorcorrecting codes are critical to all digital communications, which transmit information as long strings of 0s and 1s, each called a "bit." Sending and receiving such information might seem blackandwhite  a bit is either 0 or 1, after all  but realworld devices are always less than perfect. Errorcorrecting codes save the day when a physical device confuses a 0 with a 1, or vice versa.
Today's CD and DVD players, for example, use a variation of Berlekamp's algorithm to correct error bursts as long as 4,000 bits  about 2.5 millimeters along the surface of a scratched CD.
Despite the improvements made over the years, one thing didn't change: Everyone knew the limit on the number of errors ReedSolomon codes could correct. If a message had more errors than this limit, the information was lost.
Then, the first pair of NSFsupported scientists showed that the wellknown limit was wrong. In the mid1990s, MIT computer scientist Madhu Sudan surprised everyone by showing that ReedSolomon codes could correct more errors than previously thought possible. Later work with his thendoctoral student Venkatesan Guruswami, now at the University of Washington, raised the limit even further.
"After more than 30 years of work on ReedSolomon codes, we found that we could recover more errors," Sudan said. "Just the fact that everyone had it wrong after all those years is surprising. The difference seems small, but it turns out to have practical repercussions."
For his breakthrough, Sudan received the 2002 Rolf Nevanlinna Prize, awarded by the International Mathematical Union for outstanding contributions in the mathematical aspects of information science. That same year, Guruswami received the Association for Computing Machinery's award for the best doctoral dissertation in computer science and engineering.
The previously accepted ReedSolomon errorcorrection limit had persisted, in part, because of a worstcase scenario. Two messages could theoretically have errors just over the limit such that no known method could decide which was the correct message or, in fact, do anything reasonable to cope with such errors.
Sudan found something reasonable to do. The same realworld randomness that leads to the need for errorcorrecting codes in the first place also means that the worstcase scenario would rarely, if ever, occur in the realworld. "It's not something you'd expect to see from your CD player on the fly," Sudan said.
In other words, the new method can correct slightly more errors just fine. Even better, the GuruswamiSudan method would let you keep your CD and DVD collections and, in fact, any data recorded with ReedSolomon codes. Only the players have to change.
However, correcting "slightly more" errors is not reason enough to reengineer the world's hard drives. Besides, current ReedSolomon decoders work in hundredths or millionths of a second, whereas the GuruswamiSudan method would take minutes or hours.
That's where the second pair of NSFsupported scientists come in. Ralf Koetter of the University of Illinois, UrbanaChampaign, and Alexander Vardy at the University of California, San Diego, realized that the GuruswamiSudan algorithm could take advantage of information that all prior ReedSolomon decoders had simply thrown away.
"Decoding is always a matter of probability," Vardy said. "There had been a mismatch between the probabilistic domain of the channel and the algebraic domain of the decoder. In a sense, we had to achieve a happy marriage of probability and algebra."
Every data byte sent across a channel  whether that channel is a radio signal, harddisk readwrite signal, or whatever  is received as a set of probabilities for the possible bytes to have been heard over the background noise. Based on these probabilities, a typical ReedSolomon decoder immediately decides which byte it heard, discards the probabilistic information and listens for the next byte.
Koetter and Vardy extended the GuruswamiSudan algorithm to use these discarded probabilities and hit the jackpot. They created a ReedSolomon decoder that tolerates nearly twice the noise in the communication channel and still hears the correct message.
Just as critically, Koetter and Vardy found mathematical transformations that made the decoding algorithm 1,000 times faster and therefore practical for applications where speed is of the essence. In addition to compact disks, DVDs and hard drives, these applications include barcode readers, cellular telephones, communication satellites, digital televisions and DSL modems.
Several research groups are working to implement the new algorithm on a chip, and Koetter and Vardy have formed a company, CodeVector Technologies, to promote the new techniques. Companies in the disk drive, satellite communications and cell phone industries have all expressed interest.
With hard drives, tolerating more noise means engineers can record data bits more densely, which translates to smaller drives that hold more data. Satellites could hear and transmit less powerful signals. Similarly, ground stations could hear fainter signals from deep space probes  not to mention signals bouncing off the moon.
For Nobel laureate Taylor and other enthusiasts, the improved technique translates to successful moonbounce contacts with a radio signal nearly onethird less powerful.
"Dozens, perhaps hundreds, of EarthMoonEarth contacts are being made by amateurs with it every day now, all over the world," Taylor said. "The use of [the new] ReedSolomon decoder in this program has been a spectacular success."
 David Hart
Investigators
Madhu Sudan
Ralf Koetter
Kenneth Zeger
Richard Blahut
Alexander Vardy
Naresh Shanbhag
Venkatesan Guruswami
Related Institutions/Organizations
University of Washington
University of CaliforniaSan Diego
Massachusetts Institute of Technology
University of Illinois at UrbanaChampaign
Locations
California
Illinois
Massachusetts
Related Programs
Communications Research
Related Awards
#0073489 Source and Channel Coding for Multidimensional Channels
#0073490 HighPerformance Decoding of Algebraic Codes Beyond their Packing Radii
#9875511 CAREER: Optimization, Probabilistic Checking of Proofs and Errorcorrecting Codes
Total Grants
$1,215,000
Related Websites Taylor's moonbounce code: http://pulsar.princeton.edu/~joe/K1JT/
