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

HP.com home

Technical Reports


HP Labs

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

Click here for full text: PDF

On the Reduction of Entropy Coding Complexity via Symbol Grouping: I - Redundancy Analysis and Optimal Alphabet Partition

Said, Amir


Keyword(s): data compression; symbol grouping; dynamic programming; Monge matrices

Abstract: We analyze the technique for reducing the complexity of entropy coding that consists in the a priori grouping of the source alphabet symbols, and in the decomposition of the coding process in two stages: first coding the number of the symbol's group with a more complex method, followed by coding the symbol's rank inside its group using a less complex method, or simply using its binary representation. This technique proved to be quite effective, yielding great reductions in complexity with reasonably small losses in compression, even when the groups are designed with empiric methods. It is widely used in practice and it is an important part in standards like MPEG and JPEG. However, the theory to explain its effectiveness and optimization had not been sufficiently developed. In this work, we provide a theoretical analysis of the properties of these methods in general circumstances. Next, we study the problem of finding optimal source alphabet partitions. We demonstrate a necessary optimality condition that eliminates most of the possible solutions, and guarantees that a more constrained version of the problem, which can be solved via dynamic programming, provides the optimal solutions. In addition, we show that the data used by the dynamic programming optimization has properties similar to the Monge matrices, allowing the use of much more efficient solution methods.

42 Pages

Back to Index

»Technical Reports

» 2009
» 2008
» 2007
» 2006
» 2005
» 2004
» 2003
» 2002
» 2001
» 2000
» 1990 - 1999

Heritage Technical Reports

» Compaq & DEC Technical Reports
» Tandem Technical Reports
Printable version
Privacy statement Using this site means you accept its terms Feedback to HP Labs
© 2009 Hewlett-Packard Development Company, L.P.