Context-adaptive binary arithmetic coding. Part 2

Arithmetic coding procedure as a flow diagram

We will now try to present the steps of the arithmetic coding procedure as a flow diagram. Let the alphabet of the message to be transmitted consist of the character set {xi}(in the examples above, this alphabet consisted of three characters, {a, b, EOF}, with i = 1 for a, i = 2 for b, and i = 3 for EOF). Construct an array of values

, where fi is the relative frequency of the i-th character in the message. Let P0 = 0 and PN = 1, where N is the number of characters in the alphabet. (Again, in the coding example discussed above, we have N=3 and P = {0, 0.1, 0.95, 1}.) Using the notation thus introduced, the steps to be performed during arithmetic coding of each character can be presented as a flow diagram shown in Fig. 1.

Figure 1. Flow diagram of the arithmetic coding procedure

The EncodeSymbol() procedure takes two arguments: i, the number of the character to be coded in the alphabet, and P, the Pi array. As can be seen from the flow diagram, the first coding step consists of calculating the current interval length R (using the current values of the left and right interval endpoints, L and H respectively). The quantity H is used to calculate the updated values of the interval endpoints. Thus, in the first coding step for each message character, we split the current segment. The second step consists of a renormalization procedure, shown as a flow diagram in Fig. 2.

Figure 2. Flow diagram of the renormalization procedure

As already noted when discussing renormalization, if the current interval is fully contained inside the range [0, 1), i.e. if H< 1/2, a zero is output to the resulting bitstream followed by a sequence of ones equal in length to the value of the bitsOutstanding variable. All of this is carried out inside the put_bits() procedure, shown as a flow diagram in Fig. 4. The interval endpoint values L and H are doubled.

If the current interval is fully contained inside the range [1/2, 1), i.e. if L ≥1/2, a one is output to the resulting bitstream followed by a sequence of zeros equal in length to the value of the bitsOutstanding variable (put_bits() is again used here). The interval endpoints in this case are modified so as to double the distance from L and H to 1. Therefore, the updated values of L and H can be calculated as:

L=1 – 2(1 – L) = 2L – 1 = 2(L – 1/2),

H=1 – 2(1 – H) = 2H – 1 = 2(H – 1/2),

which is carried out in this branch of the RenormE procedure.

Finally, if the current interval is fully contained inside the range [1/4, 3/4), i.e. if L ≥1/4, and H<3/4, the value of bitsOutstanding is incremented by 1, and the interval endpoints are shifted towards each other so as to double the distance from L and H to 1/2:

L=1/2 – 2(1/2 – L) = 2L – 1/2 = 2(L – 1/4),

L=1/2 + 2(H – 1/2) = 2H – 1/2 = 2(H – 1/4),

which is carried out in this branch of the RenormE procedure.

The flow diagram of the put_bits() procedure is shown in Fig. 4. This procedure takes the bit value (0 or 1) as an argument and outputs it to the resulting bitstream that represents the result of the arithmetic coding. The procedure of outputting the bit to the stream is designated as write_bit() in the flow diagram. After completing the output, the value of bitsOutstanding is checked. A sequence of !b values (here, the flow diagram uses the syntax for the Boolean NOT operation from the C language) equal in length to the value of bitsOutstanding is output to the bitstream.

Figure 3. Flow diagram of the put_bits() procedure

About the author:

Oleg Ponomarev, 16 years in video encoding and signal digital processing, expert in Statistical Radiophysics, Radio waves propagation. Assistant Professor, PhD at Tomsk State University, Radiophysics department. Head of Elecard Research Lab.