Context Adaptive Binary Arithmetic Coding

Friday, January 2nd, 2015

Context adaptive binary arithmetic coding, often abbreviated as CABAC, is an essential part of modern video compression. It performs lossless compression of a binary data stream without any prior knowledge of the particular characteristics of the data. These features make it an attractive algorithm for video compression because it is simple, effective, relatively fast, and requires no prior (or side band) communication between a client and server.

The most well known codecs that leverage CABAC are H.264/AVC and H.265/HEVC. My own codec, P.264 also leverages a version of CABAC, and I recall during the early days of P.264 development that there were surprisingly few sturdy resources available for learning more about the details of this system.

The goal for this article is to provide a gentle introduction to the process, without delving too deeply into the underlying theory of it. Additional resources for further reading will be linked inline throughout the article. Also, for those unfamiliar with basic compression concepts, check out my previous article on compression fundamentals.

Arithmetic Coding

Arithmetic coding is the form of entropy coding that is at the heart of CABAC (as well as the final two letters of the acronym). We'll begin with an introduction to arithmetic coding, and work our way backwards through the acronym to cover each additional feature of CABAC, including its binary, adaptive and context adaptive properties.

Arithmetic coding leverages the precision range of a numerical value in order to pack information about a sequence of symbols. Let's walk through a simple example to visually demonstrate this concept.

Assume we have the following alphabet and symbol probabilities:

Let's also assume that we wish to encode the string BBDCA, and that we will use a floating point variable with infinite precision to accomplish this. Since our variable has infinite precision, we can store infinitely many values between 0.0 and 1.0 and we can assign a unique value to every possible sequence of symbols (of all lengths).

Quick note: do not be alarmed by this egregious liberty we've taken — although no computer can store values with infinite precision, we're merely using them to illustrate our process. Later we will see how to restrict this algorithm to fixed point and limited precision values.

Algorithm Walk-through

Arithmetic coding describes a specific and straightforward way of assigning all possible sequences of symbols to values within our range of 0.0 and 1.0. We accomplish this in the following manner, using the probability model of our alphabet.

First, we create what's called a cumulative distribution function, or cdf for short, that accumulates the probability values of each symbol in our alphabet within a particular range of values between 0.0 and 1.0. For example, the cdf for our current alphabet is the following:

In this case, our A symbol has a probability of 0.2, and so it occupies the range of 0.0 to 0.2 within our cdf. B has a probability of 0.4, so it occupies the range of 0.2 to 0.6, and so on. This process stacks the probabilities of our alphabet wtihin the 0.0 and 1.0 range, and enables us to begin assigning unique values to sequences.

Coding Algorithm

Using our cdf we could trivially code the single symbol sequences A, B, C, or D, by assigning each symbol to a value within their own range in the cdf. For example, we could assign any value between 0.0 and 0.2 to represent A. Upon decompression, the decoder would simply compare the input value against the cdf range to decipher the original symbol. So far this isn't particularly useful, but what if we continued to repeat this process by packing subsequent symbol values within the range of all previously examined symbols of a sequence? By repeating this process, we would produce a unique sub-range of values for all possible sequences.

This may seem a bit confusing at first, so let's walk through our example. Our goal is to arrive at a unique value, or range of values, within the range of 0.0 to 1.0, that uniquely identifies our input sequence of symbols. If we can accomplish this, then our decompression process will be able to reconstruct the original input sequence from this unique computed value.

Returning to our original sequence, BBDCA, we set a high value to 1.0, and a low value to 0.0. These variables identify our current usable range, which is simply the full range at the start. We encode our first symbol simply by reducing the usable range based on the symbol's range in the cdf. Thus, our first symbol of B means that we must set high to 0.6, and low to 0.2.

At this point, our encoder could simply output any value within the range of 0.2 and 0.6, and our decoder would be able to uniquely identify the first symbol as B. Since we're interested in encoding more than just one symbol however, we continue with the process.

Next we encode our subsequent symbol, another B, by mapping our cdf into our current usable range of 0.2 to 0.6. Notice how we overlay our cdf such that we scale our symbol probabilities to fit.

For this second symbol we must again reduce our high and low values to match B's probability range within our current usable range. This results in a high of 0.44 and a low of 0.28. If the encoder now decided to output any value within this range, then the decoder would be able to successfully reconstruct an input sequence of BB.

We repeat this process until we've encoded all symbols in our sequence. Once we're finished, we arrive at a high value of 0.42176 and a low value of 0.4208. If we output any value within this range, then the decoder will be able to successfully reconstruct our entire original input sequence. Common implementations will either output the low value or the midpoint of this range. For our example, we'll output the low value of 0.4208.

