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.

Book cover: Video Encoding, Volume 1 of the Fora Soft Video Engineering Handbook

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.

Read it on Amazon →Kindle & paperback · Fora Soft Video Engineering Handbook

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.

Book a 30-min call →WhatsApp →Email us →