Vector quantizer with first quantization using input and base vectors and second quantization using input vector and first quantization output

A first vector quantizer generates output codevectors corresponding in number to a number determined by a predetermined number of bits through linear coupling of integer coefficients of a predetermined number of base vectors stored in a base vector memory. A second vector quantizer determines coefficients of the base vectors according to at least one of output indexes of the output codevectors.

BACKGROUND OF THE INVENTION 
The present invention relates to a vector quantizer and, more particularly, 
to a vector quantizer for low bit rate coding time-sequential signals such 
as speech signals and image signals. 
Vector quantization is a typical method of quantizing time-series signals 
such as speech signals and image signals by dividing the input signal into 
a plurality of frames with a predetermined interval (or blocks with a 
predetermined area). The vector quantization is excellent in the 
quantization performance in the sense that this method can reduce the 
quantizing distortion with respect to the number of assigned bits. This 
method, however, requires great deals of computational effort and storage 
capacity for the retrieval of an optimum quantization output vector which 
best represents the quantization signal. 
For example, in vector quantization with 0.5 bit per sample and 40 vector 
dimensions, the computational effort (i.e., number of AND/ORing times) and 
storage capacity for the retrieval are 40.times.20.sup.2 per vector. This 
means that where a speech signal of 8 Khz sampling is dealt with, the 
computational effort is a little higher than about 1660.times.10.sup.6 per 
second. This operational scale is impossible with a single chip of DSP 
(Digital Signal Processor). 
In the case of possible application of a plurality of high bit rate DSPs in 
parallel, increases of the price, power consumption, installation area, 
etc. are inevitable, thus disabling the application of the method to 
portable terminals or the like. 
Various methods for executing vector quantization with less computational 
scales have heretofore been investigated. A basic method for the 
computational scale reduction is "structuring", in which some restrictions 
are provided among codevectors constituting a vector quantizer. 
A typical method of structuring is vector sum quantization, which is 
disclosed in Japanese Patent Laid-Open Heisei 2-502135. Among other 
typical methods of structuring is lattice vector quantization as shown in, 
for instance, J. H. Conway and N. J. A. Sloane, "First Quantizing and 
Decoding Algorithms for Lattice Quantizers and Codes", IEEE Trans. Inf. 
Theory, Vol. IT-28, pp. 227-232, 1982, and R. M. Gray Source Coding 
Theory, Ch. 5.5, Kluwer Academic Publishers, 1990. 
These vector quantizers feature in generation of codevectors by arithmetic 
operations of predetermined base vectors with or without multiplification 
by an integer. Specifically, denoting M base vectors by{a.sub.i, i=1, . . 
. ,M}, a k-th codebook is given as: 
##EQU1## 
where {u.sub.ki } is integers. In the vector sum quantization, the 
coefficient u.sub.ki take as values of "1" or "-1", and 2.sup.M vectors 
are generated. 
In such a vector quantization, the computational effort can be greatly 
reduced by providing appropriate contrivances with respect to the 
character of the arithmetic operations and the retrieval sequence so long 
as the number M of the base vectors is considerably small compared to the 
number L of the vector dimensions. For example, the computational effort 
in the vector quantization is reduced by providing the following 
contrivance in the retrieval step. 
Denoting an n-th frame input vector by x.sub.n, base vectors by {a.sub.i, 
i=1, . . . ,M}, the coefficient vector of a k-th codevector by {u.sub.ki, 
i=1, . . . ,M}, a k-th codebook is retrieved by using an evaluating 
function J.sub.k given as: 
##EQU2## 
where t attached to ai indicates transposition. 
It is assumed that u.sub.ki is "1" when an i-th bit is "0" for k expressed 
by the binary expression and "-1" when the i-th bit is "1" and that 
EQU u.sub.(k+1)i =-u.sub.ki and 
EQU u.sub.(k+1)j =u.sub.kj (j.noteq.i). 
Then, J.sub.k and (k+1)-th evaluating function J.sub.k+1 are related as: 
##EQU3## 
By setting L as the vector dimension number, the computational effort 
(number of AND/ORing times) C.sub.vsum that is required for the retrieval 
in this case is: 
EQU C.sub.vsum =L+ML+(1/2)M(M+1)L+(2.sup.M-1 -1) +M(2.sup.M-1 -1) (4) 
The AND/ORing times number C.sub.norm that is necessary for the usual 
vector quantizer is 
EQU C.sub.norm =L2.sup.M. 
Thus, if 
EQU M&lt;&lt;L, 
we have 
EQU C.sub.vsum &lt;&lt;C.sub.norm. 
The above prior art quantizing systems such as the vector sum quantizing 
system and the lattice vector quantizing system, feature in that the 
computational effort for the codevector retrieval can be greatly reduced. 
In these vector quantizing systems, however, codevectors are generated by 
arithmetic operations of base vectors with or without multiplification by 
an integer. Therefore, the codevector generation is greatly restricted, 
and the quantizers are greatly inferior in performance to non-structured 
vector quantizers. 
For example, it was reported that with respect to speech signals the vector 
sum quantization is inferior in performance by 2 dB or more at 8 kb/s to 
the non-structured vector quantization (LeBlanc, W. P and Mahmound, S. A., 
"Structured Codebook Design in CELP", Proc. International Mobile Satellite 
Conference, p. 667-672, 1991). 
SUMMARY OF THE INVENTION 
An object of the present invention is therefore to provide a vector 
quantizer, which requires less performance while being high in 
performance. 
According to the present invention, there is provided a vector quantizer 
having a memory with a plurality of base vectors stored therein, for 
forming an output codevector through linear coupling of integer 
coefficients of the stored base vectors and generating an output 
codevector with a predetermined number of bits from a combination of the 
integer coefficients corresponding to an index, the vector quantizer 
comprising: a first vector quantizing means for selecting at least one of 
integer coefficient combinations or index combinations on the basis of an 
evaluation reference determined by a predetermined procedure by using an 
input vector and the plurality of base vectors; and a second vector 
quantizing means for selecting a desired coefficient vector from the 
integer coefficients of the plurality of base vectors on the basis of the 
evaluating reference by using the output of the first vector quantizing 
means and the input vector. 
The first vector quantizing means includes means for generating a 
codevector from the base vectors and the indexes, means for calculating an 
evaluation function from the generated codevector and the input vector on 
the basis of the evaluation reference, and means for selecting and 
outputting a combination of a predetermined number of indexes in the order 
of smaller calculated evaluation functions. 
The second vector quantizing means includes means for executing the 
codevector selection according to each of the indexes in the index 
combination outputted from the first vector quantizer, means for 
generating an output codevector from the selected coefficient codevector 
and the plurality of base vectors, means for calculating the difference 
between the generated output codevector and the input vector, and means 
for selecting and outputting an index giving a minimum error as the 
calculated error. 
The vector quantizer further comprises means for calculating the impulse 
response or the like of a linear prediction synthesis filter, for which 
linear prediction coefficients based on liner prediction is provided 
through linear prediction analysis of the input vector. 
In the present invention, the computational effort is reduced by the 
provision of a first vector quantizer for generating a number of output 
codevectors as determined by a predetermined bit number through linear 
coupling of integer coefficients of a predetermined number of base 
vectors, and a second vector quantizer for determining the coefficients of 
the base vectors according to at least one output index provided from the 
first vector quantizer. 
Other objects and features will be clarified from the following description 
with reference to attached drawings.

