Databases Reference
In-Depth Information
advantageous to actually accept more distortion than necessary for the current sample in order
to have less distortion in the next quantization step. In fact, at times it may be advantageous
to accept poor quantization for several samples so that several samples down the line the
quantization can result in less distortion. If you have followed this reasoning, you can see how
we might be able to get lower overall distortion by looking at the quantization of an entire
sequence of source outputs. The problemwith delaying a decision is that the number of choices
increases exponentially with each sample. In the 2-bit example, for the first sample we have
four choices; for each of these four choices we have four choices for the second sample. For
each of these 16 choices we have four choices for the third sample, and so on. Luckily, there
is a technique that can be used to keep this explosive growth of choices under control. The
technique, called the
Viterbi algorithm
[
166
], is widely used in error control coding.
In order to explain how the Viterbi algorithm works, we will need to formalize some of
what we have been discussing. The sequence of choices can be viewed in terms of a state
diagram. Let's suppose we have four states:
S
0
,
S
2
, and
S
3
. We will say we are in state
S
k
if we use the reconstruction levels
Q
k
,
1
or
Q
k
,
2
. Thus, if we use the reconstruction levels
Q
0
,
i
,
we are in state
S
0
. We have said that we use the elements of Set #1 if the previous quantization
levels were
Q
0
,
i
or
Q
1
,
i
. As Set #1 consists of the quantization levels
Q
0
,
i
and
Q
2
,
i
,this
means that we can go from state
S
0
and
S
1
to states
S
0
and
S
2
. Similarly, from states
S
2
and
S
3
we can only go to states
S
1
and
S
3
. The state diagram can be drawn as shown in Figure
10.29
.
Let's suppose we go through two sequences of choices that converge to the same state, after
which both sequences are identical. This means that the sequence of choices that had incurred
a higher distortion at the time the two sequences converged will have a higher distortion from
then on. In the end we will select the sequence of choices that results in the lowest distortion;
therefore, there is no point in continuing to keep track of a sequence that we will discard
anyway. This means that whenever two sequences of choices converge, we can discard one
of them. How often does this happen? In order to see this, let's introduce time into our
state diagram. The state diagram with the element of time introduced into it is called a
trellis
diagram
. The trellis for this particular example is shown in Figure
10.30
. At each time instant,
we can go from one state to two other states. And, at each step we have two sequences that
converge to each state. If we discard one of the two sequences that converge to each state, we
can see that, no matter how long a sequence of decisions we use, we will always end up with
four sequences.
Notice that, assuming the initial state is known to the decoder, any path through this
particular trellis can be described to the decoder using 1 bit per sample. From each state we
can only go to two other states. In Figure
10.31
, we have marked the branches with the bits
used to signal that transition. Given that each state corresponds to two quantization levels,
specifying the quantization level for each sample would require an additional bit, resulting in
a total of 2 bits per sample. Let's see how all this works together in an example.
S
1
,
Example10.8.1:
Using the quantizer whose quantization levels are shown in Figure
10.32
, we will quantize the
sequence of values 0.2, 1.6, 2.3. For the distortion measure we will use the sum of absolute
differences. If we simply used the quantization levels marked as Set #1 in Figure
10.28
,we
would quantize 0.2 to the reconstruction value 0.5, for a distortion of 0.3. The second sample
