AN2121 Freescale Semiconductor / Motorola, AN2121 Datasheet - Page 7

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

It is evident in the final step that the code words are not unique; however, the length of the code word
associated with each symbol is always the same.
Table 1 lists the code words obtained from the example in Figure 1, as well as the probability for each
symbol expressed as a binary fraction. In binary fractions, 0.1 represent 2
other words, the exponent associated with the negative power of two is equal to the number of places after
the binary point.
•
•
Iterate the first two steps until the symbols are arranged in a binary tree in which only two branches
extend from each root.
Assign ‘1’ to one branch from each root, and ‘0’ to the other branch to obtain the code words. In the
example, the left-hand branches are all 1’s, and the right-hand branches are 0’s.
Figure 1. Binary Tree for Huffman Coding Example
Freescale Semiconductor, Inc.
For More Information On This Product,
Table 1. Example of Huffman Coding
o (1/8)
Symbol
o (1/8)
1
c
d
e
o
Go to: www.freescale.com
o (1/8)
oe (1/4)
Background Theory
1
e (1/8)
0
e (1/8)
oe (2/8)
oed (1/2)
Probability
(in Binary)
0.001
0.001
0.01
1
0.1
e (1/8)
d (1/8)
0
d (1/4)
d (1/4)
c (1/2)
0
Code Word
110
111
10
0
c (1/2)
c (1/2)
-1
, 0.01 represents 2
Huffman Coding
-2
, etc. In
3