New error-correcting codes guarantee the fastest possible rate of data transmission

Feb 10, 2012
Graphic: Christine Daniloff

Error-correcting codes are one of the triumphs of the digital age. They’re a way of encoding information so that it can be transmitted across a communication channel — such as an optical fiber or a wireless connection — with perfect fidelity, even in the presence of the corrupting influences known as “noise.”

An encoded message is called a codeword; the noisier the channel, the longer the codeword has to be to ensure perfect communication. But the longer the codeword, the longer it takes to transmit the message. So the ideal of maximally efficient, perfectly faithful communication requires precisely matching codeword length to the level of noise in the channel.

Wireless devices, such as cellphones or Wi-Fi transmitters, regularly send out test messages to gauge noise levels, so they can adjust their codes accordingly. But as anyone who’s used a cellphone knows, reception quality can vary at locations just a few feet apart — or even at a single location. Noise measurements can rapidly become outdated, and wireless devices routinely end up using codewords that are too long, squandering bandwidth, or too short, making accurate decoding impossible.

In the next issue of the journal IEEE Transactions on Information Theory, Gregory Wornell, a professor in the Department of Electrical Engineering and Computer Science at MIT, Uri Erez at Tel Aviv University in Israel and Mitchell Trott at Google describe a new coding scheme that guarantees the fastest possible delivery of data over fluctuating wireless connections without requiring prior knowledge of noise levels. The researchers also received a U.S. patent for the technique in September.

Say ‘when’

The scheme works by creating one long codeword for each message, but successively longer chunks of the codeword are themselves good codewords. “The transmission strategy is that we send the first part of the codeword,” Wornell explains. “If it doesn’t succeed, we send the second part, and so on. We don’t repeat transmissions: We always send the next part rather than resending the same part again. Because when you marry the first part, which was too noisy to decode, with the second and any subsequent parts, they together constitute a new, good encoding of the message for a higher level of noise.”

Say, for instance, that the long codeword — call it the master codeword — consists of 30,000 symbols. The first 10,000 symbols might be the ideal encoding if there’s a minimum level of noise in the channel. But if there’s more noise, the receiver might need the next 5,000 symbols as well, or the next 7,374. If there’s a lot of noise, the receiver might require almost all of the 30,000 symbols. But once it has received enough symbols to decode the underlying message, it signals the sender to stop. In the paper, the researchers prove mathematically that at that point, the length of the received codeword is the shortest possible length given the channel’s noise properties — even if they’ve been fluctuating.

To produce their master codeword, the researchers first split the message to be sent into several — for example, three — fragments of equal length. They encode each of those fragments using existing error-correcting codes, such as Gallager codes, a very efficient class of codes common in wireless communication. Then they multiply each of the resulting codewords by a different number and add the results together. That produces the first chunk of the master codeword. Then they multiply the codewords by a different set of numbers and add those results, producing the second chunk of the master codeword, and so on.

Tailor-made

In order to decode a message, the receiver needs to know the numbers by which the codewords were multiplied. Those numbers — along with the number of fragments into which the initial message is divided and the size of the chunks of the master codeword — depend on the expected variability of the communications channel. Wornell surmises, however, that a few standard configurations will suffice for most wireless applications.

The only chunk of the master codeword that must be transmitted in its entirety is the first. Thereafter, the receiver could complete the decoding with only partial chunks. So the size of the initial chunk is calibrated to the highest possible channel quality that can be expected for a particular application.

Finally, the complexity of the decoding process depends on the number of fragments into which the initial message is divided. If that number is three, which Wornell considers a good bet for most wireless links, the decoder has to decode three messages instead of one for every chunk it receives, so it will perform three times as many computations as it would with a conventional . “In the world of digital communication, however,” Wornell says, “a fixed factor of three is not a big deal, given Moore’s Law on the growth of computation power.”

H. Vincent Poor, the Michael Henry Strater University Professor of Electrical Engineering and dean of the School of Engineering and Applied Science at Princeton University, sees few obstacles to the commercial deployment of a coding scheme such as the one developed by Wornell and his colleagues. “The codes are inherently practical,” Poor says. “In fact, the paper not only develops the theory and analysis of such codes but also provides specific examples of practical constructions.”

Because the codes “enable efficient communication over unpredictable channels,” he adds, “they have an important role to play in future wireless-communication applications and standards for connecting mobile devices.”

Explore further: Google DeepMind acquisition researchers working on a Neural Turing Machine

Related Stories

Perfect communication with imperfect chips

Aug 05, 2011

