From Moonbounce to Hard Drives: Correcting More Errors Than Previously Thought Possible

 

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 long-distance 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 NSF-supported 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 error-correcting 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 so-called Reed-Solomon codes in practice.

Such error-correcting 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 black-and-white -- a bit is either 0 or 1, after all -- but real-world devices are always less than perfect. Error-correcting 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 Reed-Solomon codes could correct. If a message had more errors than this limit, the information was lost.

Then, the first pair of NSF-supported scientists showed that the well-known limit was wrong. In the mid-1990s, MIT computer scientist Madhu Sudan surprised everyone by showing that Reed-Solomon codes could correct more errors than previously thought possible. Later work with his then-doctoral student Venkatesan Guruswami, now at the University of Washington, raised the limit even further.

"After more than 30 years of work on Reed-Solomon 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 Reed-Solomon error-correction limit had persisted, in part, because of a worst-case 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 real-world randomness that leads to the need for error-correcting codes in the first place also means that the worst-case scenario would rarely, if ever, occur in the real-world. "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 Guruswami-Sudan method would let you keep your CD and DVD collections and, in fact, any data recorded with Reed-Solomon codes. Only the players have to change.

However, correcting "slightly more" errors is not reason enough to re-engineer the world's hard drives. Besides, current Reed-Solomon decoders work in hundredths or millionths of a second, whereas the Guruswami-Sudan method would take minutes or hours.

That's where the second pair of NSF-supported scientists come in. Ralf Koetter of the University of Illinois, Urbana-Champaign, and Alexander Vardy at the University of California, San Diego, realized that the Guruswami-Sudan algorithm could take advantage of information that all prior Reed-Solomon 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, hard-disk read-write 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 Reed-Solomon decoder immediately decides which byte it heard, discards the probabilistic information and listens for the next byte.

Koetter and Vardy extended the Guruswami-Sudan algorithm to use these discarded probabilities and hit the jackpot. They created a Reed-Solomon 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 one-third less powerful.

"Dozens, perhaps hundreds, of Earth-Moon-Earth contacts are being made by amateurs with it every day now, all over the world," Taylor said. "The use of [the new] Reed-Solomon decoder in this program has been a spectacular success."

-- David Hart