Decoding Algorithm

The decoding process is relatively straightforward, and follows from the encoding process. We begin by comparing our coded value of 0.4208 with our cdf. We discover that this value lies within B's range of 0.2 to 0.6, so the first reconstructed value is B.

Similar to our encoding process, we now adjust 0.4208 to map inside B's range by subtracting the start of this range (0.2) and then dividing by the width of this range (0.4). Note that we also maintain high and low values that track our current usable range.

We then compare this new result against our cdf to determine our second symbol. Since 0.552 falls within our B range of 0.2 to 0.6, we know that our second symbol must be B. We continue this process of mapping values into symbol ranges and then comparing the results against our cdf table in order to reconstruct the full sequence.

Completing the Stream

Now that we've successfully encoded each symbol in our sequence, there's still one more issue that we need to consider — how will the decoder know when to finish the reconstruction process?

To better illustrate this question, let's consider the results of encoding the following sequences: A, AA, AAA, and AAAAAA. Notice that each of these sequences encodes to the exact same value: 0.0. If you experiment with this you will find that, with our current design, any arithmetically encoded value will be perpetually decoded by the decoompressor. This will result in extra erroneous symbols being appended onto an output, which prevents us from correctly reconstructing a unique input sequence.

There are two common ways to solve this problem:

What we've just described is known as floating point arithmetic coding. It uses infinite precision to code alphabets and sequences of arbitrary lengths. In practice, for both physical and performance reasons, we must rely upon finite precision and fixed point values, so let's discuss fixed point arithmetic coding.

Fixed Point Coding

As noted earlier, floating point coding is impractical for real world computers, so we must implement our arithmetic coder with finite precision. Additionally, we'll switch over to fixed point values to leverage the integer performance available in many processors, and to allow us to easily switch between bit depths. We'll use 16 bit values for the remainder of this article, but alternate bit depth solutions flow trivially from this design.

Fixed point arithmetic coding follows the same general principles of floating point coding but relies on fixed point integers to store the high, low, and output values. Returning to our original example, our cdf is now:

Similar to our previous walk-through, we begin by setting our high value to 65535, and our low value to 0. We then move along our input sequence and adjust our high and low values based on the probability ranges of each input symbol. After encoding our first symbol, our range is reduced to the following:

So far we've encoded the first symbol in our sequence, a B. Next we encode our second symbol, and our valid range becomes the following:

You may have noticed that we are running out of precision to encode additional symbols. We didn't have this issue with floating point coding because our precision was infinite. With fixed point encoding, we quickly arrive at a valid range that is too small to uniquely encode each symbol's probability range, and so we need to modify our process.

E1, E2, and E3 Scaling

When selecting the fixed point precision of the coder, it is important that sufficient precision is guaranteed so that the entire cdf can fit within half of the provided precision. For example, if a cdf requires the use of 32,767 distinct values to encode a single symbol, then the arithmetic coder should use a minimum of 16 bits of precision.

Provided we've used a large enough integer format, then we can employ one of the following three different scaling operations to prevent us running out of precision while coding a sequence. After each symbol is encoded, we check our current high and low values, and optionally perform one of the following:

After performing a scaling operation, we re-check our newly adjusted high and low values. If the values still require scaling, then we repeat the necessary scaling operation and check the values again. We repeat this process until our high and low values occupy different hemispheres and are at least 1/2 our precision range apart.

Decoding Process

Decoding with support for e-scaling is slightly more involved because we need to properly account for the scaling operations that occurred during the encoding phase. Luckily, this process is essentially the inverse of the encode scaling process. After we decode each symbol we check our high and low values. If the criteria for an e-scale has been met, we perform the necessary scaling operation but instead of writing out a 0 or a 1, we shift in the next bit from our input stream.

Binary Arithmetic Coding

