# - Acharya T.

ISBN 0-471-48422-9

**Download**(direct link)

**:**

**19**> 20 21 22 23 24 25 .. 100 >> Next

BINARY ARITHMETIC CODING 35

the allowed precision of a digital computer. The incremental encoding and decoding process in binary arithmetic coding resolves this issue. The four general observations or rules behind binary arithmetic coding are as follows:

• Case 1: If the present range [LOW, HIGH) entirely belongs to the lower half of the interval [0.0, 1.0) (i.e., HIGH < 0.5), the encoder outputs or transmits a binary bit 0 and rescales the range by a factor 2 as [2* LOW, 2* HIGH).

• Case 2: If the present range [LOW, HIGH) entirely belongs to the upper half of the interval [0.0, 1.0) (i.e., LOW > 0.5), the encoder outputs or transmits a binary bit 1 and rescales the range by subtracting 0.5 from both LOW and HIGH and multiplying the results by a factor

2 as [2 * (LOW - 0.5), 2 * (HIGH - 0.5)).

• Case 3: If the present range [LOW, HIGH) entirely belongs to the second and third quarters of the interval [0.0, 1.0) (i.e., LOW > 0.25 and HIGH < 0.75), we keep track of this situation by incrementing a special counter SPCLjOOUNT and rescale the range by subtracting 0.25 from both LOW and HIGH and multiplying the results by a factor

2 as [2*(LOW-0.25), 2*(HIGH-0.25)). Whenever case 1 or 2 arises, the encoder checks the value of SPCLJJOUNT. If it is greater than 0, those many binary l’s (or 0’s) are output or transmitted after it outputs the binary bit 0 (or 1) as described in case 1 (or 2). After all the binary bits are output, the SPCL-COUNT is reset to count 0.

• For any other cases, there is no need to output or transmit any binary bit and also no need to rescale the range. This is a significant part of the binary arithmetic coding that leads to low bit rate.

We describe the binary arithmetic coding algorithm using the same example as in the previous section. We consider the same probability model and show how we can generate a unique binary code incrementally for the same message “cacbad.” Consider LOW and HIGH represent the low and high values of the present half-open range. The changes in the range and output of the binary bits are shown in Figure 2.4.

We begin with the half-open interval R0= [0.0, 1.0) (i.e., LOW = 0.0 and HIGH = 1.0). The special counter SPCL-COUNT is initialized to count 0. The first symbol in the message is c which represents the range R1 = [0.5, 0.9) shown in Figure 2.4. Since the new range [0.5, 0.9) entirely belongs to the upper half of the interval [0.0, 1.0), we output the binary code 1 and rescale the interval to R2= [0.0, 0.8). Since SPCL.COUNT = 0, no other binary bit is output.

The second symbol in the message is a and the corresponding range is R3 = [0.0, 0.24). Since this range entirely belongs to the lower half of the interval [0.0, 1.0), we output the binary code 0 and rescale the range to R4 = [0.0,

36 SOURCE CODING ALGORITHMS

Fig. 2.4 Binary arithmetic coding technique: an example.

0.48). This again entirely belongs to the lower half of the interval [0.0, 1.0). Hence, we output the binary code 0 and rescale the range to R5 = [0.0, 0.96).

The third symbol in the message is c and the corresponding range is R6=[0.48, 0.864). This does not require us to output any binary bit nor is the range rescaled.

The fourth symbol in the message is b and the corresponding range is R7= [0.5952, 0.672). Since this range entirely belongs to the upper half of the interval [0.0, 1.0), we output the binary code 1 and rescale the range to R8 = [0.1904, 0.344). The new range now entirely belongs to the lower half of the interval [0.0, 1.0). Hence, we output the binary code 0 and rescale the range to R9= [0.3808, 0.688). Now this range entirely belongs to the second and third quarter of the interval [0.0, 1.0) because LOW = 0.3808 > 0.25 and HIGH = 0.688 < 0.75. Hence we increment the special counter to SPCL.COUNT = 1 and rescale the range to R10=[0.2616, 0.876).

BINARY ARITHMETIC CODING 37

The fifth symbol in the message is a and the corresponding range is R11 = [0.2616, 0.44592) which entirely belongs to the lower half of the interval [0.0, 1.0). Hence we output the binary code 0 and rescale the range to R12 = [0.5232, 0.89184). Since the value of the special counter is greater than

0 (SPCLjCOUNT = 1), we output one more binary bit 1. Now the new range R12 = [0.5232, 0.89184) entirely belongs to the upper half of the interval [0.0, 1.0). As a result, we output the binary bit 1 and rescale the range to R13= [0.0464, 0.78368).

The last symbol is d and the corresponding range is R14 = [0.709952, 0.78368). As a result we rescale the range to R15 = [0.419904, 0.56736) and output the binary bit 1. At this point, we can stop encoding by sending the binary representation of any value in the final interval. In this case we can conveniently choose the value 0.5. The binary representation of 0.5 is 0.1000.... Thus, we transmit a 1 followed by as many as 0’s required by the word length used in the implementation. Hence the unique binary code for the message “cacbad” is 100100111100000 0. It should be noted that the first 9 bits, 1001001 11, represent the binary codes generated by the above incremental binary arithmetic coding procedure. The last 7 bits, 100000 0, represent 0.5 chosen from the final range [0.419904, 0.56736), assuming a 16-bit word for implementation.

**19**> 20 21 22 23 24 25 .. 100 >> Next