Understanding ANS coding through examples

We owe asymmetric numeral systems (ANS) to Jarek Duda who wrote multiple papers on them and their application to data compression and encryption.

I will not talk about the theory; this article is about the practical use of the technique for compression.

ANS Coding (rANS)

In our example, the message to encode is constituted entirely of three symbols: the letters S = {A, B, C}. Let us assume that we know the expected frequency of each symbol, and they are approximately proportional to F = {3, 3, 2}.

We will need the total of all values in F which we call M = 8. For all integers between 0 and 8 exclusive we assign an interval to each letter according to F:

A: 0…2 (interval length = 3)
B: 3…5 (interval length = 3)
C: 6…7 (interval length = 2)

The start of each interval is equal to I = {0, 3, 6}.

Decoding

I will start with the decoding part. I use div for integer division and mod for integer modulus (remainder from integer division). We will take the end state of the encoder and work back to recover all the symbols in reverse order to how they were encoded.

In our example, the end state is x =17910 (taken from this page). We also need to know the size of the message which will be 9 symbols.

First, we divide x by M and take the remainder:

d = 17910 div 8 = 2238
r = 17910 mod 8 = 6

Next we look which symbol does r belong to. Number 6 is in the interval 6…7, so it belongs to C. That is the first symbol we recovered.

Then we need to update the state to recover the next symbol. The relative frequency value for symbol C is Fᴄ = 2 and the position of r in the interval is (r - Iᴄ) = (6 - 6) = 0. The next value for the state x is:

x = d × Fᴄ + r - Iᴄ = 2238 × 2 + 0 = 4476

Let’s calculate d and r:

d = 4476 div 8 = 559
r = 4476 mod 8 = 4 → B

The second recovered symbol is B and the position of r in the interval is (4 - 3) = 1, so we can calculate the next state x:

x = 559 × 3 + 1 = 1678

From this point on I will just write the calculations and the recovered symbols.

d = 1678 div 8 = 209
r = 1678 mod 8 = 6 → C
x = 209 × 2 + 0 = 418

d = 418 div 8 = 52
r = 418 mod 8 = 2 → A
x = 52 × 3 + 2 = 158

d = 158 div 8 = 19
r = 158 mod 8 = 6 → C
x = 19 × 2 + 0 = 38

d = 38 div 8 = 4
r = 38 mod 8 = 6 → C
x = 4 × 2 + 0 = 8

d = 8 div 8 = 1
r = 8 mod 8 = 0 → A
x = 1 × 3 + 0 = 3

d = 3 div 8 = 0
r = 3 mod 8 = 3 → B
x = 0 × 3 + 0 = 0

The initial state is 0 which belongs to symbol A.

Our decoder recovered the message ABACCACBC. Remember that the decoder works backwards compared to the encoder, so the message is reversed.

Encoding

The encoding works similarly to the decoding, but this time we will multiply the state by M instead of dividing.

In this example the start state is x = 0. The message to encode is ABACCACBC of size 9.

As the first symbol is A, we take Fᴀ = 3 and calculate the integer division and remainder of x:

d = 0 div 3 = 0
r = 0 mod 3 = 0

For this round, that did not accomplish much. But we will be using the same formula for other values of the state x.

The next state is calculated as follows:

x = d × M + Iᴀ + r = 0 × 8 + 0 + 0 = 0

It is zero again so d and r don’t change. The next letter is a B, so the interval starts with 3 which gives the next state:

x = 0 × 8 + 3 + 0 = 3

Finally the state is not zero! The next letter is an A and we take Fᴀ = 3 for the division and remainder.

d = 3 div 3 = 1
r = 3 mod 3 = 0

Now we can calculate the next state:

x = 1 × 8 + 0 + 0 = 8

Note that the states match with those of the decoder, which is great. From this point on I will only write the calculations:

C →
d = 8 div 2 = 4
r = 8 mod 2 = 0
x = 4 × 8 + 6 + 0 = 38

C →
d = 38 div 2 = 19
r = 38 mod 2 = 0
x = 19 × 8 + 6 + 0 = 158

A →
d = 158 div 3 = 52
r = 158 mod 3 = 2
x = 52 × 8 + 0 + 2 = 418

C →
d = 418 div 2 = 209
r = 418 mod 2 = 0
x = 209 × 8 + 6 + 0 = 1678

B →
d = 1678 div 3 = 559
r = 1678 mod 3 = 1
x = 559 × 8 + 3 + 1 = 4476

C →
d = 4476 div 2 = 2238
r = 4476 mod 2 = 0
x = 2238 × 8 + 6 + 0 = 17910

That is the end state of our encoder. We already verified that feeding it to the decoder gives the same message.

Performance

Both the encoder and the decoder use division, which is an expensive operation. However in our example the decoder uses M = 8 which is a power of two, which means div and mod can be done using bit shifting and bit masking, and that is very fast! Ensuring that M is a power of two is clearly desirable.

So we have a slow encoder and a fast decoder. We can rely on compiler cleverness to convert the division into a multiplication, which speeds the encoder up a bit. Or we could choose values for F which are powers of two.

For example: F = {2, 4, 2}. Instead of Fs we are interested in ks where Fs = 2ᵏˢ, which gives k = {1, 2, 1}. I will use shl for left bit shifting (multiplication) and shr for right bit shifting (division) to calculate the next state of the encoder:

