ON JULY 1st, a spacecraft called Cassini went into orbit around Saturn—the first probe to visit the planet since 1981. While the rockets that got it there are surely impressive, just as impressive, and much neglected, is the communications technology that will allow it to transmit its pictures millions of kilometres back to Earth with antennae that use little more power than a light-bulb.
To perform this transmission through the noisy vacuum of space, Cassini employs what are known as error-correcting codes. These contain internal tricks that allow the receiver to determine whether what has been received is accurate and, ideally, to reconstruct the correct version if it is not.
Such codes go back to 1948, the year when Claude Shannon, universally regarded as the father of coding theory, published a paper which showed the maximum theoretical rate at which information can be transmitted without error. But it is only recently that real codes have started to approach Shannon's theoretical limit. Those on Cassini, while powerful, still have some way to go, because the probe is limited to the technology available when it was built in the mid-1990s. But developments in coding theory made at the time Cassini was being assembled are now coming to fruition. As a result, as well as spacecraft, tomorrow's consumer-electronic devices, from mobile phones to high-definition televisions, will be able to receive and transmit data at something close to Shannon's limit.
Turbo coding, as the first of the new techniques to come on stream is known, was invented by Alain Glavieux and Claude Berrou, two researchers at the Ecole Nationale Supérieure des Télécommunications de Bretagne in Brest, France. It is now being deployed in third-generation (3G) mobile-telephone networks, and will allow wireless access from 3G phones to be over ten times faster than from an old-fashioned dial-up line.
Turbo coding takes one of the techniques deployed on Cassini—known as convolution coding—and doubles it. Convolutional codes work by adding some of the bits (the ones and zeros of binary arithmetic) from a block of data, and transmitting that sum alongside the raw data. The decoder then works backwards, to make sure the sums add up correctly. If they do not, it knows there has been a mistake and fiddles with the appropriate bits to try to correct the errors. Unfortunately, it does not always succeed.
What Dr Glavieux and Dr Berrou showed was that combining two convolutional codes would yield a dramatic improvement in performance—one that would go almost all the way to the Shannon limit. To do this, you have to shuffle the bits in each block of data at random. Each block is then broadcast twice—once unshuffled and once shuffled. One convolutional decoder works on the unshuffled data, and the other on the shuffled data. The shuffling means that an error which affects one block will not affect the other at the same place in the sequence.
If the two decoders disagree about a particular bit in the message because transmission noise has introduced errors, they consult one another by feeding their “opinions” about the error to each other, along with a measure of how confident each is about its opinion. Each decoder then uses the other's input to make a decision, and the process is repeated until they agree with each other.
This feedback loop has proved to be effective at making almost error-free transmissions, so long as each block of transmitted data is fairly long. This requirement for long blocks of data means that turbo codes are not very useful for applications that require almost no delays but transmit a fairly small number of bits—voice communications, for example. But they are ideal for data-rich applications such as wireless broadband.
Or almost ideal. For another coding technology is being touted to replace them before they have even been properly deployed. Low-density parity check (LDPC) codes are actually an old trick. They were invented by Robert Gallager, then a doctoral student at the Massachusetts Institute of Technology, in 1960. But, because the computers of the time were not powerful enough to take advantage of their benefits, these codes were largely forgotten until 1994—when three different groups of researchers rediscovered them.
LDPC codes also work on large blocks of data, but each batch is then encoded using a mathematical technique known as matrix algebra. This involves “multiplying” a block of bits by an array of different bits known as a matrix, and then transmitting the resulting bits.
The matrices used in LDPC coding are a type known as sparse matrices, in which almost all of the entries in the array are zero, rather than one. Because the few non-zero entries in a sparse array tend to be far apart, the process of matrix multiplication means that the resulting blocks of code end up looking different from one another, even if the starting data are similar. This, in turn, means that LDPC codes can tolerate large numbers of errors and still detect where the mistakes are. Furthermore, according to David MacKay of Cambridge University, who is one of the pioneers of the new generation of LDPC codes, after a few mathematical tweaks dreamt up in the late 1990s, these codes now outperform turbo codes, and are computationally simpler to implement.
This, according to Dr MacKay, is why they have been adopted in the next-generation standard for satellite television, which is being hammered out by the regulators at the European Telecommunications Standards Institute over the next few months. They are also being incorporated into standards for so-called 4G mobile telephones, which will, if all goes well, be introduced around 2010. These phones would be able to handle as many as a billion bits a second. At that rate it would only take a few seconds to download an entire movie. Perhaps the next probe to go to Saturn will send back live video to the world's mobile phones.
|Copyright © 2004 The Economist Newspaper and The
Economist Group. All rights reserved.|