Sampling and Quantization - Digital Speech: Coding for Low Bit Rate Communication Systems - page 46

v 3

y 1

v 1

y 2

v 4

y 3

y 4

v 5 y 5

v 2

y 6

v 6

y 7

y 8

Figure 3.11 Binary splitting into eight cells

2 B ,where B is an integer number of bits. Each region is associated
with a centroid. Figure 3.11 shows the division of space into L

of 2, L =

8 cells. At
the first binary division v 1 and v 2 are calculated as the centroids of the two
halves of the total space to be covered. At the second binary division four
centroids are calculated as v 3 to v 6 . The centroids of the regions after the
third binary division are the actual codebook vectors y i .Aninputvector x is
quantized, searching the tree along a path that gives the minimum distortion
at each node in the path. Again assuming N multiply-adds for each distortion
computation, the computation cost will be,

=

Com bs = 2 N log 2 L = 2 NB multiply − add per input vector (3.54)

At each stage, the input vector is compared against only two candidates.
This makes the computation cost a linear function of the number of bits in the
codewords.
The total storage cost, on the other hand, has gone up significantly,

M bs = 2 N(L − 1 ) locations (3.55)

or,

B

2 i M bs = N locations (3.56)

i = 1

A tree search codebook need not be a binary search codebook. In other
words the number of splitting stages may be less than the number of bits, B ,in
the codeword. In this case, each vector from the previous stage may point to
more than two vectors in the current stage. This can be seen as a compromise