AN2121 Freescale Semiconductor / Motorola, AN2121 Datasheet - Page 12

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

Background Theory
In binary fraction format,
Therefore, any fraction received at the decoder between the interval of 420/512 and 421/512 will represent
the sequence of transmitted symbols
In general, it turns out that it is only necessary to transmit the most significant –log
fractional representation of C
the value of C
there are –log
This shows that in the example, the average code rate for four symbols is higher than the entropy lower
bound. However, as n tends to infinity, the average number of bits per symbol does converge to the
entropy. This is because
where the E[x] operator denotes the expectation of x.
Again, this example is only intended to show the relationship between entropy and Huffman coding.
Arithmetic encoding can be equally effective with symbols whose probabilities are not rational fractions of
2
2.3
In binary arithmetic coding (BAC), symbols in a code stream are classified as either Most Probable
Symbol (MPS) or Least Probable Symbol (LPS). The interval A (see Figure 2 on page 5) has two
divisions, one each for MPS and LPS.The width of each division is determined by the probability for each
symbol. The interval associated with the LPS should always be less than that associated with the MPS. The
events received by the encoder can either be MPS:True (‘T’) or MPS:False (‘F’).
The JPEG2000 literature has adopted the convention of referring to the probability for the LPS as Q
the corresponding probability for the MPS is (1 – Q
denoted by P
Figure 5 illustrates the BAC process. In this example, the message ‘TFTT’ is coded where T denotes the
MPS and F the LPS (MPS:False). The probabilities are Q
two non-overlapping subintervals. The convention adopted here is that the Q
the P
fractional and binary fraction format. When a symbol occurs, the subinterval associated with that symbol
becomes the new interval. For example, the initial interval [0, 1) has two subintervals [0, 0.01) and
[0.01, 1) associated with ‘F and ‘T’ respectively. When ‘T’ occurs, the subinterval [0.01, 1.0) becomes the
new interval. The code word C in this example always points to the left point (lower bound) of the interval
and A denotes its width.
8
i
where i is an integer.
e
subinterval. As before, the initial interval is [0, 1). Again, the notation has been given in both
A
C
A
4
4
4
= 0.1011001
= A
= 0.000001
=
Binary Arithmetic Coding
e
2
64
.
n
1
A
3
+ A
n
bits representing n symbols, then the average code rate is
(
1
8
n
f
–log
X
regardless of the number of 1s concatenated to C
=
(
e
n
JPEG2000 Arithmetic Encoding on the StarCore SC140
512
)
2
1
0.01 = 0.00000001
A
Freescale Semiconductor, Inc.
=
n
For More Information On This Product,
to uniquely define the encoded interval. This is because C
i = 1
n
log
code
n
–log
2
Go to: www.freescale.com
f
X
.
(x
n
2
i
A
)
n
n
=
9
4
e
). In this document, the probability for the MPS is
= 2.25
–E[log
e
= ¼ and P
2
f
X
(X)] = H(X)
e
n
= 1 – Q
in the decoder. In the example, if
e
e
subinterval always precedes
= ¾ and are represented as
2
A
n
bits in the binary
n
will never reach
Eqn. 6
Eqn. 7
e
and