Punctured Elias Codes for Variable-Length Coding of the Integers
Peter M. Fenwick · 1996
The compact representation of integers is an important problem in areas such as data compression, especially where there is a nearly monotonic decrease in the likelihood of larger integers. While many different representations have been described, it is not always clear in which circumstances a particular code is to be preferred. This report introduces a variant of the Elias γ code which is shown to be better than other codes for some distributions. 1. Compact integer representations The efficient representation of symbols of differing probabilities is one of the classical problems of information theory and coding theory, with efficient solutions known since the early 1950’s (Shannon-Fano and Huffman codes[9]). In traditional, non-adaptive, coding we assume a priori probabilities of the input symbols and construct suitable codes to represent those symbols efficiently. There is no necessary or simple relation between a symbol and its representation. Here we are concerned with a different problem, especially as the symbol alphabet (integers of arbitrary upper bound) may be so large as to preclude the formal construction of an efficient code. Given an arbitrary integer we wish to represent it as compactly as possibly, preferably by an algorithm which recognises only the magnitude and bit pattern of the integer (no table lookup or mapping needed). Equally, a simple algorithm should be able to recover an integer from an input bit stream, even if that particular integer has never been seen before. The binary representation of the integer is often visible within the representation and other information is appended to indicate the length or precision. Many variable-length representations have been described; here we concentrate on just a few, emphasising those which have a simple relation between code and value and are instantaneous or nearly so. Following Elias[3], we first introduce two preliminary representations which are relatively unimportant per se, but are used in many other codes. • α(n) is the unary representation, n 0’s followed by a 1 (or 1’s followed by a 0) • β(n), is the natural binary representation of n, from the most significant 1.