Related Experiment Video
Updated: Jul 30, 2025
10:58
Multimedia Battery for Assessment of Cognitive and Basic Skills in Mathematics BM-PROMA
Published on: August 28, 2021
4.6K
The Compression Optimality of Asymmetric Numeral Systems
Josef Pieprzyk1,2, Jarek Duda3, Marcin Pawłowski3
1Institute of Computer Science, Polish Academy of Sciences, 01-248 Warsaw, Poland.
Entropy (Basel, Switzerland)
|May 16, 2023
Summary
Asymmetric numeral systems (ANS) offer efficient data compression. This study proves ANS achieves optimal compression for specific probability distributions and introduces algorithms to enhance compression ratios, even on quantum computers.
Area of Science:
- Computer Science
- Information Theory
- Data Compression
Background:
- Multimedia internet applications drive demand for efficient data compression.
- Asymmetric numeral systems (ANS) provide high compression with low redundancy.
- Designing optimal ANS instances requires careful selection of symbol spread functions.
Purpose of the Study:
- Investigate the compression optimality of Asymmetric Numeral System (ANS).
- Determine conditions under which ANS achieves optimal compression rates.
- Develop algorithms for discovering high-performance ANS instances.
Main Methods:
- Utilized Markov chains to calculate ANS state probabilities.
- Analyzed compression optimality for symbol sources with power-of-1/2 probability distributions.
- Developed two algorithms for finding ANS instances with improved compression ratios.
Main Results:
- Demonstrated that ANS is optimal for symbol sources with probability distributions as natural powers of 1/2.
- Presented algorithms that approximate or achieve near-optimal compression ratios.
- Analyzed algorithmic complexity, including quantum computing implementations.
Conclusions:
- ANS compression is mathematically elegant and practically efficient.
- Optimal ANS instances can be systematically found, improving compression performance.
- Future research can leverage quantum computing for further optimization.
Related Concept Videos
01:24Numerical Calculations
388
In engineering applications, the representation of the numerical value is critical. Presenting or reporting the answer is one of the essential parts of engineering practices. Numerical calculations are performed using handheld calculators or computers since numerically accurate answers are always preferred.
The solution to a problem is obtained using different methods. While manually solving algebraic symbols is one of the most common methods, the graphical method is often preferred. Computers...
The solution to a problem is obtained using different methods. While manually solving algebraic symbols is one of the most common methods, the graphical method is often preferred. Computers...
388
01:21Bulk Modulus
354
The bulk modulus is a scientific term used to describe a material's resistance to uniform compression. It is the proportionality constant that links a change in pressure to the resulting relative volume change.
354
01:29Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
88
Mechanistic models play a crucial role in algorithms for numerical problem-solving, particularly in nonlinear mixed effects modeling (NMEM). These models aim to minimize specific objective functions by evaluating various parameter estimates, leading to the development of systematic algorithms. In some cases, linearization techniques approximate the model using linear equations.
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
88
01:14Norton's Theorem
656
Norton's theorem is a fundamental principle stating that a linear two-terminal circuit can be substituted with an equivalent circuit, which comprises a current source (ⅠN) in parallel with a resistor (RN). Here, ⅠN represents the short-circuit current flowing through the terminals, and RN stands for the input or equivalent resistance at the terminals when all independent sources are deactivated. This implies that the circuit illustrated in Figure (a) can be exchanged with the...
656
00:58Significant Figures in Calculations
11.5K
Uncertainty in measurements can be avoided by reporting the results of a calculation with the correct number of significant figures. This can be determined by the following rules for rounding numbers:
11.5K
01:19Routh-Hurwitz Criterion II
307
In the application of the Routh-Hurwitz criterion, two specific scenarios can arise that complicate stability analysis.
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
307