You're about to play your favorite DVD movie or music CD when you stop to examine its shiny encoded surface and, to your surprise, find a deep scratch -- yet when you insert the disc, it plays perfectly.
Error-correction algorithms may not be the first thing you think about while enjoying your still-flawless tunes or movie. But it is these algorithms -- pioneered by information theory researchers -- that make it possible for DVD/CD players to reconstruct how a disc would look and sound without a scratch that may have obliterated millions of bits of data.
"Information theory is a lot more than theory. It has practical applications," says Gadiel Seroussi, director of information theory research at HP Labs. "Cell phones, tape drives, DVDs, even the Internet -- none of these would work without technologies derived from information theory."
Information theory in everyday life
Three key areas of information theory research -- data compression, coding for error correction and cryptography -- touch many aspects of our everyday lives.
Data compression, one of the enablers of the digital multimedia revolution, allows information to be encoded efficiently so that fewer bits need to be transmitted or stored. It has a crucial role in compressing music, video and images in multimedia production and editing and in sending and receiving compressed multimedia files over the Internet.
Coding for error correction makes it possible to send bits over "noisy channels" -- radio waves, wires, CDs and DVDs -- without losing data by adding patterns of redundancy to the transmission. A noisy channel is one with static, dust or some other interference (electrical or mechanical, like a scratch on a CD) that can potentially corrupt data. By mathematically manipulating available information to reconstruct corrupted bits, error correction coding can mask these transmission defects.
At HP, the work of information theory researchers has touched everything from computer memories to tape drives. Their work shows up in printers, cameras, scanners, network routers and lots more.
"At HP Labs, we attack problems that impact HP businesses," says Seroussi, who was named a Fellow of the IEEE in 1998 for his theoretical and practical work in error correction and data compression.
Among other things, researchers played a key role in creating compression standards that allow people to manipulate, store and transmit images efficiently .
developing compression standards
One of these standards JPEG-LS, is based on HP Labs' Low Complexity Loss-less Compression for Images (LOCO-I) algorithm, which achieves state-of-the-art lossless compression performance at a fraction of the complexity of other algorithms in the same performance class. "Lossless" means that no bits are altered in the compression/decompression cycle. This is particularly critical in fields that require exacting detail, such as medical imaging and space exploration.
LOCO-I springs from research into statistical models in image compression and optimal codes for these models.
HP Labs researchers also made key contributions to the JPEG 2000 standard, which is set to replace the current JPEG standard. The new standard orders information so that when images are decompressed, the best possible reconstruction is produced, even when downloads aren't fully completed and parts of the compressed stream are missing.
The team also uses information theory to develop and analyze prediction (or sequential decision) algorithms, with the goal of making optimal decisions in advance of events, based on observed data.
They applied this work to guessing memory access patterns in computer memories. Predicting these can be useful in creating computer architectures.
"If you can guess what a program will need and prepare it beforehand, everything runs faster," Seroussi says.
the theory in information theory
But information theorists' contributions to practical applications can't happen without their academic work. Researchers routinely publish papers that support the discipline of information theory, helping to build a healthy exchange of ideas and knowledge among the community of researchers and academics at public, private and corporate research institutions in the United States and around the world.
"Some people don't know what to think of information theorists," says Seroussi. "Some believe we're too practical to be basic researchers and others believe we're too theoretical to be applied researchers. To us, that means we're operating at exactly the right point. The reality is that we publish theoretical research, but our work gets used in practice.
"Helping HP and doing scientific research are complementary," he adds. "They feed off each other."
cycle of discovery
Working with engineers and studying their problems often yields interesting mathematical problems that remain interesting and challenging, even after work on the practical application is done. The new theoretical insights, in turn, are often helpful in future practical applications.
In the area of elliptic curve cryptography, for example, Seroussi co-authored a book with former HP Labs colleagues Nigel Smart and Ian Blake that helped bridge the gap between mathematicians and engineers in their understanding of this discipline. As a result, more people were able to use elliptic curve cryptography, a form of public-key cryptography that provides security with less complexity than other methods.
"For HP, kind of cryptography is useful for providing strong security for small, handheld devices with little computational power," he says. "For us researchers, the mathematics involved are deep, beautiful and intellectually stimulating. It's a perfect match of practicality and passion."
by Sanjay Khanna
for more information