AN2121 Freescale Semiconductor / Motorola, AN2121 Datasheet - Page 6

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

Background Theory
2
This section presents a look at some of the theory behind symbol coding, including the well-known
Huffman coder, general arithmetic coding, and binary arithmetic coding, which is employed by the
JPEG2000 standard.
Arithmetic coding is a form of statistical coding, which compresses data by encoding more probable
symbols with shorter code words than less probable symbols. The ideas behind compressing the
information associated with a sequence of random variables in order to transmit them over a
communication link can be traced back to Shannon’s ground breaking 1948 paper [2], in which he defined
the entropy of a random variable, X, with a discrete alphabet, e.g. {x
where
much information it holds. As an extreme example, when it is known in advance that one particular symbol
will be received, e.g. an a, then its probability is 1 and its entropy is 0 because it holds no new information.
At the other extreme, if all the symbols in a particular alphabet are equally likely, then this will give
maximum entropy because each new received symbol is totally unpredictable. Shannon also proved that
for a stationary process, entropy is equal to the minimum average number of bits per symbol required to
represent the information source. The significance of arithmetic coding is that it can be made to approach
this theoretical limit.
As an introduction to arithmetic encoding, let us examine the simpler approach of Huffman coding, which
is used in the baseline JPEG standard.
2.1
One way of coding symbols in an information stream is to allocate a unique code word for each symbol.
One such coding scheme, Huffman coding, is a form of prefix coding, meaning that each prefix in a given
set of code words is unique. This fact simplifies the decoding process because the decoder simply
continues to receive binary digits until a new code word has been obtained.
2.1.1
The significance of the Huffman coder is that it uses an algorithm which ensures that
is minimized, where l
explain the algorithm. Consider an alphabet which consists of four possible symbols, {
respective probabilities of 1/2, 1/4, 1/8, and 1/8. The encoding algorithm, illustrated in Figure 1, consists of
the following steps:
2
•
•
f
X
Sort the symbols from least probable symbol to most probable symbol.
Group the two least probable symbols together to form a root to the two separate symbols, which
become the leaves.
(x
i
) is the probability that x
Background Theory
Huffman Coding
The Huffman Coding Algorithm
The following discussions assume that a perfect communication channel is
present so that there are no errors associated with the code stream.
i
is the length of the code word associated with x
JPEG2000 Arithmetic Encoding on the StarCore SC140
Freescale Semiconductor, Inc.
For More Information On This Product,
H(X) = –
i
occurs. The entropy of a random variable can be thought of as how
Go to: www.freescale.com
i = 0
i = 0
n
n
f
f
X
X
NOTE:
(x
(x
i
i
)l
)log
i
2
f
X
(x
i
)
0
, x
i
. A simple example can serve to
1
, . . ., x
n
} as:
c
,
d
,
e
,
o
}, with
Eqn. 1
Eqn. 2