Gregory Wornell - The blind codemaker
New error-correcting codes guarantee the fastest possible rate of data transmission, even over fluctuating wireless links.
Larry Hardesty, MIT News Office
February 10, 2012
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
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.
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
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.
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 code. “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 wirelesscommunication
applications and standards for connecting mobile devices.”