d = x shr ks
r = x mod ks
x = d shl R + Is + r

Get Denis Bredelet’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

I am using R such that M = 2ᴿ, in our case it is equal to 3 because M is 8.

Note that (Is + r) cannot be greater than (M - 1) which means that in x, d is copied as-is into the bitstream. We could split the state in two parts: the bitstream B and the “small state” which will be the new x. We’ll have:

d = x shr ks
r = x mod ks
x = Is + r
B ← d

That is a nice thing because that way, x can never grow so large that calculating it becomes an issue. To get the next x the decoder needs to pull (R - ks) bits from the bitstream depending on the symbol S.

However, it is unlikely that expected frequencies are all proportional to powers of two so our F is likely a poor match, which hurts the compression ratio. Thankfully Jarek Duda proposed a clever scheme which addresses this shortcoming.

Tabled ANS coding (tANS)

We will use the same example as previously with S = {A, B, C} and F = {3, 3, 2}.

As a first step, we will write a table with two rows. In the first row we will count integers starting from M, that will be the value of the state x. In the second row we will distribute the symbols according to F:

I placed the letters at random but the relative frequencies are respected. The pattern of the symbols has a small effect on the compression ratio, I did not try to optimise them.

Then for each symbol we will build a table that matches numbers starting from Fs with the values of x in the table above:

The order doesn’t really matter, although again it could have a small effect on compression ratios and I did not try to optimise. This information can be used to complete the decoding table:

tANS decoding table example

Let us look at this last row. What is k?

It is the number of bits to read from the bitstream. It is calculated by looking how many times does y need to be doubled to be a valid state x?

For example, let’s take the first column. We have y = 3 but the state ranges from 8 to 15. So y needs to be doubled which gives 6. This value is still not in the interval 8…15, so we double it again which gives 12.

The number x = 12 is a valid state so we stop. In this case y was doubled two times which means that k = 2.

Decoding

Now that the decoding table is ready we can get to it! The input in our example is the end state x = 11 and the bitstream B = 1000111001011 of length 13.

According to the decoding table, the first letter is C.

The next state is calculated with:

x = y shl k + b⁽ᵏ⁾ = 3 shl 2 + 3 = 15

The number b⁽ᵏ⁾ is obtained by pulling k bits from the end of the bitstream. In this case k = 2 so we pull the two bits 11 which is the binary notation for number 3.

The new bitstream is B = 10001110010 of length 11.

Let’s use the decoding table on the new state — it gives the next letter: B.

Then we can update the state and the bitstream:

x = 5 shl 1 + 0 = 10 → C
B = 1000111001

According to the decoding table, the corresponding letter is C. From this point on I will just give the calculations and the recovered symbols:

x = 2 shl 2 + 1 = 9 → A
B = 10001110

x = 5 shl 1 + 0 = 10 → C
B = 1000111

x = 2 shl 2 + 3 = 11 → C
B = 10001

x = 3 shl 2 + 1 = 13 → A
B = 100

x = 3 shl 2 + 0 = 12 → B
B = 1

x = 4 shl 1 + 1 = 9 → A
B = ∅

At this point decoding is finished since there is nothing left in the bitstream. As previously the order is reverse of how the message was encoded, which means the recovered message is ABACCACBC.

Encoding

The encoder uses a table in a similar way to the decoder. The encoding table is based on the decoding table. The first row is the same list of states x.

To help fill the remaining of the table, let us extend the three per-symbol tables with the values for k and for y’ = y shl k, used by the decoder to calculate the next state.

The encoding table has two rows per symbol which I grouped together for readability. The first row of a symbol is filled with the value of x in the corresponding small table for each column corresponding to y’. The same value is copied across a range defined by 2ᵏ. The second row of a symbol contains the offset in that range, starting with 0. That gives the value to write to the bitstream.

tANS encoding table example

Now we can start encoding the message ABACCACBC. The first symbol is A, so let us choose a number in the A row as initial state: it will be 9. There is nothing to add to the bitstream at this point.

The next symbol is B. According to the encoding table, the next state is x = 12 (column 9). Since k = 1, we need to write one bit to the bitstream — the second row of B says that bit is 1. Now we have B = 1.

The next symbol is A. Looking at column 12 in the encoding table, the next state is x = 13 and there are two bits to write to the bitstream corresponding to value 0. In binary this is written 00, so we have B = 100.

I will only write the updates to x and B for the remaining symbols below:

C → x = 11
B = 10001

C → x = 10
B = 1000111

A → x = 9
B = 10001110

C → x = 10
B = 1000111001

B → x = 15
B = 10001110010

C → x = 11
B = 1000111001011

That is the end state of the encoder. We already saw that feeding these parameters to the decoder generates the expected message.

Conclusion

Although the tANS algorithm requires to store tables in addition to the end state, it is very fast, simple to code and achieves very good compression ratios. For smaller data rANS offers very fast decoding speed, simple code and very good compression ratios without the decoding table overhead.

Both have the disadvantage that the decoder recovers symbols in reverse order to the encoder. Actually almost all compression algorithms are applied to blocks of data so it doesn’t make much practical difference.

Another limitation is that the estimated frequency of each symbol needs to be known in advance. ANS not alone in that, and compression is still good even if the frequency values are not completely accurate.