Vector Quantization - Introduction to Data Compression - page 331

Set #1

Q 0,1 Q 1,1 Q 2,1 Q 3,1 Q 0,2 Q 1,2 Q 2,2 Q 3,2

Set #2

F I GU R E 10 . 28 Reconstruction levels for a 2-bit trellis-coded quantizer.

10.8 Trellis-Coded Quantization

Finally, we look at a quantization scheme that appears to be somewhat different from other
vector quantization schemes. In fact, some may argue that it is not a vector quantizer at all.
However, the trellis-coded quantization (TCQ) algorithm gets its performance advantage by
exploiting the statistical structure exploited by the lattice vector quantizer. Therefore, we can
argue that it should be classified as a vector quantizer.
The trellis-coded quantization algorithm was inspired by the appearance of a revolutionary
concept in modulation called trellis-coded modulation (TCM). The TCQ algorithm and its
entropy-constrained variants provide some of the best performance when encoding random
sources. This quantizer can be viewed as a vector quantizer with very large dimension, but a
restricted set of values for the components of the vectors.
Like a vector quantizer, the TCQ quantizes sequences of source outputs. Each element of a
sequence is quantized using 2 R reconstruction levels selected from a set of 2 R + 1 reconstruction
levels, where R is the number of bits per sample used by a trellis-coded quantizer. The 2 R
element subsets are predefined; which particular subset is used is based on the reconstruction
level used to quantize the previous quantizer input. However, the TCQ algorithm allows us to
postpone a decision on which reconstruction level to use until we can look at a sequence of
decisions. This way we can select the sequence of decisions that gives us the lowest amount
of average distortion.
Let's take the case of a 2-bit quantizer. As described above, this means that we will need 2 3 ,
or 8, reconstruction levels. Let's label these reconstruction levels as shown in Figure 10.28 .The
set of reconstruction levels is partitioned into two subsets: one consisting of the reconstruction
values labeled Q 0 , i and Q 2 , i , and the remainder comprising the second set. We use the first
set to perform the quantization if the previous quantization level was one labeled Q 0 , i or
Q 1 , i ; otherwise, we use the second set. Because the current reconstructed value defines the
subset that can be used to perform the quantization on the next input, sometimes it may be