What if probability could be packed into one changing integer state instead of one shrinking interval?
That is the central intuition behind Asymmetric Numeral Systems, usually shortened to ANS.
Like arithmetic coding, ANS is an entropy-coding method. It does not discover repetition, build dictionaries or predict symbols by itself. It receives a probability model and converts those probabilities into a compact stream of bits.
Its distinctive move is elegant: the message is represented through an evolving numerical state. Common symbols change that state gently. Rare symbols require proportionally more expansion. Bits are emitted or consumed when the state grows or shrinks beyond chosen ranges.
The result is a coder that can approach arithmetic-coding efficiency while fitting extremely well with table-driven and high-throughput implementations.
Quick Read
- ANS is an entropy-coding family, not a predictive model.
- It represents a message using an evolving integer state.
- High-probability symbols consume less coding capacity than rare symbols.
- Renormalisation keeps the state inside a manageable numerical range.
- Different ANS variants include rANS and tANS.
- Table-based ANS can be extremely fast in practice.
- ANS appears in modern compression systems because it combines strong compression efficiency with implementation-friendly speed.
The One-Sentence Answer
Asymmetric Numeral Systems encode symbols by moving an integer state through probability-weighted transitions, so common symbols require smaller average state growth while rare symbols require larger growth, producing near-entropy code lengths with efficient machine operations.
Why Another Entropy Coder?
Huffman coding is simple and fast but works with integer-length codewords. Arithmetic coding can approach fractional-bit average costs very closely but involves interval state and often serial update logic.
ANS occupies an attractive middle ground.
It offers probability-sensitive coding efficiency comparable in spirit to arithmetic coding while using state transitions that can be highly efficient on modern hardware.
That combination made ANS increasingly important in contemporary codecs and compression libraries.
Start With a State, Not a Codeword
Traditional textbook coding often encourages us to think:
symbol → codeword
ANS asks us to think differently:
current state + symbol → new state
The state contains the compressed history so far.
To decode, the process reverses:
current state → recovered symbol + previous state
Lossless reconstruction depends on these transitions being perfectly invertible.
Why “Asymmetric”?
Imagine an alphabet where A is common and B is rare.
If A has probability 3/4 and B has probability 1/4, a good entropy coder should spend fewer bits on A than on B.
ANS achieves this through asymmetric allocation of state transitions. Common symbols are assigned more states or denser transitions. Rare symbols receive fewer.
The state space itself reflects the probability model.
A Useful Mental Model: Numbering All Possible Messages
Imagine assigning integers to possible symbol sequences.
If A is common, sequences ending in A should occupy many nearby integer states. If B is rare, B-related states should be sparser.
Encoding a symbol moves from one integer to another according to this probability-shaped numbering system.
As the state grows, its binary representation accumulates information. When the state becomes too large for the working range, low-order bits are emitted and the state is renormalised.
Probability Appears as State Growth
In an ideal entropy coder, a symbol with probability p costs roughly -log₂ p bits.
ANS reproduces this relationship through multiplicative state growth.
A common symbol causes modest growth. A rare symbol causes larger growth. Over many symbols, the average number of emitted bits follows the informational cost implied by the probabilities.
The geometry differs from arithmetic coding, but the pricing rule is the same.
Renormalisation: Keep the State Manageable
If the state grew forever, it would eventually require an impossibly large integer.
ANS therefore keeps the state within a chosen range.
During encoding, when the state would become too large, some low-order bits are written to the output and the state is reduced. During decoding, when the state becomes too small, bits are read back from the compressed stream to restore it.
state grows → emit bits → continue state shrinks → consume bits → continue
This is conceptually similar to arithmetic coding’s renormalisation: an unbounded theoretical process is converted into bounded machine state plus a bitstream.
rANS: Range Asymmetric Numeral Systems
rANS uses arithmetic formulas based on integer frequencies and cumulative symbol ranges.
The encoder maps a symbol and current state to a larger state according to the symbol frequency. The decoder can recover the symbol from a residue-like portion of the state, then invert the mapping.
Because the operations are integer-heavy and compact, rANS can be implemented efficiently in software.
tANS: Table-Based ANS
tANS precomputes state-transition tables representing a discretised probability distribution.
Encoding and decoding can then rely heavily on table lookups plus bit operations rather than repeated division or interval arithmetic.
This makes tANS attractive when speed and predictable implementation cost matter.
Finite State Entropy, associated with modern codecs such as Zstandard, uses table-based ANS ideas.
The Probability Table Is Part of the Contract
Encoder and decoder must agree on symbol frequencies or on the table derived from them.
If the source has probabilities 0.7, 0.2 and 0.1 but the decoder uses a different table, state transitions no longer invert correctly.
So ANS does not remove model transmission. It merely provides an efficient way to encode symbols once the model is shared.
Frequencies Must Be Quantised
Practical ANS usually represents probabilities with integer frequencies summing to a chosen table size.
A true probability such as 0.317829 cannot always be represented exactly. It is approximated by an integer count.
This introduces a small modelling loss. Larger tables provide finer probability resolution but consume more table space and setup cost.
Once again, precision has a price.
Why ANS Can Be Fast
Modern processors are exceptionally good at integer arithmetic, shifts, masks and table lookups.
ANS can exploit those strengths.
It also permits implementations that interleave several independent ANS states. While one state waits on a dependency, another can be processed, improving instruction-level parallelism.
This is one reason ANS became compelling in high-throughput compression.
Interleaving States
A single state is sequential: each symbol depends on the state produced by the previous one.
But a codec can maintain two, four or more independent ANS states and distribute symbols among them. Those states can be updated in an interleaved schedule.
The compressed representation remains exact, while the processor gains more opportunities to execute independent work.
Compression architecture has adapted to hardware architecture.
Why Decoding Direction Can Feel Strange
In basic forms of ANS, the algebra naturally behaves like a stack: the last symbol encoded is the first symbol decoded.
Practical implementations organise buffers or encode input in reverse so the user-visible decoded sequence comes out in the desired forward order.
This is not a flaw. It is a consequence of the reversible state machine.
ANS Versus Arithmetic Coding
Both methods aim to convert probability estimates into code lengths close to -log₂ p.
- Arithmetic coding tracks a numerical interval or range.
- ANS tracks one or more integer states with probability-shaped transitions.
Arithmetic coding has an especially intuitive probability-interval interpretation. ANS often fits fast table-based or integer implementations beautifully.
Which is better depends on implementation, probability model, hardware, latency, parallelism and ecosystem constraints.
ANS Versus Huffman Coding
Huffman coding gives each symbol an integer-length prefix codeword. For many distributions this is excellent, fast and simple.
But when probabilities do not align neatly with powers of two, Huffman can leave coding efficiency unused.
ANS can realise finer average bit costs across a sequence because the state carries fractional informational cost over time.
That advantage matters especially when compression ratio and high throughput are both valuable.
A Concrete Intuition: Common Symbols Own More Doors
Imagine a hotel with 100 numbered rooms representing states.
If A has probability 70%, A gets roughly 70 convenient doors through which the decoder can identify it. If B has probability 20%, B gets about 20. If C has probability 10%, C gets about 10.
The exact ANS construction is more precise than this metaphor, but the intuition holds: common symbols occupy more of the state space.
Because they own more states, representing them requires less average state expansion.
The Model Still Does the Intelligent Work
ANS does not know whether “the” is common in English. It does not know that neighbouring pixels resemble one another. It does not discover repeated DNA motifs.
Those are model jobs.
ANS receives frequencies and converts them into bits efficiently.
structure → model → probabilities/frequencies → ANS → compressed bitstream
Good entropy coding cannot compensate for a model that assigns poor probabilities.
Modern Compression Is Often a Pipeline
A modern compressor may:
- find repeated strings;
- convert them into literals and match descriptions;
- model the probability of those symbols;
- normalise the frequencies;
- use ANS or another entropy coder to pack the symbol stream.
This explains why one article cannot own “compression” completely. Different layers solve different problems.
Why Zstandard Matters as an Example
Zstandard is a useful modern case study because it combines dictionary-style match finding with multiple entropy-coding techniques. Its Finite State Entropy component uses ANS-family ideas for suitable symbol streams, while Huffman coding is used in other parts of the format.
The lesson is architectural: a strong compressor can choose different representations for different statistical jobs rather than forcing one coder onto everything.
Tables Can Be Shared or Sent
If frequencies vary by block, the encoder may need to transmit enough information for the decoder to reconstruct the ANS table.
That setup cost matters for small blocks.
For large blocks, better probability matching may amortise the table overhead.
This connects ANS directly to our Amortisation and Boundaries articles.
The Decoder Must Mirror the State Exactly
ANS is unforgiving of disagreement.
If encoder and decoder use different frequencies, different table layouts, different renormalisation rules or different symbol order, reconstruction fails.
The compressed bitstream is therefore only half the machine. The shared state-transition contract is the other half.
Error Propagation and Framing
Because decoding depends on state, corruption can disturb later symbols. Practical formats therefore surround entropy-coded sections with lengths, checksums, block boundaries or other structures that help contain and detect failure.
Useful redundancy returns because perfect compactness is not the only engineering goal.
ANS Is a Beautiful Example of Representation Engineering
The underlying information-theoretic target is old: spend about -log₂ p bits on an event with probability p.
The novelty is representational.
Instead of a tree of prefix codewords or a narrowing arithmetic interval, ANS uses a reversible state machine whose numerical growth mirrors surprise.
Same informational law. Different machine.
Education: Separate the Three Layers
Students understand ANS more easily when three layers stay separate:
- Model: how likely is each symbol?
- ANS table or transition rule: how do probabilities shape state transitions?
- Bitstream: which bits are emitted or consumed during renormalisation?
Mix these layers together and ANS looks mysterious. Separate them and it becomes another implementation of familiar information-theoretic pricing.
Primary School: More Likely Means More Spaces
Give 10 numbered boxes to three symbols. If A has probability 0.6, assign it six boxes; B gets three; C gets one.
Ask which symbol is easiest to land on. The activity builds intuition that probability can be represented by ownership of state space.
Secondary School: State Machine Thinking
Draw a small reversible state table. Let each state reveal a symbol and point to a previous state. Then reverse the process.
Students discover how one evolving state can contain a sequence history.
JC and Beyond: Entropy Coding as Dynamical Systems
At higher levels, ANS can be studied as a family of bijective mappings over integers whose density reflects a probability distribution. The state approximately scales inversely with symbol probability, giving logarithmic code lengths after renormalisation.
This viewpoint connects number representation, finite-state machines, probability and information theory in an unusually elegant way.
An ANS Checklist
- Where do symbol probabilities come from?
- How are probabilities quantised into frequencies?
- Which ANS variant fits the implementation?
- How large is the state or table?
- How does renormalisation emit and consume bits?
- Can multiple states be interleaved for throughput?
- What table overhead is paid per block?
- How are corruption and block boundaries handled?
The Deeper Point
Arithmetic coding teaches us to see a message as one shrinking interval.
ANS teaches another equally powerful view: a message can be one evolving state.
Both obey the same deeper law. Probability determines informational cost.
Compression does not care whether we picture surprise as a shrinking interval, a longer codeword or a faster-growing state. The bill is still written in bits.