Pushing the Limit: Digital-Communications Experts Are Zeroing in on the Perfect Code

Article excerpt

When SMART-1, the European Space Agency's first mission to the moon, launched in September 2003, astronomers hailed it as the testing ground for a revolutionary and efficient solar-electric-propulsion technology. While this technological leap absorbed the attention of scientists and the news media, a second, quieter revolution aboard SMART-1 went almost unheralded. Only a small band of mathematicians and engineers appreciated the quantum leap forward for digital communications. Incorporated into SMART-1's computers was a system for encoding data transmissions that, in a precise mathematical sense, is practically perfect.

Space engineers have long grappled with the problem of how to reliably transmit data, such as pictures and scientific measurements, from space probes back to Earth. How can messages travel hundreds of millions of miles without the data becoming hopelessly garbled by noise? In a less extreme situation, as any cell phone user can attest, noise is also an issue for communication systems on Earth.

Over the past half-century, mathematicians and computer scientists have come up with clever approaches to the noise problem. They've devised codes that intentionally incorporate redundancy into a message, so that even if noise corrupts some portions, the recipient can usually figure it out. Called error-correcting codes, these underlie a host of systems for digital communication and data storage, including cell phones, the Internet, and compact disks. Space missions use this technique to send messages from transmitters that are often no more powerful than a dim light bulb.

Yet coding theorists have been aware that their codes fall far short of what can, in theory, be achieved. In 1948, mathematician Claude Shannon, then at Bell Telephone Laboratories in Murray Hill, N.J., published a landmark paper in which he set a specific goal for coding theorists. Shannon showed that at any given noise level, there is an upper limit on the ratio of the information to the redundancy required for accurate transmission. As with the speed of light in physics, this limit is unattainable, but--in theory at least--highly efficient codes can come arbitrarily close.

The trouble was that no one could figure out how to construct the superefficient codes that Shannon's theory had predicted. By the early 1990s, state-of-the-art codes were typically getting information across at only about half the rate that Shannon's law said was possible.

Then, in the mid-1990s, an earthquake shook the coding-theory landscape. A pair of French engineers--outsiders to the world of coding theory--astonished the insiders with their invention of what they called turbo codes, which come within a hair's breadth of Shannon's limit.

Later in the decade, coding theorists realized that a long-forgotten method called low-density parity-check (LDPC) coding could edge even closer to the limit.

Turbo codes and LDPC codes are now coming into play. In addition to being aboard the SMART-1 mission, turbo-code technology is on its way to Mercury on NASA's Messenger mission, launched last year. In the past couple of years, turbo codes have also found their way into millions of mobile phones, enabling users to send audio and video clips and to surf the Internet.

LDPC codes, meanwhile, have become the new standard for digital-satellite television. Hundreds of research groups are studying potential applications of the two kinds of codes at universities and industry giants including Sony, Motorola, Qualcomm, and Samsung.

"In the lab, we're there" at the Shannon limit, says Robert McEliece, a coding theorist at the California Institute of Technology in Pasadena. "Slowly, the word is getting out, and the technology is being perfected."

The closing of the gap between state-of-the-art codes and the Shannon limit could save space agencies tens of millions of dollars on every mission because they could use lighter data transmitters with smaller batteries and antennas. …