Binary arithmetic coding (BAC) refers to an arithmetic coder that only operates on alphabets with precisely two specific symbols: 0 and 1. Binary coders are an attractive solution because they are simple and may be heavily optimized. Also, since the alphabet of a binary coder is always known, no additional communication is necessary between an encoder and decoder in order to define and agree on the set of symbols in an alphabet. For these reasons, binary coders are also particularly useful for adaptive coding (which we'll get to in a moment).

The biggest drawback to binary arithmetic coders is that they are unable to take advantage of higher level structural similarities in a sequence. Let's use the following example to illustrate this important point.

Binary vs. Multi-Symbol Coding

Assume we have the binary sequence 001011010010010 and wish to analyze the minimum coding rates when using a binary model versus a multi-symbol model.

  1. Binary Model:
    If we use a binary model, then our sequence consists of 15 symbols with 9 zeroes and 6 ones. Assuming that our input string is representative of our probability model, we compute the Shannon entropy of this model to be 0.97 bits per symbol.

    We then multiply our entropy by the number of symbols in the input to realize a minimum compressed size of 15 bits for this sequence.

  2. Multi-Symbol Model:
    If we use a multi-symbol model, then our sequence consists of 5 symbols: 1x 001, 1x 011, and 3x 010. We compute the entropy of this model to be 1.37 bits per symbol. If we multiply this value by the number of symbols in our sequence, we arrive at a total minimum compressed size of 7 bits.

We can clearly see that a multi-symbol processor could potentially produce a more efficient result. The insight here is that, by combining binary values into higher level symbols, we are reducing the number of symbols in our sequence at a faster rate than the increase in entropy. Furthermore, since our model does not include all combinations of three digit binary symbols, we might be able to gain even further efficiencies.

Binary Coding

The operation of a binary coder is almost identical to that of the fixed arithmetic coder described in the previous section. The primary distinction is that instead of a multi-symbol cumulative distribution function, binary coders have a simple two symbol cdf which can be described by a single value, the mid point. The mid point partitions the probability range into two distinct regions that define the probabilities for each of the two symbols in the alphabet.

All other operations follow the design of our fixed point arithmetic coding scheme.

Adaptive Binary Arithmetic Coding

Now that we've defined a fixed point binary arithmetic coding scheme, we're ready to make it adaptive. As previously discussed, one of the advantages of binary coding is that the alphabet is always known and does not need to be communicated between the encoder and decoder.

This is great, but it leaves out one other necessary piece — the probability model. Without the model, we do not know which symbol is more common, and this will make it difficult to efficiently encode a sequence.

Adaptive coding is the process of learning a probability model as we code a sequence or sequences. We assume that past symbols in a sequence are a relatively useful indicator of future symbols, and that the more symbols we process, the more accurate our model will become.

Adaptive Process

We begin by initializing our cdf to assign equal probability to each symbol:

Then, we begin our regular binary arithmetic coding process, but after each symbol is encoded we update our probability model. If we encode a 0, we increase the probability of 0's, and similarily if we encode a 1 we will increase the probability of 1's.

For example, if we encode the sequence 00000000, we will arrive at the following cdf that expects a significantly increased probability of future 0's, and a decreased probability of 1's. The closer our future symbols match this expected probability distribution, the greater our coding efficiency.

The adaptive decode process is identical to the encode process, and it will learn the exact same probability cdf as it decodes each symbol. Both processes must have identical cdfs for each iteration in order to ensure proper reconstruction of the input sequence.

The benefits of adaptive binary arithmetic coding are its simplicity, performance (the cdf may be updated very quickly), and the fact that no side band data needs to be communicated in order to synchronize the encoder and decoder. A significant drawback however is that the cdf may contain inaccurate data due to abrupt changes in the symbol stream — recall that our adaptive cdf is based on past history and this history may be significantly different than future symbols. In this case, we need a slightly augmented form of adaptive coding known as context adaptive arithmetic coding.

Context Adaptive Binary Arithmetic Coding

As previously described, there are cases where our simple adaptive model will fail to yield efficient results due to abrupt, or at least historically divergent, changes in the sequence. When this happens, our adaptive model will see significantly reduced efficiency but it will recover over time.

To speed the recovery of our adaptive cdf, we introduce the notion of contexts which are essentially cached snapshots (or bins) of our cdf. Only a single bin may be active at a time, and it will specify our current probability model.

After each symbol is coded, we examine the set of recently processed symbols and decide whether to continue using the current context, or switch to another one.

While a context is active, it's probabilities are updated in the same manner as our adaptive binary coder (described in the previous section). This gives us the ability to adapt to large or global probability changes, while maintaining our ability to adapt to more gradual, or local changes.

Contexts should be carefully chosen and modelled after the expected characteristics of the input data. For example, we could craft our contexts to enable us to quickly adapt to sudden silence in an audio stream, or a sharp transition in a video.


The purpose of this article was to provide a relatively comprehensive summary of the theories and practical considerations of CABAC. If you're interested in learning more about this form of compression, check out this paper which describes the design of the CABAC module within the H.264 video codec.

Also, check out this github repo for an example implementation.

Thanks for reading!