PaperlayerView exact revision on arXiv

Source-linked AI summary

Asymmetric numeral systems

Jarek Duda

arXiv:0902.0271v5cs.ITcs.CRmath.GM

TL;DR

Entropy coding must represent freely chosen symbol probabilities efficiently, while conventional approaches either approximate probabilities or use a more complex range state. The paper introduces asymmetric numeral systems, including precise ABS and fast, table-based ANS, and applies them to encryption and error correction near Shannon’s limit.

  • Problem

    The paper addresses how to encode symbols from freely chosen probability distributions efficiently without the approximation of Huffman coding or the two-state range representation of arithmetic coding.

  • Method

    It generalizes numeral systems into asymmetric binary and general systems that use one state, uniformly distribute symbol subsets, and optionally initialize ANS tables with a pseudorandom generator.

  • Results

    ABS provides an extremely precise binary entropy encoder, while ANS offers high compression rates with fast table-based transfers and can also support key-initialized encryption.

  • Takeaways & Limitations

    The framework spans precise binary coding, fast general-symbol coding, encryption, and an error-correction approach described as near Shannon’s limit with expected linear or N lg(N) correction time.

  • Takeaways & Limitations

    The correction analysis has a practical limit because rare large local error concentrations can produce an infinite expected correction-tree width.

Abstract

from arXiv · show

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.

1 Introduction

The paper introduces asymmetric numeral systems as entropy coders that generalize standard numeral systems to freely chosen symbol probabilities. It presents ABS and ANS variants, encryption through randomized initialization, and an error-correction approach near Shannon’s limit.

  • Arithmetic coding is precise but requires two state values to define the current range, whereas Huffman coding approximates probabilities with powers of two.
  • ANS generalizes standard numeral systems from equiprobable digits to freely chosen probability distributions by distributing symbols uniformly rather than assigning them to ranges.
  • ABS provides an extremely precise binary entropy encoder whose symbol probability can change freely and can serve as an alternative to arithmetic coding.
  • ANS uses initialized pseudorandom coding tables to encode several bits per table use, combining arithmetic-coding-like compression rates with Huffman-like transfers.
  • A key-driven initialization can additionally encrypt data, while delaying computation to initialization makes brute-force key testing more expensive.
  • The proposed error-correction method is described as approaching Shannon’s limit for any noise level with expected linear or N lg(N) correction time.

2 General concept

The general concept represents the encoder state as one natural number and bijectively transforms it with symbols according to their probabilities. ANS distributes symbol subsets uniformly and reversibly maps states to symbols and smaller states.

  • The paper seeks to encode a known, stationary symbol distribution into the shortest possible bit sequence.
  • Unlike arithmetic coding’s two range-defining states, the proposed encoder stores its state as one natural number x.
  • The state x represents all processed symbols and can be uniquely reversed because the encoding rules are bijective.
  • For symbol s, the state set is partitioned into subsets of sizes x_s approximating xq_s, so choosing a subset has probability q_s.
  • The bijective transform x ⇌ (s, x_s) stores a symbol with approximately lg(1/q_s) bits while retaining a residual state with lg(x) − lg(q_s) bits.
  • ANS distributes the subsets uniformly across the state interval instead of dividing the interval into contiguous ranges as in range coding.

3 ASYMMETRIC BINARY SYSTEM (ABS)

The asymmetric binary system supplies explicit coding and decoding formulas for two symbols with freely selected probability q. It is bijective and reduces to the ordinary binary numeral system when q = 1/2.

  • ABS is the binary case in which practical explicit formulas exist for coding and decoding.
  • For two symbols, q denotes the probability of symbol 1 and 1 − q denotes the probability of symbol 0.
  • The subset sizes are selected as x_1 = ceil(xq) and x_0 = x − x_1, approximating the desired probabilities.
  • The decoding rule determines symbol 1 from jumps in the ceiling sequence ceil((x + 1)q) − ceil(xq).
  • The corresponding coding rule reconstructs x from the selected symbol and residual state using the fractional remainder r = ceil(xq) − xq.
  • When q = 1/2, ABS becomes the usual binary numeral system with the digit labels switched.

4 Stream coding/decoding

