On universal codes for integers: Wallace Tree, elias omega and beyond

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

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.11The codes may be tried at www.allisons.org/ll/MML/Discrete/Universal/\leftarrow click.

Original languageEnglish
Title of host publicationProceedings - DCC 2021, 2021 Data Compression Conference
EditorsAli Bilgin, Michael W. Marcellin, Joan Serra-Sagrista, James A. Storer
Place of PublicationPiscataway NJ USA
PublisherIEEE, Institute of Electrical and Electronics Engineers
Pages313-322
Number of pages10
ISBN (Electronic)9780738112275, 9781665403337
ISBN (Print)9781665447850
DOIs
Publication statusPublished - 2021
EventData Compression Conference 2021 - Online, Snowbird, United States of America
Duration: 23 Mar 202126 Mar 2021
https://ieeexplore.ieee.org/xpl/conhome/9418628/proceeding (Proceedings)
https://signalprocessingsociety.org/blog/dcc-2021-2021-data-compression-conference (Website)

Publication series

NameData Compression Conference Proceedings
PublisherThe Institute of Electrical and Electronics Engineers, Inc.
Volume2021-March
ISSN (Print)1068-0314
ISSN (Electronic)2375-0359

Conference

ConferenceData Compression Conference 2021
Abbreviated titleDCC 2021
CountryUnited States of America
CitySnowbird
Period23/03/2126/03/21
Internet address

Keywords

  • compression
  • integers
  • omega
  • universal code

Cite this