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

Lloyd Allison, Arun S. Konagurthu and Daniel F. SchmidtData Compression Conference (DCC), pp.313322, 2226 March 2021Abstract: 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^{*} (omegastar) 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 1697bit codeword mark. Encoding and decoding routines for the codes described here are implemented and available for interactive use^{1}. Download at the IEEE [doi:10.1109/DCC50243.2021.00039], or here [paper.pdf]. [1] ← click. 

↑ © L. Allison, www.allisons.org/ll/ (or as otherwise indicated). Created with "vi (Linux)", charset=iso88591, fetched Tuesday, 21Sep2021 22:09:01 EDT. Free: Linux, Ubuntu operatingsys, OpenOffice officesuite, The GIMP ~photoshop, Firefox webbrowser, FlashBlock flash on/off. 