Stream coding keeps the ANS state within a fixed interval by transferring its youngest base-b digits to or from the output. The state distribution is expected to be approximately proportional to 1/x, while each symbol step transfers one of two adjacent digit counts.

  • Stream coding/decoding: ABS/ANS stream coding transfers information between a natural-number state and base-b output digits to keep the state in a fixed range.
  • Stream coding/decoding: A b-unique interval guarantees that repeated reductions or digit insertions reach the interval in a unique way.
  • Stream coding/decoding: Stream decoding emits x mod b and replaces x with floor(x/b), while stream coding applies the inverse state transform and inserts an input digit.
  • State behavior: The state’s random behavior comes from random symbol selection, generally irrational lg q_s / lg b values, and the fact that coding is only near x/q_s.
  • State behavior: The state visits are expected to cover the possible space approximately uniformly, giving a state probability proportional to 1/x.
  • Single-step analysis: The step analysis assumes probability approximation through l_s and relates the post-step state to the distributing function and boundary condition.
  • Single-step analysis: For a coding step, the number of transferred digits has at most two possibilities, k_s − 1 and k_s, separated by a boundary X_s.

5 Asymmetric Numeral Systems(ANS)

ANS extends numeral-system coding to arbitrary symbol probabilities by using a single state and distributing symbol occurrences across the state space. The section develops precise and faster initialization methods, analyzes approximation error, and describes key-based randomized coding tables.

  • General construction: ANS directly encodes symbols with arbitrary probability distributions instead of reducing them to binary choices.The general case can be handled straightforwardly, although practical explicit formulas for more than two symbols are unavailable and coding functions may be calculated during initialization.
  • Precise coder: The precise coder fixes a finite state range and approximates each symbol probability through prescribed symbol counts.The coding functions are determined by the counts of each symbol within the fixed range.
  • Precise coder: In simulations, the symbol-count deviation is usually smaller than 1, although some distributions may attain the pessimistic bound.The method selects symbols using ordered candidate positions, with a priority queue providing the smallest element at each step.
  • Statistical initialization: A faster statistical initializer fills a table with the required symbol multiplicities and samples from it while progressively reducing the table.This behaves diffusively at first and self-corrects as the process approaches the table’s end.
  • Encryption: Fixing symbol counts still leaves an exponentially large family of coding functions, allowing a key to select randomized tables for encryption.Randomized initialization makes processing table-based and faster, while requiring full initialization for each brute-force key trial.
  • Statistical initialization: The expected sampling width follows Mq(1 − M/N), agreeing with exact calculations and approaching the expected value as M approaches N.For small M the behavior is diffusion-like; the correction factor distinguishes the finite-population process from the binomial approximation.

6 Statistical analysis

The analysis models ANS state evolution as approximately random and derives practical estimates for state distributions, imprecision, and compression loss. Simulations generally support the approximations, while pathological rational-probability cases can worsen compression.

  • 6.1 Probability distribution of the states: ANS state evolution has three sources—symbol asymmetry, uniform covering, and diffusion—that make the state behave approximately like a random variable.The paper argues that these effects should allow movement between states, although pathological cases can restrict the reachable subset.
  • 6.1 Probability distribution of the states: For the idealized zero-error model, the stationary distribution is D(y) = y, while finite discrete states produce a nearby but non-continuous distribution.The author could not prove the correction remains small, but numerical simulations indicate it is much smaller than the approximation error.
  • 6.1 Probability distribution of the states: The state probability is approximately proportional to 1/x, providing the basis for subsequent estimates of symbol-transfer probabilities and expected coding behavior.The analysis uses harmonic-number approximations and normalization to calculate these quantities.
  • 6.2 Evaluation of the compression rate: In practice, approximation estimates are usually close to simulations, although the coder’s imprecision is treated through rough expected-value calculations.The analysis separates losses associated with l and b from losses caused by coder imprecision, assuming relevant quantities are independent.
  • 6.2 Evaluation of the compression rate: 10-100 times smaller values than pessimistic estimates are observed, while the general log(l)/l dependence remains consistent with simulations.The paper reports that a loss around 1/1000 can usually be achieved when l/n is below 100 for ScD initialization.
  • 6.3 Probability distribution of digits and symbols: The nonuniform state distribution creates small digit-distribution deviations, but increasing l to 10^5-10^6 can make the effect extremely weak and reduce it further by orders of magnitude.The paper states that the closest-to-Shannon symbol distribution can be characterized and used to modify coding functions.

7 Practical remarks and modifications

