Databases Reference
In-Depth Information
where the superscript indicates whether the previous pixel was a 0 or a 1. We will always
assume that for each row there is an imaginary white pixel to the left of the leftmost pixel.
Therefore, we will always begin our encoding using the
Cum
_
Count
0
array. After encoding
the first pixel all other pixels will be encoded using the
Cum_Count
array corresponding to the
previous pixel. Assume we wish to encode the sequence
000000111111
Notice that the marginal probabilities of 1 and 0 are 1/2 so if we used an arithmetic coder that
did not take the context into account we would end up with a 1 bit/pixel encoding. Using the
conditional probability tables we hope to do better. We will use a word length
m
of six:
l
(
0
)
=
0
=
(
000000
)
2
(56)
u
(
0
)
=
63
=
(
111111
)
2
(57)
The first bit to be encoded is 0:
64
64
Cum
_
Count
0
×
(
−
1
)
×
0
l
(
1
)
=
0
+
=
=
0
10
10
=
(
000000
)
2
64
64
Cum
_
Count
0
×
(
0
)
×
8
u
(
1
)
=
0
+
−
1
=
−
1
=
50
10
10
)
2
The second bit to be encoded is also 0:
=
(
110010
51
51
Cum
_
Count
0
×
(
−
1
)
×
0
l
(
2
)
=
+
=
=
0
0
10
10
=
(
000000
)
2
51
51
Cum
_
Count
0
×
(
0
)
×
8
u
(
2
)
=
0
+
−
1
=
−
1
=
39
10
10
)
2
The third bit to be encoded is also 0:
=
(
100111
40
40
Cum
_
Count
0
×
(
−
)
×
1
0
l
(
3
)
=
+
=
=
0
0
10
10
=
(
0
00000
)
2
40
40
Cum
_
Count
0
×
(
0
)
×
8
u
(
3
)
=
0
+
−
1
=
−
1
=
31
10
10
)
2
The MSBs of
l
(
3
)
and
u
(
3
)
are both 0. Therefore, we shift this value out and send it to the
decoder. All other bits are shifted to the left and we get
l
(
3
)
=
(
=
(
0
11111
000000
)
2
=
0
u
(
3
)
=
(
111111
)
2
=
63
