AV1 Coefficient Tokenization and Entropy Optimization

This article explores the mechanics of transform coefficient tokenization in modern video compression, focusing specifically on the AOMedia Video 1 (AV1) codec. It breaks down how quantized frequency coefficients are mapped into compact syntax elements and details how AV1 optimizes symbol probability distributions to maximize the efficiency of its entropy coding engine.

Understanding Coefficient Tokenization

In video coding, residual data—the difference between a predicted frame and the original frame—is converted into the frequency domain using transforms like the Discrete Cosine Transform (DCT) or Asymmetric Discrete Sine Transform (ADST). After transformation, the resulting frequency coefficients are quantized, leaving a two-dimensional grid populated predominantly by zeros and small integers, with occasional high-magnitude values at low frequencies.

Coefficient tokenization is the process of converting these two-dimensional arrays of numerical values into a structured stream of symbols (tokens) suitable for an entropy coder. Rather than transmitting raw numerical amplitudes directly, tokenization abstracts the values into logical components:

• Significance: Whether a coefficient is non-zero.
• Signs: Positive or negative values.
• Magnitudes: Small values vs. large values.
• Run-lengths: The distance between consecutive non-zero coefficients.

By structuring coefficients into standardized categories, the encoder can group similar statistical events together, allowing the entropy engine to assign shorter codes to frequently occurring patterns.

AV1’s Non-Binary Entropy Coding Model

Earlier standards like H.264 and HEVC rely heavily on binary arithmetic coding engines (such as CABAC), which require non-binary values to be completely binarized into trees of single-bit decisions before encoding.

AV1 diverges from this approach by using a multi-symbol arithmetic coder derived from the Daala project. AV1 can encode non-binary alphabets—up to 16 symbols per cycle—using cumulative distribution functions (CDFs). Tokenization in AV1 is tailored specifically to fit this multi-symbol model, reducing serialization overhead and enabling parallel hardware processing.

How AV1 Optimizes Symbol Distribution

Entropy coding operates on the principle that rare symbols cost more bits than common symbols. To achieve maximum compression, the distribution of symbols must be shaped so that the actual probabilities closely match the model's expected probabilities. AV1 employs several key techniques to condition and optimize this distribution.

1. Multi-Level Representation (Level Splitting)

Instead of tokenizing a coefficient's entire magnitude as a single large symbol, AV1 decomposes it into progressively deeper layers:

• eob_pt (End-of-Block Position): The index of the last non-zero coefficient in the transform block, allowing the encoder to skip coding trailing zeros entirely.
• Base Levels (abs_level_gt1, abs_level_gt2): Binary flags indicating if the magnitude is greater than 1, greater than 2, etc.
• Remainder Levels: Values exceeding the initial thresholds are encoded using an adaptive base-4 alphabet or Exp-Golomb codes for the extreme tails.

This splitting ensures that the most common values (zeros, ones, and twos) dominate the low-entropy symbols, while the rarer, computationally expensive magnitudes are isolated into separate code spaces.

2. Context Modeling Based on Spatial Neighbors

A symbol’s distribution changes depending on where it appears in the block. AV1 optimizes probability modeling by assigning context states derived from neighboring coefficients.

When evaluating a specific coefficient, the encoder samples:

• The magnitudes of previously decoded immediate spatial neighbors (left and above).
• The transform block size and transform type (e.g., DCT, identity, or directional transforms).
• The frequency position (low-frequency vs. high-frequency).

If adjacent neighbors contain large values, the probability of the current coefficient being non-zero increases. By selecting a CDF tied specifically to that local context, AV1 flattens prediction error and sharpens the probability peak of the symbol, driving down entropy.

3. Dynamic CDF Adaptation

Instead of relying on fixed static probability tables or performing costly, slow updates on every single bit, AV1 adapts its CDFs on the fly after decoding symbols.

AV1 uses a fast adaptation rule that updates context-specific CDFs throughout the frame. The rate of adaptation scales based on the frequency of the context: rarely used contexts adapt slowly to avoid overreacting to noise, while frequently accessed contexts quickly converge to the true statistical distribution of the current frame content.

4. Reverse Scan Order

AV1 processes coefficients in a reverse zigzag or coordinate-specific scan order, starting from the highest-frequency non-zero coefficient (the End-of-Block) and working backwards toward the DC component (top-left).

Scanning in reverse stabilizes the statistical distribution: because higher-frequency values are predominantly zeros or small integers, scanning backward establishes a clean baseline of context that makes predicting the transition toward larger low-frequency values far more accurate.