The Compression Optimality of Asymmetric Numeral Systems

Source coding has a rich and long history. However, a recent explosion of multimedia Internet applications (such as teleconferencing and video streaming, for instance) renews interest in fast compression that also squeezes out as much redundancy as possible. In 2009 Jarek Duda invented his asymmetri...

Full description

Saved in:
Bibliographic Details
Published in:Entropy (Basel, Switzerland) Switzerland), 2023-04, Vol.25 (4), p.672
Main Authors: Pieprzyk, Josef, Duda, Jarek, Pawłowski, Marcin, Camtepe, Seyit, Mahboubi, Arash, Morawiecki, Paweł
Format: Article
Language:English
Subjects:
Algorithms
ANS
Approximation
Asymmetry
Coding
Complexity
Compression ratio
Entropy
entropy coding
Internet
lossless compression
Markov analysis
Markov chains
Mathematical analysis
Multimedia
Multimedia communications
Multiplication & division
Optimization
Probability
Probability distribution
Quantum computers
Quantum computing
Redundancy
source coding
Statistical analysis
Teleconferencing
Video compression
Video transmission
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Source coding has a rich and long history. However, a recent explosion of multimedia Internet applications (such as teleconferencing and video streaming, for instance) renews interest in fast compression that also squeezes out as much redundancy as possible. In 2009 Jarek Duda invented his asymmetric numeral system (ANS). Apart from having a beautiful mathematical structure, it is very efficient and offers compression with a very low coding redundancy. ANS works well for any symbol source statistics, and it has become a preferred compression algorithm in the IT industry. However, designing an ANS instance requires a random selection of its symbol spread function. Consequently, each ANS instance offers compression with a slightly different compression ratio. The paper investigates the compression optimality of ANS. It shows that ANS is optimal for any symbol sources whose probability distribution is described by natural powers of 1/2. We use Markov chains to calculate ANS state probabilities. This allows us to precisely determine the ANS compression rate. We present two algorithms for finding ANS instances with a high compression ratio. The first explores state probability approximations in order to choose ANS instances with better compression ratios. The second algorithm is a probabilistic one. It finds ANS instances whose compression ratios can be made as close to the best ratio as required. This is done at the expense of the number θ of internal random "coin" tosses. The algorithm complexity is O(θL3), where is the number of ANS states. The complexity can be reduced to O(θLlog2L) if we use a fast matrix inversion. If the algorithm is implemented on a quantum computer, its complexity becomes O(θ(log2L)3).
ISSN:1099-4300
1099-4300
DOI:10.3390/e25040672