Fetching the paper…

Reading the bibliography…

2009

Asymmetric numeral systems

Duda, Jarek

Original
PDF
Post on X

Understand

In this paper will be presented new approach to entropy coding: family of generalizations of standard numeral systems which are optimal for encoding sequence of equiprobable symbols, into asymmetric numeral systems - optimal for freely chosen probability distributions of symbols.

It has some similarities to Range Coding but instead of encoding symbol in choosing a range, we spread these ranges uniformly over the whole interval.
This leads to simpler encoder - instead of using two states to define range, we need only one.
This approach is very universal - we can obtain from extremely precise encoding (ABS) to extremely fast with possibility to additionally encrypt the data (ANS).

Asymmetric numeral systems · Around

Built on

D.A. Huffman, A Method for the Construction of Minimum-Redundancy Codes , Proceedings of the I.R.E., September 1952, pp 1098-1102
1952
Earlier work this paper cites.
Gallager, R. G., Low Density Parity Check Codes, Monograph , M.I.T. Press, 1963,
1963
Earlier work this paper cites.

Similar

J.J. Rissanen, Generalized Kraft inequality and arithmetic coding , IBM J. Res. Develop., vol. 20, no. 3, pp. 198-203, May 1976
1976
Cited alongside, same era.
G.N.N. Martin, Range encoding: an algorithm for removing redundancy from a digitized message , Video and Data Recording Conf., Southampton, England, July 1979. vol. 2, pp 179-194, July 1992
1992
Cited alongside, same era.
J. Duda, Optimal encoding on discrete lattice with translational invariant constrains using statistical algorithms , arxiv:0710.3861
Original
Cited in the paper.
M. Mahoney, Data Compression Programs web site, http://cs.fit.edu/ mmahoney/compression/
Cited in the paper.
J. Duda, Data Compression Using Asymmetric Numeral Systems, Wolfram Demonstration Project, http://demonstrations.wolfram.com/author.html?author=Jarek+Duda
Cited in the paper.
M. Matsumoto, Y. Kurita, Twisted GFSR generators , ACM Transactions on Modeling and Computer Simulation,
Cited in the paper.

Then

D. MacKay, Information Theory, Inference, and Learning Algorithms , Cambridge University Press (2003)
2003
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…