Jump to content United States-English
HP.com Home Products and Services Support and Drivers Solutions How to Buy
» Contact HP

hp.com home

From Theory to Practice

Using Information Theory to Design the Digital Future

May 2002

printable version

HP Labs

» Research
» News and events
» Technical reports
» About HP Labs
» Careers @ HP Labs
» Worldwide sites
» Downloads
Content starts here

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.

This is a controller for a color printer. Each chip contains a compressor/decompressor based on an algorithm created by HP Labs

Cryptography secures communications and protects them from prying eyes. It also enables digital signatures, identification and authentication in electronic transactions.

product impact

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 .

Quote: 'Cell phones, tape drives, DVDs, even the Internet -- None of these would work without technologies derived from information theory

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.

predicting events

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

Related links

» Information Theory Research
» The LOCO-I Lossless Compression Algorithm (Technical Paper)
» Elliptic Curves in Cryptography
Photo of Gadiel Seroussi
Privacy statement Using this site means you accept its terms Feedback to HP Labs
© 2009 Hewlett-Packard Development Company, L.P.