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 …