The practical discussion covers probability-model handling, implementation trade-offs, table design, state initialization, and decorrelation. ANS provides precise table-based coding with fast transfers, while ABS favors formula-based precision and flexible distributions.

  • 7.1 Data compression: Compression implementations either store tables for many probability distributions, use a constant distribution, or estimate probabilities dynamically during encoding.Dynamic estimation avoids storing tables and supports locally varying symbol distributions, but is somewhat slower.
  • 7.1 Data compression: ANS can use a table smaller than 100kB to obtain a very precise coder encoding about 8bits per table use.Changing probability distributions requires separate initialization, and reverse encoding and decoding may require two processing passes.
  • 7.1 Data compression: ABS offers more precise formula-based coding with freely changing binary probabilities, whereas ANS uses initialized tables to transfer a few bits per operation.The paper contrasts ABS flexibility and precision with ANS’s fast table-based transfers and arithmetic-like compression rates.
  • 7.2 Bit transfer and storing the tables: Bit-transfer speed can be improved by combining extraction and state shifting into one operation, while small tables determine transfer counts, masks, and state updates.Coding and decoding tables can encode symbol transitions and the number or sequence of transferred digits.
  • 7.2 Bit transfer and storing the tables: Table layouts trade memory for speed, ranging from compact indexed representations to storing complete transitions or generating symbol-specific low-level code during initialization.The decoding table can store the symbol and new state, with additional transfer information embedded in table bits.
  • 7.3 Initialization and modifications: The initial state may be fixed or random, but the final state must be stored for reversal; initialization can also encode information, reducing wasted bits for small files.This benefit is most relevant when many small files are encoded separately.
  • 7.3 Initialization and modifications: XORing transferred blocks with a reproducible cyclic sequence can reduce digit correlations by many orders of magnitude while preserving decodability.The same sequence is used during decoding, and varying block lengths make the transformation difficult to remove from the known sequence alone.
  • 7.3 Initialization and modifications: The number of internal states can be increased exponentially by representing the bit table as one or several large numbers, enabling faster operation.This modification addresses cases where the usual (b −1)l states are insufficient.

8 Cryptographic applications

ANS supports cryptographic use through key-dependent coding tables and costly initialization, while retaining fast entropy coding. The paper also identifies residual weaknesses and practical mitigations.

  • Keyed initialization: ANS can use a key to initialize a pseudorandom generator that creates coding tables, producing different encoded sequences for the same parameters.The paper presents this as making the coding function practically unique for a given key.
  • Keyed initialization: Checking a candidate key requires completing the initialization, making the approach more resistant to brute-force attacks.The initialization time can be deliberately increased through additional pseudorandom-generator computation.
  • Keyed initialization: The coding function does not directly reveal the key because each observed symbol can correspond to multiple possible random-variable values.The paper suggests secure pseudorandom generators can further protect the seed state.
  • Limitations and mitigations: ANS-based encryption has weaknesses because short blocks and imperfectly random state behavior can expose statistical or coding-function information.The paper proposes additional encryption layers, random initialization, or random prefix bytes as protections in specific scenarios.
  • Limitations and mitigations: For nearly uniform byte sequences, encryption can perturb the symbol distribution with the same pseudorandom generator, but this slows state changes and enlarges the output.The alternative of homophonic substitution increases message size further.

9 Near Shannon’s limit error correction method

The paper connects redundancy across short blocks so the message can be corrected globally rather than losing an entire block after concentrated errors. ANS state or hashing supplies the connection and can approach Shannon’s limit with practical correction time.

  • Motivation: Independent block codes can lose an entire block when local errors exceed the block’s correction boundary.The proposed method instead connects block redundancy so the whole message participates in correction.
  • Core approach: Connected redundancy transfers unused redundancy from low-error regions to locally concentrated errors through the coder’s internal state.The state contains checksum-like information about the already processed message.
  • Core approach: A hash-derived state can be combined with each block so an undamaged block verifies against the current state, while state divergence signals later damage.The figure describes XORing block bits with state bits before decoding.
  • Detection behavior: After multiple errors in one block, subsequent blocks detect damage with probability pd = 3/4, helping locate additional corrections.This detection probability is higher than the probability associated with ordinary proper correction.
  • Variants: The approach can use either a conventional block code with connected redundancy or checksum bits embedded directly in each block.The latter arrangement does not require a standard block code.

9.1 Very short introduction to error correction

