TitleLength-Limited Variable-to-Variable Length Codes for High-Performance Entropy Coding (In Proceedings)
inProceedings, 2004 Data Compression Conference
Author(s) Joshua Senecal, Mark A. Duchaineau, Ken Joy
Keyword(s)Data Compression, bin coding, variable to variable length codes
Year March 2004
LocationSnowbird, UT
DateMarch 23--25, 2004
PublisherIEEE Computer Society
Abstract Arithmetic coding achieves a superior coding rate when encoding a binary source, but its lack of speed makes it an inferior choice when true high–performance encoding is needed. We present our work on a practical implementation of fast entropy coders for binary messages utilizing only bit shifts and table lookups. To limit code table size we limit our code lengths with a type of variable–to–variable (VV) length code created from source string merging. We refer to these codes as “merged codes”. With merged codes it is possible to achieve a desired level of speed by adjusting the number of bits read from the source at each step. The most efficient merged codes yield a coder with a worst–case inefficiency of 0.4%, relative to the Shannon entropy. Using a hybrid Golomb–VV Bin Coder we are able to achieve a compression ratio that is competitive with other state–of–the–art coders, at a superior throughput.