The blind codemaker: a boon to communications

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 fibre 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 US 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 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.