Libvpx Boolean Coder vs Arithmetic Coding

This article explores the fundamental differences between the libvpx Boolean coder and standard arithmetic coding. While both are entropy coding techniques designed to compress data by encoding symbols based on their probabilities, they differ significantly in mathematical complexity, precision, execution speed, and hardware friendliness. Understanding these differences highlights why the libvpx coder is uniquely optimized for real-time video codecs like VP8 and VP9.

Overview of the Two Coders

Standard arithmetic coding is a mathematically precise method of entropy coding. It represents an entire message as a single fractional number within a shifting interval between 0 and 1. As more symbols are encoded, the interval narrows based on the probability of each symbol, requiring high-precision multiplication and division to calculate the new boundaries.

The libvpx Boolean coder (often called the VPX bool coder) is a highly optimized, multiplication-free approximation of arithmetic coding. It is designed specifically for speed in software and simplicity in hardware implementations. Instead of maintaining exact mathematical intervals, it simplifies the range-updating process to keep computational overhead to a minimum.

Key Differences

1. Mathematical Simplification and Speed

• Standard Arithmetic Coding: To update the coding interval, standard arithmetic coding requires multiplying the current range by the probability of the symbol being encoded. High-precision multiplication and division are computationally expensive and can bottleneck real-time video decoding.
• Libvpx Boolean Coder: The libvpx coder eliminates the need for multiplication. It approximates the range division using bit shifts and additions. By restricting the range variable to a specific 8-bit precision window, the coder can determine interval splits using fast bitwise operations. This sacrifice in mathematical precision results in a massive boost in execution speed.

2. Register Size and Precision

• Standard Arithmetic Coding: Standard implementations often track intervals using high-precision registers (32-bit, 64-bit, or even arbitrary-precision arithmetic) to prevent underflow and overflow during long streams of data.
• Libvpx Boolean Coder: The libvpx coder uses an 8-bit register to track the range (range) and a 32-bit or 64-bit register to track the exact position within that range (value). As soon as the range drops below a certain threshold (typically 128), the coder shifts the registers left to output or read new bits. This tight control of register width ensures the coder runs efficiently on low-power CPU architectures.

3. Probability Representation

• Standard Arithmetic Coding: Standard coders, such as CABAC (Context-Adaptive Binary Arithmetic Coding) used in H.264 and H.265, map probabilities to complex, dynamically updated state machines with hundreds of states.
• Libvpx Boolean Coder: The libvpx coder represents probabilities as simple 8-bit integers ranging from 1 to 255 (representing the probability of a zero-bit occurring, scaled out of 256). This straightforward probability estimation model reduces memory footprint and makes context modeling highly efficient.

4. Compression Efficiency vs. Computational Overhead

• Standard Arithmetic Coding: Standard arithmetic coding achieves near-optimal compression performance, pushing data density very close to the theoretical Shannon entropy limit.
• Libvpx Boolean Coder: Because the libvpx coder uses approximations rather than exact multiplication, it suffers from a minor loss in compression efficiency (typically less than 1% compared to a true arithmetic coder). However, this negligible loss is offset by the massive reduction in the CPU cycles required to decode the stream.

Summary of Differences