## 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^{1}.

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

`[1]`
← click.