A new recursive universal code of the positive integers
Hirosuke Yamamoto
IEEE Trans. on Information Theory, vol.46, no.2, pp.717-723, March 2000
- A new recursive universal code of the positive integers is proposed, in which any given sequence can be used as a delimiter of codeword while bit "0'' is used as a delimiter in known universal codes, e.g. Levenshtein code, Elias $\Omega$ code, Even-Rodeh code, Stout code, Bentley-Yao code, etc. The codeword length of the proposed code is shorter than $\log^{*}_{2}n$ in almost all of sufficiently large positive integers although the known codes are longer than $\log_{2}^{*}n$ for any positive integer $n$.
- Index Terms: Elias $\Omega$ code, log-star function, universal code of positive integers, universal coding
- The above scheme is explained in Section 2.13 "Yamamoto's Recursive Code" of the following book:
- David Salomon, "Variable-length Codes for Data Compression", Springer-Verlag, 2007. (ISBN 978-1-84628-958-3)
- DOI: 10.1109/18.825850