Arithmetic Coding
In arithmetic coding, a message is encoded as a real number in an interval from zero to one. Arithmetic coding serves a very important role in imaging standards such as JBIG and JPEG.
There are two fundamentals in arithmetic coding: the probability of a symbol and its encoding interval range. The probabilities of source symbols determine the compression efficiency. They also determine the interval ranges of source symbols for the encoding process. These interval ranges are contained within the interval from zero to one. The interval ranges for the encoding process determine the compression output.
The encoding process of an arithmetic coder can be explained through the following example:
Example
Let us assume that the source symbols are {00, 01, 10, 11} and the probabilities of these symbols are {0.1, 0.4, 0.2, 0.3}, respectively. Then, based on these probabilities, the interval [0, 1) can be divided as four sub-intervals: [0, 0.1], [0.1, 0.5], [0.5, 0.7], [0.7, 1], where [x, y] denotes a half open interval, which includes x but excludes y. The above information can be summarized in table:
Table 1. Source symbols, their probabilities and initial encoding intervals
Symbols |
00 |
01 |
10 |
11 |
Probabilities |
0.1 |
0.4 |
0.2 |
0.3 |
Initial Encoding Intervals |
[0,0.1) |
[0.1,0.5) |
[0.5,0.7) |
[0.7,1) |
To encode a message of a binary sequence
10 00 11 00 10 11 01,
We take the first symbol 10 from the message and find its encoding range is [0.5, 0.7]. Since the range of the second symbol 00 from the message is [0, 1], it is encoded by taking the first 10th of interval [0.5, 0.7] as the new interval [0.5, 0.52]. Similarly, by encoding the third symbol 11, we have a new interval [0.514, 0.52]. After encoding the fourth symbol 00, the new interval is [0.514, 0.5146]. And so on.
The compression output of this message can be any number in the last interval.
Visually, we can use the following figure:
Picture 1: Compression output
A visual illustration of the encoding process
In the above example, we assume both the encoder and decoder know the length of the message so that the decoder would not continue the decoding process forever. In the real world, we need to include a special terminating symbol so that we the decoder sees the terminating symbol, it stops the decoding process.
There are some problems in arithmetic coding which the reader may already notice:
1. Since there are no single machine having an infinite precision, “underflow” and “overflow” are the obvious problems for the real world machines. We can use a scaling process to solve this problem. Most of these machines have a 16-, 32-, or 64-bit precision.
2. An arithmetic coder produces only one codeword, a real number in interval [0,1], for the entire message to be transmitted. We cannot perform decoding process until we received all bits representing this real number.
3. Arithmetic coding is an error sensitive compression scheme. A single bit error can corrupt the entire message.
Arithmetic coding can be static or adaptive. In static arithmetic coding, the probabilities of source symbols are fixed. In adaptive arithmetic coding, the probabilities of source symbols are dynamically estimated based on the changing symbol frequencies having been seen in the message to be encoded. The process to estimate the probabilities of source symbols from the part of a message seen so far during encoding is known as modeling.
Since usually the exact probabilites of source symbols are unknown or impractical to produce, we cannot expect an arithemtic encoder to achieve maximum efficiency when compressing a message. The best we can do is to estimate the probabilities on the fly. Therefore, dynamic modeling becomes the key to determining the compression efficiency of an arithmetic encoder.
Table 2: Source symbols, their probabilities and initial encoding intervals.
Symbols |
00 |
01 |
10 |
11 |
Probabilities |
0.1 |
0.4 |
0.2 |
0.3 |
Initial Encoding Intervals |
[0,0.1] |
[0.1,0.5] |
[0.5,0.7] |
[0.7,1] |
Table 3: The encoding process of example. | |||
Step |
Input |
Encoding Interval |
Encoding Decision |
1 |
10 |
[0.5,0.7] |
The symbol range is [0.5,0.7] |
2 |
00 |
[0.5,0.52] |
The 1st 10th of [0.5,0.7] |
3 |
11 |
[0.514,0.52] |
The last 10ths of [0.5,0.52] |
4 |
00 |
[0.514,0.5146] |
The 1st 10th of [0.514,0.52] |
5 |
10 |
[0.5143,0.51442] |
Starting from the 5th 10th, two 10ths of [0.514,0.5146] |
6 |
11 |
[0.514384,0.51442] |
The last three 10ths of [0.5143,0.51442] |
7 |
01 |
[0.51439,0.5143948] |
Four 10ths of [0.514384,0.51442], starting from the 2nd 10th |
8 |
Choose a number from the interval [0.51439,0.5143948] as the output: 0.51439 |
Table 4: The decoding process of example | |||
Step |
Range |
Decoded |
Decoding Decision |
1 |
[0.5,0.7] |
10 |
0.51439 is in [0.5,0.7] |
2 |
[0.5,0.52] |
00 |
0.51439 is in the 1st 10th of the interval [0.5,0.7] |
3 |
[0.514,0.52] |
11 |
0.51439 is in the 7th 10th of the interval [0.5,0.52] |
4 |
[0.514,0.5146] |
00 |
0.51439 is in the 1st 10th of the interval [0.514,0.52] |
5 |
[0.5143,0.51442] |
10 |
0.51439 is in the 5th 10th of the interval [0.514,0.5146] |
6 |
[0.514384,0.51442] |
11 |
0.51439 in the 7th 10th of the interval [0.5143,0.51442] |
8 |
The decoded message is 10 00 11 00 10 11 01 |