One of the triumphs of the information age is the idea of error-correcting codes, which ensure that data carried by electromagnetic signals — traveling through the air, or through cables or optical fibers ...

Researcher finds optimal fix-free codes

Apr 03, 2009

(PhysOrg.com) -- More than 50 years after David Huffman developed Huffman coding, an entropy encoding algorithm used for lossless data compression in computer science and information theory, an electrical ...

Explained: The Shannon limit

Jan 19, 2010

It's the early 1980s, and you’re an equipment manufacturer for the fledgling personal-computer market. For years, modems that send data over the telephone lines have been stuck at a maximum rate of 9.6 kilobits ...

Entanglement can help in classical communication

Mar 30, 2011

(PhysOrg.com) -- When most of us think of entanglement, our minds jump immediately to quantum communication. "Entanglement has become very well known and useful in quantum communication," Robert Prevedel tells PhysOrg.com. Preved ...

Simple security for wireless: no password required

Aug 22, 2011

In early August, at the Def Con conference — a major annual gathering of computer hackers — someone apparently hacked into many of the attendees’ cell phones, in what may have been the first successful breach ...

Explained: Gallager codes

Jan 21, 2010

In the 1948 paper that created the field of information theory, MIT grad (and future professor) Claude Shannon threw down the gauntlet to future generations of researchers. In those predigital days, communications ...

Recommended for you

Saving lots of computing capacity with a new algorithm

Oct 29, 2014

The control of modern infrastructure such as intelligent power grids needs lots of computing capacity. Scientists of the Interdisciplinary Centre for Security, Reliability and Trust (SnT) at the University of Luxembourg have ...

User comments : 9

Adjust slider to filter visible comments by rank

Display comments: newest first

baudrunner
1 / 5 (8) Feb 10, 2012
This introduces result averaging and prediction of missing chunks of data and that can get to be freaky science. When applied, it can also impact on the quality of the information that we receive.
antialias_physorg
5 / 5 (2) Feb 10, 2012
When applied, it can also impact on the quality of the information that we receive

Er. Whut?

This has nothing to do with the content of the information transmitted. Only with the needed error correction.

A drawback of this system is that if the variation in noise level is high and the distribution of noise levels is not normal then this might render lower transmission speeds.

This could happen if the noise types are inconsistent (i.e. if your line as intermittent bit-errors and at other times block-errors).

Sanescience
1 / 5 (5) Feb 10, 2012
I find it interesting that "quality" is used in such a manner, because before the digital representation of the voice is handed to the ECC layer, it has already been compressed to a tiny fraction of it's original content throwing out most of its "quality" to begin with.

I have to add, that it won't be long now till phones use voice recognition to translate speech to words, then will just send the text and on the other side, will "read" them back to you sounding like your GPS navigator.
Parsec
5 / 5 (1) Feb 10, 2012
I find it interesting that "quality" is used in such a manner, because before the digital representation of the voice is handed to the ECC layer, it has already been compressed to a tiny fraction of it's original content throwing out most of its "quality" to begin with.

I have to add, that it won't be long now till phones use voice recognition to translate speech to words, then will just send the text and on the other side, will "read" them back to you sounding like your GPS navigator.

Actually, Its quite possible to send not only the speech as text, but enough phonemic 'hints' to be able to reconstruct the voice as it was expressed. At the end of the day however, whatever you do to compress the message, its still just data. It needs to be transmitted. Advances of the sort outlined in this paper will always be useful, no matter what kind of data is transmitted.
axemaster
2 / 5 (2) Feb 10, 2012
This is clever. It will be nice to reduce the overhead and wasted bandwidth/energy used by today's servers. Perhaps this could be used on optical disks as well, to make them scratch resistant and possibly have faster read speeds?
Urgelt
1 / 5 (1) Feb 10, 2012
Um. It sounds like they're using the principle underlying PAR2.

I wouldn't grant a patent on this without a careful review of priors.
meBigGuy
2.3 / 5 (3) Feb 11, 2012
Um, sounds like you don't understand PAR2 nor the proposed scheme. PAR2 uses simple reed solomon block coding.
baudrunner
1 / 5 (3) Feb 12, 2012
The whole concept is about reconstructing a facsimile that can almost not be distinguished from the original. It just gets worse from there.
Graeme
not rated yet Feb 13, 2012
This proposal does neeed a two way channel and applications that can tolerate variable delay. For broadcast video you cannot use it, due to no back channel, but a long delay code would be acceptable. For telephone a variable decoding delay would force introduction of silence, which is not very pleasant!
This system would be best for batch data.

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.