PREFERRED EMBODIMENTS OF THE INVENTION 
Embodiments of the present invention will now be described with reference 
to the drawings. 
FIG. 1 is a block diagram showing an embodiment of the present invention. 
Referring to the figure, the embodiment of the vector quantizer according 
to the present invention comprises a buffer memory 3 for storing input 
vectors supplied from an input terminal 5, a first and a second vector 
quantizers 1 and 2, and a base vector memory 4 with a plurality of base 
vectors stored therein. 
The first vector quantizer 1 adopts the vector sum quantizing system. 
Hereinafter, it is assumed that the number of vector dimensions is L, the 
quantizing bit number per vector is M, and the output codevector number is 
.sub.2.sup.M. 
Referring to FIG. 1, an input vector X.sub.n supplied from the input 
terminal 5 is fed to the buffer memory 3 and thence to an error calculator 
11. In the base vector memory 4, M predetermined base vectors {a.sub.i, 
i=1, . . . ,M} are stored. 
A codevector generator 12 receives a base vector from the base vector 
memory 4 (step S21 in FIG. 2), generates an output codevector {v.sub.k } 
(step S23) based on an index k (of "0" to "2.sup.M -1") received from an 
index generator 13 (step S22). The output codevector v.sub.k is given by 
equation (1). 
An error calculator 11 receives the output codevector v.sub.k from the 
codevector generator 12 and an input vector X.sub.n (step S31 in FIG. 3), 
and according to these received data it calculates an evaluation function 
{J.sub.k, k=0, . . . ,2.sup.M-1 } using equation (3) and outputs the 
result of the calculation to an error sorter 14 (step S32). 
The error sorter 14 receives the evaluation function J.sub.k from the error 
sorter 11 (step S41 in FIG. 4), and then it selects B indexes {k.sub.b, 
b=1, . . . , B} in the order of smaller values and outputs these indexes 
to an index buffer 21 in the second vector quantizer 2 (step S42). 
A coefficient vector memory 22 receives each index k.sub.b from the index 
buffer 21 (step S51 in FIG. 5), and according to the received index it 
selects a coefficient vector z(k.sub.b), z(k.sub.b)=[z(k.sub.b).sub.1, . . 
. ,z(k.sub.b)M].sup.t and outputs the selected coefficient vector z(kb) to 
a codevector generator 23 (step S52). 
The codevector generator 23 generates codevectors. Specifically, it 
receives a base vector a.sub.i from the base vector memory 4, and from 
this base vector and the coefficient vector z(k.sub.b) received from the 
coefficient vector memory 32 (step S61 in FIG. 6) it calculates an output 
codevector v(k.sub.b) as: 
EQU v(k.sub.b)=.SIGMA.z(k.sub.b).sub.i a.sub.i (5) 
(step S62). 
The output codevector v(k.sub.b) calculated in this way is supplied to an 
error calculator 24. The error calculator 24 also receives an input vector 
from the buffer memory 3 (step S71 in FIG. 7), and calculates the error 
J(k.sub.b) between the two input vectors as: 
EQU J(k.sub.b)=.vertline.x.sub.n -v(k.sub.b).vertline..sup.2 (6) 
(step S72). 
An index output unit 25 receives the outputted error J(k.sub.b) (step S81 
in FIG. 8), and it selects an index k.sub.b which gives the minimum error 
as the error J(k.sub.b) and outputs the selected error from an output 
terminal 6. 
In the case where the number B of indexes outputted from the first vector 
quantizer 1 is "1", the process in the second vector quantizer 2 can be 
skipped. In this case, the output codevector is expressed as: 
EQU v(k.sub.b)=.SIGMA.z(k.sub.b).sub.i a.sub.i (7) 
A second embodiment will now be described with reference to drawings. In 
the first embodiment shown in FIG. 1, mean square error over the vector 
degree is used as a distance measure when calculating the error J.sub.k or 
J(k.sub.b) between the input vector and the output codevector. However, it 
is possible that the distance measure of the error calculation is 
dependent on the input vector characteristic. 
For example, denoting linear prediction coefficients that is determined as 
a result of a J-degree linear prediction analysis for the pertinent input 
vector or a plurality of input vectors including the pertinent input 
vector by {.alpha..sub.k (j), j=1, . . . ,J} and an impulse response of a 
linear prediction synthesizing filter having the coefficients as {h.sub.k 
(j), j=1, . . . ,L-1}, J.sub.k can be given as: 
EQU J.sub.k =.vertline.H.sub.k (x.sub.n -.SIGMA.u.sub.ki 
a.sub.i).vertline..sup.2 (8) 
where 
##EQU4## 
In this case, by preliminarily calculating H.sub.k x.sub.n, and {H.sub.k 
a.sub.i, i=1, . . . ,M} and making changes x.sub.n .rarw.H.sub.k X.sub.n 
and a.sub.i .rarw.H.sub.k a.sub.i, the procedure of calculation of J.sub.k 
is the same as equation (3). FIG. 9 shows an embodiment in this case. 
In this case, a weighting coefficient calculator 7 derives H.sub.k, a base 
vector weighter 9 calculates {H.sub.k a.sub.i }, and an input vector 
weighter 8 calculates H.sub.k x.sub.n. For the remainder of the 
constitution, the embodiment is the same as the first embodiment shown in 
FIG. 1. 
Referring to FIG. 9, the weighting coefficient calculator 7 executes an 
operation as shown in the flow chart of FIG. 10. Specifically, it executes 
linear prediction of an input vector in the buffer memory 3 (step S101), 
and derives an impulse response {h.sub.k (j)} of a linear prediction 
synthesizing filter having linear prediction coefficients {a.sub.i } that 
is determined as a result (step S102). 
The input vector weighter 8 executes an operation as shown in the flow 
chart shown in FIG. 11. Specifically, it reads out the input vector 
{x.sub.n } from the buffer memory 3 (step S111), receives the impulse 
response from the weighting coefficient calculator 7 (step S112), and 
calculates a weighted input vector H.sub.k x.sub.n (step S113). 
The base vector weighter 9 executes an operation as shown in the flow chart 
of FIG. 12. Specifically, it reads out a base vector from the base vector 
memory 4 (step S121), and calculates H.sub.k a.sub.i by using the impulse 
response received from the weighting coefficient calculator 7 (step S122). 
FIG. 13 shows an embodiment of the present invention applied to a speech 
coder. In the following description, it is assumed that the frame length 
is L.sub.frm, the sub-frame length is L.sub.sub, the sub-frame number is 
N.sub.sub, and the pertinent sub-frame index is n.sub.sub. 
Referring to the figure, the speech signal {x.sub.buf (n), n=0, . . . 
,L.sub.buf -1} of sample L.sub.buf (.gtoreq.L.sub.frm) supplied from an 
input terminal 600 is stored in a frame buffer 610. With {x.sub.buf } in 
the frame buffer 610, a linear prediction analyzer 640 derives an 
M.sub.lpc -degree linear prediction coefficient f{.alpha..sub.i, i=1, . . 
. ,M.sub.lpc } and a corresponding LSP parameter {lsp.sub.i, i=l, . . . 
,M.sub.lpc }, and outputs {a.sub.i } to weighting filters 660 and 661 and 
an impulse response calculator 680, while outputting {lsp.sub.i } to an 
LSP parameter quantizer 650. 
The linear prediction coefficient and the LSP parameters may be derived 
from the input speech signal in a well-known method as disclosed in, for 
instance, Sugamura and Itakura, "Speech Information Compression by Linear 
Spectrum Pair (LSP) Speech Analysis Synthesizing System", IECE Japan, 
Trans. J64-A, 8, pp. 599-606, 1981. 
An LSP parameter quantizer 650 quantizes LSP parameters supplied from the 
linear prediction analyzer 640, and outputs an index obtained as result of 
the quantization to an output terminal 602 and linear prediction 
coefficients {.alpha.i} corresponding to the quantization of the LSP to a 
synthesizing filter 670 and also to the impulse response calculator 680. 
It further outputs a normalized prediction error errnorm determined by a 
COR coefficient {par.sub.i } corresponding to the linear prediction 
coefficient to a gain retriever 710. 
The quantization of the LSP parameter may be executed by using a multiple 
stage method based on vector quantization and split vector quantization as 
proposed in, for instance, Ohya, Suda and Miki, "Pitch Synchronous 
Innovation CELP (PSI-CELP)", IECE Technical Report, RCS93078, pp. 63-70, 
1993. 
The normalized prediction error errnorm is obtained from {par.sub.i } 
usually by using: 
##EQU5## 
A mean power calculator 620 estimates mean power RO per frame of the input 
speech signal, and outputs the estimated mean power to a mean power 
quantizer 630. The mean power quantizer 630 quantizes RO, and outputs an 
index thereof from an output terminal 601, while outputting rms=.sqroot. 
(RO) to the gain retriever 710. 
A weighting filter 660 converts the input speech signal {x(n), n=0, . . . 
,L.sub.sub -1} of a pertinent sub-frame supplied from a frame buffer 610 
into a weighted input speech signal {x(n), n=0, . . . ,L.sub.sub -1}, and 
outputs the weighted input speech signal to a subtracter 725. Here, 
EQU x(n)=x.sub.buf (n.sub.sub .times.L.sub.sub +n) (11) 
and 
##EQU6## 
In the above equation, .gamma..sub.1 and .gamma..sub.2 are constants which 
are set such as to satisfy 0&lt;.gamma..sub.1 and .gamma..sub.2 &lt;1. 
The subtractor 725 subtracts the influence of the past sub-frame. 
Specifically, it calculates the past influence of the weighting filter 661 
and the synthesizing filter 670 as: 
##EQU7## 
and converts this past influence into 
##EQU8## 
Then, it outputs {x.sub.w } in the left side of the equation to an 
adaptive codebook retriever 690, a noise source retriever 700 and the gain 
retriever 710. 
An impulse response calculator 680 derives an impulse response of a cascade 
filter, which is formed by a synthesizing filter constituted by 
{.alpha..sub.i } supplied from an LSP parameter quantizer 650 and a 
weighting filter constituted by {.alpha..sub.i } supplied from a linear 
prediction analyzer 640. The impulse response is calculated as: 
##EQU9## 
and outputted to the adaptive codebook retriever 690, noise retriever 760 
and gain retriever 710. 
The adaptive codebook retriever 690 has a buffer memory for storing 
excitation signal determined in the past, and from the excitation signal 
in the buffer memory, quantized linear prediction coefficient 
{.alpha..sub.i } supplied from the LSP quantizer 650 and linear prediction 
coefficient {.alpha..sub.i } supplied from the linear prediction analyzer 
640 it derives a continuous excitation signal for L.sub.sub samples that 
best represents the weighted input speech signal {x.sub.w (n)} of the 
pertinent sub-frame and coefficients of that excitation signal. 
The excitation signal {V.sub.adp (n), n=0, . . . , L.sub.sub -1} for 
L.sub.sub samples is an adaptive codevector and is outputted together with 
its coefficient g.sub.adp to the noise source retriever 700. An index 
representing the relative position of the adaptive codevector in the 
buffer memory is outputted to the outside. 
The adaptive codevector may be derived by a well-known method, for instance 
described in Kroon, P. and Atal B. S., "Pitch Predictors with High 
Temporal Resolution", Proc. IEEE ICASSP, pp. 661-664, 1990, or in Kleijn, 
W. B., Krasinski D. J., and Ketchum R. H., "Improved Speech Quality and 
Efficient Vector Quantization", Proc. IEEE ICASSP, pp. 155-158, 1988. 
The noise source retriever 700 derives a noise source signal that best 
represents the weighted input speech signal {x.sub.w (n)} of the pertinent 
sub-frame on the basis of the quantized linear prediction coefficient 
{.alpha..sub.i } supplied from the LSP quantizer 650, linear prediction 
coefficient {.alpha..sub.i } supplied from the linear prediction analyzer 
60, adaptive codevector {V.sub.adp (n), n=0, . . . ,L.sub.sub -1} supplied 
from the adaptive codebook retriever 690 and the coefficients g.sub.adp 
thereof. 
The noise source retriever 700 includes at least a first vector quantizer, 
which has D (D&gt;1) base vectors and an integer coefficient vector codebook 
concerning the base vectors, and a second vector quantizer which has real 
number coefficient vectors corresponding to the base vectors. In the first 
vector quantization, the noise source signal {d.sub.k (n), k=0, . . . 
,2.sup.D -1, n=0, 1.sub.dots, L.sub.sub -1} is given as: 
##EQU10## 
where {u.sub.ki } is "1" or "-1". 
In the second vector quantization, d.sub.k (n) is given in terms of the 
real number coefficient codevectors {r.sub.ki, k=0, . . . ,2.sup.D -1, 
i=1, 1.sub.dots, D} as: 
##EQU11## 
In each vector quantization, the coefficient codevector retrieval reference 
is 
##EQU12## 
As mentioned before, in the first vector quantization the integer 
coefficients of the base vectors are such that 
EQU u.sub.(k+1)i =-u.sub.ki and 
EQU u.sub.(k+1)j =u.sub.ki, (j.noteq.i), 
and the evaluation function can be calculated progressively by using an 
equation: 
##EQU13## 
where E.sub.k.sup.d and E.sub.k.sup.n are 
EQU E.sub.k.sup.d =d.sub.k.sup.t H.sub.w t.sub.x 
EQU E.sub.k.sup.n =d.sub.k.sup.t H.sub.w.sup.t H.sub.w d.sub.k.sup.t (21) 
and S.sub.i and R.sub.mi are 
EQU S.sub.i =a.sub.i.sup.t t.sub.x 
EQU R.sub.mi =a.sub.m.sup.t H.sub.w.sup.t H.sub.w a.sub.m (22) 
In the first vector quantizer, Bcnd indexes {k.sub.b =1, . . . ,B.sub.cnd } 
are selectively outputted in the order of smaller values of {J.sub.k } 
calculated in the above way to the second vector quantizer. In the second 
vector quantizer, an index for minimizing 
##EQU14## 
is retrieved from real number coefficient vectors {k.sub.b } corresponding 
to the selected indexes {k.sub.b }. The retrieved index is 
##EQU15## 
The index of the noise source which minimizes equation (24) is outputted to 
an output terminal 605, and a noise source codevector d.sub.kb 
corresponding to that index is outputted to a gain retriever 710. By using 
the adaptive codevector V.sub.adp supplied from the adaptive codebook 
retriever 690, the noise source codevector d.sub.kp supplied from the 
noise source retriever 700 and the quantized linear prediction coefficient 
{.alpha..sub.i } supplied from the LSP quantizer 650, the gain retriever 
710 retrieves an adaptive codevector best representing the weighted input 
speech signal {x.sub.w (n)} of the pertinent sub-frame and a gain 
codevector as a coefficient of the noise source codevector d.sub.kp. 
The gain codevector is calculated such as to minimize 
EQU J.sub.m =-2(g.sub.m.sup.v v.sub.adp +g.sub.m.sup.d d.sub.k.sbsb.b).sup.t 
H.sub.w.sup.t x.sub.w +(g.sub.m.sup.v v.sub.adp +g.sub.m.sup.d 
d.sub.k.sbsb.b).sup.t H.sub.w.sup.t H.sub.w (g.sub.m.sup.v v.sub.adp 
+g.sub.m.sup.d d.sub.k.sbsb.b) (25) 
An index of the codevector for minimizing the above equation is outputted 
from an output terminal 604. The gain codevector that is actually stored 
in the gain codebook is, using errnorm supplied from the LSP quantizer 650 
and rms supplied from the mean power quantizer 630, 
##EQU16## 
The predetermined pertinent sub-frame excitation signal 
EQU e(n)=g.sub.m.sup.d v.sub.adp (n)+g.sub.m.sup.d d.sub.k.sbsb.b (n) (27) 
is used to update the excitation buffer memory in the adaptive codebook 
retriever. Also, a signal 
##EQU17## 
which is synthesized from the excitation signal {e(n)} is used to update 
memories in the synthesizing and weighting filters 670 and 661. 
When the above sub-frame routine is completed for one frame, the indexes 
which are outputted from the output terminals 601 to 605 are multiplexed 
and then sent to the decoding side. 
As has been described in the foregoing, the vector quantizer according to 
the present invention which forms output codevectors through linear 
coupling of a plurality of base vectors, adopts integer coefficients for 
the first vector quantization and adopts a second vector quantization with 
real number coefficients only for a small number (the least number being 
"1") of indexes outputted from the first vector quantizer. It is thus 
possible to obtain high performance vector quantization with little 
computational effort increase compared to the prior art vector 
quantization such as the vector sum vector quantization or lattice vector 
quantization. In the case where the number of indexes outputted from the 
first vector quantization is "1", the total computational effort is only 
that for the vector quantization. 
Changes in construction will occur to those skilled in the art and various 
apparently different modifications and embodiments may be made without 
departing from the scope of the present invention. The matter set forth in 
the foregoing description and accompanying drawings is offered by way of 
illustration only. It is therefore intended that the foregoing description 
be regarded as illustrative rather than limiting.