On universal codes for integers: Wallace Tree, Elias Omega and beyond

Lloyd Allison, Arun S. Konagurthu and Daniel F. Schmidt

Data Compression Conference (DCC), pp.313-322, 22-26 March 2021

Abstract: A universal code for the (positive) integers is a variable length code that can be used to store or compress a sequence of integers. It also implies a probability distribution on integers which can be a natural choice when the true distribution of a source of integers is unknown; such a code and distribution may be useful in statistical inference. This paper provides two improvements to the theory and practice of universal codes. First, it defines and examines a new universal code omega^* (omega-star) that asymptotically beats the Elias omega code. Second, it analyses the properties of a code proposed by Wallace based on trees, and shows it to be a universal code, to have desirable properties for use in inference, and to beat the Elias omega code on almost all integers up to the 1697-bit code-word mark. Encoding and decoding routines for the codes described here are implemented and available for interactive use¹.

Download at the IEEE [doi:10.1109/DCC50243.2021.00039], or here [paper.pdf].

[1] ← click.