Title :
Worst-case Analysis of the Low-complexity Symbol Grouping Coding Technique
Author_Institution :
Hewlett Packard Lab., Palo Alto, CA
Abstract :
The symbol grouping technique is widely used in practice because it allows great reductions on the complexity of entropy coding symbols from large alphabets, at the expense of small losses in compression. While it has been used mostly in an ad hoc manner, it is not known how general this technique is, i.e., in exactly what type of data sources it can be effective. We try to answer this question by searching for worst-case data sources, measuring the performance, and trying to identify trends. We show that finding the worst-case source is a very challenging optimization problem, and propose some solution methods that can be used in alphabets of moderate size. The numerical results provide evidence confirming the hypotheses that all data sources with large number of symbols can be more efficiently coded, with very small loss, using symbol grouping
Keywords :
entropy codes; group codes; optimisation; entropy coding symbols; large alphabets; low-complexity symbol grouping coding technique; optimization problem; solution methods; worst-case data sources; Arithmetic; Clocks; Costs; Entropy coding; Laboratories; MPEG standards; Optimization methods; Probability distribution; Throughput; Transform coding;
Conference_Titel :
Information Theory, 2006 IEEE International Symposium on
Conference_Location :
Seattle, WA
Print_ISBN :
1-4244-0505-X
Electronic_ISBN :
1-4244-0504-1
DOI :
10.1109/ISIT.2006.262028