Efficient LPC Quantization Methods - Digital Speech: Coding for Low Bit Rate Communication Systems - page 111

5.7.3 SearchstrategiesforMSVQ
The usual search strategy for an SVQ codebook is straightforward: a full
search (FS) for each of the subvectors is applied. The structure of an MSVQ
quantizer, however, allows different types of search strategy depending on
the desired complexity. The simplest of the searches is the sequential search
(SS). In this search, the input vector f is first approximated by the i t 0 vector

from the first codebook Y 0 which minimizes:

p

w n f n − (y i 0 ) n 2

d( f , f ) =

(5.69)

n = 1

The index for the first codebook i 0 is then fixed and the quantization error
f y i 0

is then quantized using the i t 1 − vector from the second codebook Y 1

which minimizes:

p

w n ( f n (y i 1 ) n 2 (y i 0 ) n ) d( f , f ) = − − (5.70)

n = 1

This process is repeated for each stage in the codebook. The complexity of this
search is the sum of the complexity of a full search through each codebook,
given by,

K

2 B k

=

C N (5.71)

k = 1

where K is the number of stages, each with B k bits, and N is the length
of the input vector. This search is, however, nonoptimal as there is no
guarantee that the set of codebook vectors giving the lowest intermediate
distortion will also result in the best overall distortion. A better way to ensure
that the best performance is obtained is simply to perform a full search
on all codebooks jointly. That is, every combination of codebook vectors
ˆ

y i K − 1
K

y i 0 y i 1

1 is tested against the original input vector. This
guarantees optimal quantization, but at the cost of a very high complexity,
given by,

= + + ... +

x

−

N 2 k = 1 B k C = (5.72)

This complexity is equal to that of a direct vector quantization of the LSF,
which is far too high for practical applications. The only advantage of
the full-search MSVQ over a standard full search vector quantizer is the
reduced storage requirement. However, it is possible to obtain most of the