Information theory

Research opportunities

Every time you open a JPEG image, watch a DVD, talk on a mobile phone or receive an encrypted message, you're reaping the benefits of information theory. Although the field is mathematical in nature, three key areas of information theory research -- data compression, coding for error correction and cryptography -- touch many aspects of our everyday lives.

Information theory provides a conceptual framework for HP core technologies in imaging, storage, computing, communications and even services. Beyond its original focus on communication problems, it is also instrumental to other areas of engineering and science.

Although information theory is a fairly mature discipline (founded in 1948 by Claude Shannon's seminal work), new applications and data types create an influx of problems that require sophisticated solutions for innovation and technology differentiation. With a unique blend of engineering and mathematics, information theory provides a rigorous approach to problem-solving that adds depth to proposed solutions.

Research focus

Current work

Some of our current activities are:

• context-based data and image compression algorithms, with application to printers and other imaging devices
• context-based denoising, with emphasis on image denoising
• compression in large storage systems with redundancies across files
• simulation of random processes
• 2D inter-symbol interference and 2D constrained coding
• low-density parity check codes under linear programming decoding
• error-correcting codes for nano-scale crossbar memory demultiplexers and self-assembly
• error-correcting codes for memory controllers
• study of the capacity region of the interference channel
• distribution of audio and video signals over networks with packet losses and unreliable links

Technical contributions

We have made key contributions in compression, universal statistical modeling, error correction and cryptography.

Compression

HP Labs' information theorists have been leaders in designing practical data compression algorithms and developing the associated theory.

The team invented the algorithm at the core of the JPEG-LS standard for lossless image compression, which is used in a wide variety of applications -- including lossless image compression by the Mars Expedition Rovers. In addition, the group produced key contributions to the wavelet-based JPEG 2000 standard for lossy-image compression.

On the theoretical front, our researchers have been active in solving open problems pertaining to bounds on universal modeling performance (i.e., modeling data in the absence of any a priori statistical characterization) in various settings.

The team has transferred proprietary compression technology for use in remote workstations, printers, scanners, all-in-ones, network routers and other products.

Universal statistical modeling

HP Labs' contributions to universal statistical modeling have influenced not only data compression, but other aspects of information theory and computation. The group made pioneering contributions to adaptive prefetching, universal simulation and discrete denoising -- including inventing DUDE, the first universal discrete denoising algorithm.

DUDE has linear complexity and performs as well as the optimum denoiser that knows the clean data distribution. This contribution was awarded the 2006 Communications Society and Information Theory joint paper award.

Error correction

The group developed error-correction technology for very high-density storage devices, such as MRAM or PIRM memories. As storage densities increase, so does the density of defects, so defect tolerance is needed to keep manufacturing costs in check.

The group also developed error-correction technology for various memory controllers for server architectures, magnetic tape storage and optical media, as well as constrained coding technologies for DVD standards.

In a novel error-correction application, the group contributed to HP's strong patent portfolio in defect tolerance for nano-electronic circuits.

Cryptography

HP researchers made significant contributions to elliptic-curve cryptography, a less complex alternative to conventional public key primitives based on factorization or finite field logarithms.

The technology was used in low-power, computationally constrained devices (portable appliances). Other contributions include security for sentient spaces and information embedding.

Related research