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 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 wireless-communication applications and standards for connecting mobile devices.”
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 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 wireless-communication applications and standards for connecting mobile devices.”