The section motivates global error correction by contrasting Shannon-capacity coding with practical independent-block schemes. It explains why local error fluctuations make fixed block redundancy inefficient and vulnerable.

  • Correction foundations: Forward error correction adds recognizable redundancy so damaged received sequences can be mapped back to valid codewords.Valid codewords must be sufficiently separated for nearest-codeword correction.
  • Correction foundations: Triple modular redundancy encodes one bit as 000 or 111 and corrects any single-bit error using Hamming distance.The code chooses the value appearing most often in the three transmitted bits.
  • Shannon limit: For a symmetric channel, h(pb) measures the uncertainty of a received bit, leaving 1 − h(pb) bits of information per transmitted bit.The corresponding theoretical redundancy rate is h(pb) / (1 − h(pb)) bits per message bit.
  • Shannon limit: Shannon’s theorem permits correction arbitrarily close to capacity for typical errors, but the standard proof requires checking an exponentially large set of possible corrections.This makes the theoretical construction impractical directly.

9.2 Path tracing approach

The path-tracing method spreads verification throughout the message using forbidden states, so errors can be detected shortly after occurring. At a suitable detection probability, undetected correction paths stop growing exponentially while correction remains practical.

  • From global checks to path tracing: A hash-based proof checks all typical corrections against a final state, but the practical method distributes this verification across the message.The distributed design detects errors during processing rather than only at the end.
  • Practical limitation: Practical correction must account for large error concentrations, so its capacity may need to exceed the theoretical threshold slightly.The text identifies this as an additional issue for nearly linear correction methods.
  • Practical limitation: After an error, the state can accidentally return to the correct path before detection, creating a wrong correction; suitable parameters make this probability asymptotically vanish.The final coder state must also be stored and protected for decoding to begin correctly.
  • Forbidden-state detection: The coder reserves a forbidden symbol with probability pd; after an error, random state evolution reaches a forbidden state with probability pd per step.Allowed symbols are rescaled to preserve the intended data distribution.
  • Capacity threshold: At the critical threshold, the expected number of corrections that evade detection no longer grows exponentially, and the threshold equals Shannon’s limit.The method pays for this detection probability in capacity.
  • State-space requirement: If the coder has sufficiently many states, the expected number of undetected correction scenarios can remain bounded, allowing the proper correction to pass almost certainly.The text gives a state-space example growing as N^3 while the expected scenario count is bounded by N^2.

9.3 Practical correction algorithms

The section develops practical correction algorithms that trade redundancy and search complexity against proximity to Shannon’s limit. Tree-based methods use verification probabilities and prioritized correction searches to obtain finite expected width and near-linear or N lg(N) correction time.

  • Practical correction limits: Practical correction algorithms must keep the expected number of surviving candidate corrections finite at each point.This motivates gradually extending candidate corrections rather than searching the exponentially large space of whole-message corrections.
  • Moving the tree front: The proper correction is prioritized by the number of changed bits, with larger candidate sets improving recovery probability but increasing runtime.If the candidate set is too small, the correct path can be lost and later damage-density increases can reveal that failure.
  • Practical correction limits: The practical limit is somewhat above Shannon’s limit, reaching up to twice the limit as p_b approaches 0.5.The section gives a choice of p_d based on the entropy terms to approach this practical boundary.
  • Correction-tree algorithm: Correction-tree methods can achieve finite expected tree width and, with polynomially many decoder states, almost-certain practically linear-time recovery.The basic-weight tree algorithm has N lg(N) time complexity when selecting the highest-weight node, while finite width requires p_d above the relevant threshold.
  • Correction-tree algorithm: The correction-tree boundary is at most 13.1% above the practical correction limit, with the largest gap near p_b ≈ 0.03.The tree can nevertheless grow large wrong subtrees, and optimal switching parameters are left to experimental determination.

9.4 Generalized block codes

Generalized block codes embed redundancy into ANS states so that state validity detects or helps correct errors while preserving connected rather than independent block redundancy.

  • Connected block redundancy: ANS tables can combine state-agreement verification with per-step error detection and standard block-code mechanisms.The internal coder state connects the redundancy across blocks, while block-code structure can immediately repair simple damages.
  • Hamming-distance constructions: A parity-based distance-2 construction marks half the states forbidden and gives p_d = 1/2.The construction inserts a parity bit, doubles the state range, and retains the original symbol distribution through initialization.
  • Hamming-distance constructions: Distance-2 coding immediately detects a single error within one block, while forbidden states also indicate possible earlier multiple errors.This reduces the set of candidate corrections compared with relying only on the general correction mechanism.
  • Hamming-distance constructions: Larger Hamming distances can be created by forbidding states near each allowed state across the youngest K positions.Allowed states are generated from block codes using XOR masks and bit permutations that preserve minimum Hamming distance.
  • Table construction: A pseudorandom generator can select the masks and permutations, including key initialization when encryption is also desired.This extends the earlier ANS initialization strategy to the construction of connected error-correcting state tables.
Loading 0902.0271v5…