Arithmetic coding is a near-optimal lossless compression technique that turns a stream of symbols into a sequence of bits as short as the entropy lower bound allows. Unlike older techniques like Huffman that assign whole numbers of bits to each symbol, arithmetic coding can encode a single symbol in a fractional number of bits — meaning it doesn't waste any space rounding up to the next bit. Over millions of symbols in a typical video frame, the savings add up to several percent.
The intuition: arithmetic coding represents the entire input message as a single floating-point number between 0 and 1, where each symbol narrows down the range further. Frequent symbols barely change the range (using almost no bits); rare symbols narrow it dramatically (using many bits). The final number is written out in just enough binary digits to uniquely identify the chosen range. Combined with context-adaptive probability estimates that update as the encoder scans the frame, you get coding that adapts to local statistics in real time.
For a product team, arithmetic coding is the mathematical backbone of CABAC (H.264, HEVC) and a variant called daala_bool (AV1). It contributes roughly 10–15 % of any modern codec's compression efficiency. The cost is computational: arithmetic coding is inherently serial (each symbol depends on the running state), so it's hard to parallelise and is often the bottleneck of low-power decoders. For an executive summary: arithmetic coding is why the same video at the same visual quality is meaningfully smaller in H.264 Main profile than in Baseline profile — the difference is entirely in the entropy coder.
The book · Volume 1 of 7
Video Encoding: A Complete Guide to Video Compression — From Pixels and Color to H.264, HEVC, AV1, Quality Metrics, and AI
Arithmetic coding squeezes the last few percent out of a bitstream and sets how much CPU a decoder spends per frame. The volume covers arithmetic coding in depth: entropy coding, CAVLC and CABAC, AV1's entropy coder, and the profile choices that follow from them. Written by Nikolay Sapunov, CEO at Fora Soft.
Weighing arithmetic coding efficiency against decode cost on low-end devices?
We will profile decode load and bitrate across codec profiles on your target devices and give you a profile recommendation per device class. 250+ video products shipped since 2005.