Asymmetric numeral systems
By J. Duda. 2009
157 citations recorded by the source corpus.
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). This encryption uses the key to initialize random number generator, which is used to calculate the coding tables. Such preinitialized encryption has additional advantage: is resistant to brute force attack - to check a key we have to make whole initialization. There will be also presented application for new approach to error correction: after an error in each step we have chosen probability to observe that something was wrong. There will be also presented application for new approach to error correction: after an error in each step we have chosen probability to observe that something was wrong. We can get near Shannon's limit for any noise level this way with expected linear time of correction.
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Information Theory
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Yoshua Bengio
- Jun Zhu
- Sergey Levine
- Pieter Abbeel
- Ruslan Salakhutdinov
- Mohit Bansal
- Quoc V. Le
- Stefano Ermon
In Computational Theory and Mathematics
- F. Kingma
- Casper Kaae Sønderby
- Benjamin Bloem-Reddy
- James Townsend
- Jun Zhu
- David Barber
- Ben Poole
- Pieter Abbeel
In Information Theory
- David Barber
- Thomas Bird
- Ben Poole
- F. Kingma
- Casper Kaae Sønderby
- Benjamin Bloem-Reddy
- James Townsend
- Jun Zhu
Citations in the corpus
- Variational Diffusion Models (2021, methodology): “, 2018], an implementation of bits-back coding based on asymmetric numeral systems [Duda, 2009].”
- Fast Lossless Neural Compression with Integer-Only Discrete Flows (2022, methodology): “The speedup is lower than that for inference latency due to our suboptimal CPU implementation of rANS.”
- Lossy Compression for Lossless Prediction (2021, methodology): “This has the advantage that the learned qθ can be used for entropy coding Z [26, 27].”
- IDF++: Analyzing and Improving Integer Discrete Flows for Lossless Compression (2020, methodology): “[12, 13, 49] is used for lossless compression of the latent variables z = [ z (1) , . . . , z ( L ) ] by using the probability distribution p ( z ) = p ( z ( L ) ) p ( z ( L − 1) | y ( L − 1) ) . . . p ( z (1) | y (1) ) corresponding to the model’s multi-level structure.”
- Bit-Swap: Recursive Bits-Back Coding for Lossless Compression with Hierarchical Latent Variables (2019, methodology): “(Duda, 2009) Both schemes operate by encoding the data into single number (in its binary representation equivalent to a sequence of bits or bitstream) and decoding the other way around, where the single number serves as the message to be sent.”
- HiLLoC: Lossless Image Compression with Hierarchical Latent Variable Models (2019, methodology): “This implementation makes use of asymmetric numeral systems (ANS), a last-in-first-out (LIFO) entropy coding scheme (Duda, 2009).”
- Practical Lossless Compression with Latent Variables using Bits Back Coding (2019, background): “For a far more detailed introduction to arithmetic coding, see Witten et al. (1987), for asymmetric numeral systems, see Duda (2009).”
- Latent Variable Models (2019, methodology): “This implementation makes use of asymmetric numeral systems (ANS), a last-in-first-out (LIFO) entropy coding scheme (Duda, 2009).”