Computer Science – Information Theory
Scientific paper
2005-11-15
IEEE/DCC 2006, p. 468
Computer Science
Information Theory
Submitted to DCC-2006
Scientific paper
Quantized Indexing is a fast and space-efficient form of enumerative (combinatorial) coding, the strongest among asymptotically optimal universal entropy coding algorithms. The present advance in enumerative coding is similar to that made by arithmetic coding with respect to its unlimited precision predecessor, Elias coding. The arithmetic precision, execution time, table sizes and coding delay are all reduced by a factor O(n) at a redundancy below 2*log(e)/2^g bits/symbol (for n input symbols and g-bit QI precision). Due to its tighter enumeration, QI output redundancy is below that of arithmetic coding (which can be derived as a lower accuracy approximation of QI). The relative compression gain vanishes in large n and in high entropy limits and increases for shorter outputs and for less predictable data. QI is significantly faster than the fastest arithmetic coders, from factor 6 in high entropy limit to over 100 in low entropy limit (`typically' 10-20 times faster). These speedups are result of using only 3 adds, 1 shift and 2 array lookups (all in 32 bit precision) per less probable symbol and no coding operations for the most probable symbol . Further, the exact enumeration algorithm is sharpened and its lattice walks formulation is generalized. A new numeric type with a broader applicability, sliding window integer, is introduced.
No associations
LandOfFree
Quantized Indexing: Beyond Arithmetic Coding does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Quantized Indexing: Beyond Arithmetic Coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantized Indexing: Beyond Arithmetic Coding will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-7482