AN2121 Freescale Semiconductor / Motorola, AN2121 Datasheet - Page 9

• Manufacturer Part Number: AN2121
• Description: JPEG2000 Arithmetic Encoding on StarCore SC140
• Manufacturer: Freescale Semiconductor / Motorola

Whereas Huffman coding involves transmitting separate code words for each symbol in a sequence,
arithmetic coding requires transmitting only the information needed to allow a decoder to determine the
particular fractional interval between 0 and 1 to which the sequence is mapped. This information includes
a fractional code word, C, which points to the lower bound of the interval, and the interval width, A, as
illustrated in Figure 2.
Each time a new symbol is received by the encoder, a smaller interval is chosen within the current interval.
This interval represents the whole sequence of symbols up to and including the new symbol. The length of
the updated interval is the probability associated with this sequence of symbols, as shown in Figure 3. The
position of the probability interval associated with a particular symbol is always fixed in relation to the
intervals of the other symbols. (Note that in arithmetic encoding, the position of the fractional interval is as
important as the length.) In theory, this process can continue indefinitely until all symbols have been
received. In practice, finite precision problems restrict the size of the shortest possible interval that can be
represented. When the length of the probability interval falls below a certain minimum size, the interval
must be renormalized to lengthen it above the minimum. The renormalization process is explained in more
detail in Section 2.4.4 on page 14.
Figure 4 illustrates how arithmetic coding is used to derive the fractional numbers which represent the
position and width of the interval on [0,1) which can be decoded as the sequence
the same symbol set and probabilities as in the previous example (see Table 1 on page 3). The top line in
the diagram is the [0,1) interval. This line is subdivided into smaller intervals whose widths are directly
0
0
0
0
The convention for expressing an interval employed in this discussion uses
a bracket for an inclusive bound, and a parenthesis for an exclusive bound.
Thus, [0,1) represents a range including zero but not including 1.
Final probability interval =
codestream {x1, x2, x3}
probability of receiving
Figure 2. Mapping a Sequence to a Fractional Interval
Freescale Semiconductor, Inc.
For More Information On This Product,
C
Figure 3. Arithmetic Coding Process
A
Interval associated with
Go to: www.freescale.com
Background Theory
symbol x1
NOTE:
symbol stream {x1,x2,x3}
Interval associated with
Interval associated with
symbol stream {x1,x2}
Interval length =
probability of x1
code
. This example uses
Arithmetic Coding
1
1
1
1
5