Databases Reference
In-Depth Information
0
0
0
S
0
1
1
1
0
0
0
S
2
0
0
0
1
1
1
1
1
1
S
1
0
0
0
1
1
1
S
3
F I GU R E 10 . 31
Trellis diagram for the selection process with binary labels for the
state transitions.
The reconstruction levels associated with state
S
0
are
5 and 0.5. The closest value to 1.6
is 0.5. This results in an absolute difference for the second sample of 1.1. We can reach
S
0
from
S
0
and from
S
1
. If we accept the first sample reconstruction corresponding to
S
0
, we will
end up with an accumulated distortion of 1.4. If we accept the reconstruction corresponding
to state
S
1
, we get an accumula
t
ed distortion of 2.4. Since the accumulated distortion is less
if we accept the transition from state
S
0
, we do so and discard the transition from state
S
1
.
Continuing in this fashion for the remaining states, we end up with the situation depicted in
Figure
10.34
. The sequence of decisions that have been terminated are shown by an
X
on the
branch corresponding to the particular transition. The accumulated distortion is listed at each
node. Repeating this procedure for the third sample value of 2.3, we obtain the trellis shown
in Figure
10.35
. If we want to terminate the algorithm at this time, we can pick the sequence
of decisions with the smallest accumulated distortion. In this particular example, the sequence
would be
S
3
,
−
3
.
S
2
. The accumulated distortion is 1.0, which is less than what we would have
obtained using either Set #1 or Set #2.
S
1
,
10.9 Summary
In this chapter we introduced the technique of vector quantization. We have seen how we can
make use of the structure exhibited by groups, or vectors, of values to obtain compression.
Because there are different kinds of structure in different kinds of data, there are a number of
different ways to design vector quantizers. Because data from many sources, when viewed as
vectors, tend to form clusters, we can design quantizers that essentially consist of representa-
tions of these clusters. We also described aspects of the design of vector quantizers and looked
Q
0,1
Q
1,1
Q
2,1
Q
3,1
Q
0,2
Q
1,2
Q
2,2
Q
3,2
−3.5
−2.5
−1.5
− 0.5
0.5
1.5
2.5
3.5
F I GU R E 10 . 32
Reconstruction levels for a 2-bit trellis-coded quantizer.
