Efficient codebook search for CELP vocoders

• US 5,187,745 A
• Filed: 06/27/1991
• Issued: 02/16/1993
• Est. Priority Date: 06/27/1991
• Status: Expired due to Term

• Current Assignee: General Dynamics C4 Systems Incorporated (General Dynamics Corporation)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Barron, David L., Yip, William C.
• Primary Examiner(s): KEMENY, EMANUEL
• Application Number:
  US07/722,572
• Time in Patent Office: 600 Days
• Field of Search: 381/29-40
• US Class Current: 704/219
• CPC Class Codes: G10L 19/12 the excitation function being a code excitation, e.g. in code excited linear prediction [CELP] vocoders
• CPC Class Codes: G10L 2019/0002 Codebook adaptations
• CPC Class Codes: G10L 2019/0014 Selection criteria for distances
• CPC Class Codes: G10L 25/06 the extracted parameters being correlation coefficients
• CPC Class Codes: G10L 25/18 the extracted parameters being spectral information of each sub-band

Abstract

A new way of determining correlation coefficients for stochastic codebook vectors for CELP coding of speech takes advantage of the sparsely populated nature of stochastic codebook vectors. N valued input signals (e.g., convolution vectors) to be correlated with N valued codebook vectors are fed to an N by N multiplexer or other selection means and the signal values either passed to an accumulator or not according to the state of N select inputs or other identification means determined from a memory store (e.g., an EPROM) whose entries correspond to the non-zero values of the codebook vectors. The accumulator output is the correlation of the codebook vector with the input signal. A sequencer steps through the entire codebook to provide correlation values for each vectors. The results are used to determine the optimum stochastic codebook vector for replicating the particular speech frame being analyzed.

Claims

1. A method for CELP coding speech by combining a first vector with a set of second vectors identified by index k, wherein the first and second vectors have values identified by indices n running from n=1 to N, comprising:

providing an N by N multiplexer having n=1 to N outputs, n=1 to N first inputs, second inputs, and n=1 to N select means, wherein a first logic level presented to n^th select means couples the n^th output to the n^th first input and a second logic level presented to the n^th select means couples the n^th output to the second input;

supplying n=1 to N values of the first vector to the n=1 to N first inputs of the multiplexer;

presenting n=1 to N values of the second vector of index k=1 to n=1 to N select means of the multiplexer, the second vector providing at the n=1 to N select means the first logic level for some values of n and the second logic level for other values of n;

adding together values of the first vector coupled to the multiplexer output to provide a sum;

repeating the presenting and adding steps for further values of k; and

synthesizing speech based on whichever sum identifies a second vector giving the closest match to target speech.

2. The method of claim 1 further comprising determining which vector k=j has the largest sum.

3. The method of claim 1 wherein the supplying, presenting and adding steps are repeated for other first vectors.

4. A method for CELP coding speech by combining a first vector with a set of second vectors identified by index k, wherein the first and second vectors have values identified by indices n running from n=1 to N, comprising:

dividing each second vector into two portion, a first portion having values 0, +1 corresponding to the location of values of 0, +1 of the second vector and a second portion having values 0, +1 corresponding to the location of values 0, -1 of the second vector, comprising;

providing first and second N by N multiplexers each having n=1 to N outputs, n=1 to N first inputs, second inputs, and n=1 to N select means, wherein a first logic level presented to n^th select means couples the n^th output to the n^th first input and a second logic level presented to the n^th select means couples the n^th output to the second input;

supplying n=1 to N values of the first vector to the n=1 to N first inputs of the first and second multiplexers;

presenting n=1 to N values of the k=1 first portion of the second vector to n=1 to N select means of the first multiplexer and presenting the n=1 to N values of the k=1 second portion of the second vector to n=1 to N select means of the second multiplexer;

adding together values of the first vector coupled to the output of the first multiplexer to provide a first sum and adding together values of the first vector at the output of the second multiplexer to provide a second sum;

combining the first and second sums to provide a result;

repeating the presenting, adding and combining steps for further values of k; and

synthesizing speech based on whichever result identifies a second vector giving the closest match to target speech.

5. The method of claim 4 further comprising comparing the results for each value of k to determine the value of k having the largest result.

6. The method of claim 4 wherein the supplying, presenting, adding and combining steps are repeated for other first vectors.

7. An apparatus for CELP coding speech by combining a first vector with a set of second vectors identified by an index k, wherein the first and second vectors have values identified by indices n running from n=1 to N, comprising:

an N by N multiplexer having n=1 to N outputs, n=1 to N first inputs, second inputs, and n=1 to N select means, wherein a first logic level presented to n^th select means couples the n^th output to the n^th first input and a second logic level presented to the n^th select means couples the n^th output to the second input;

means for supplying n=1 to N values of the first vector to the n=1 to N first inputs of the multiplexer;

means for presenting n=1 to N values of the second vector of index k=1 to the n=1 to N select means of the multiplexer, the second vector providing at the n=1 to N select means the first logic level for some values of n and the second logic level for other values of n;

means coupled to the multiplexer output for adding together values of the first vector transferred to the outputs of the multiplexer to provide a sum;

means for indexing k from k=1 to k=K; and

means for synthesizing speech based on whichever sum identifies a second vector giving the closest match to target speech.

8. The apparatus of claim 7 further comprising means for determining which vector k=j has the largest sum.

9. The apparatus of claim 7 further comprising means for supplying other first vectors.

10. An apparatus for CELP coding speech by combining a first vector with a set of second vectors identified by index k and having values identified by indices n=1 to N, comprising:

memory means for storing first portions of the second vectors, and having values 0, +1 corresponding to the locations of values 0, +1 of the second vectors;

memory means for storing second portions of the second vectors, and having values 0, +1 corresponding to the locations of values 0, -1 of the second vectors, comprising;

first and second N by N multiplexers each having n=1 to N outputs, n=1 to N first inputs, second inputs, and n=1 to N select means, wherein a +1 presented to n^th select means couples the n^th output to the n^th first input and a 0 presented to the n^th select means couples the n^th output to the second input, the first multiplexer coupled to the first memory means and the second multiplexer coupled to the second memory means;

means for supplying n=1 to N values of the first vector to the n=1 to N first inputs of the first and second multiplexers;

means for presenting n=1 to N values of the k=1 first portion of the second vector to n=1 to N select means of the first multiplexer;

means for presenting the n=1 to N values of the k=1 second portion of the second vector to n=1 to N select means of the second multiplexer;

first adder coupled to the outputs of the first multiplexer for summing values of the first vector appearing at outputs of the first multiplexer to produce a first sum;

second adder coupled to the outputs of the second multiplexer for summing values of the first vector appearing at outputs of the second multiplexer to produce a second sum;

means for combining the first and second sums to produce a result;

means for indexing k to load first and second portions of other second vectors into the memory means and for multiplexing, adding and combining to produce other results; and

means for synthesizing speech based on whichever result identifies a second vector giving the closest match to target speech.

11. The apparatus of claim 10 further comprising means for comparing the results for each value of k to determine the value of k having the largest result.

12. The apparatus of claim 10 further comprising means for providing other first vectors.

13. A method for CELP coding speech using a combination of a first vector V(n) having values identified by index n running from n=1 to N, and a set of the second vectors S_k (n) wherein each of the second vectors is identified by index k and wherein each of the second vectors has up to N values which are either zero or non-zero and are identified by index n from n=1 to N, comprising:

identifying indices n_k,i of S_k (n) for different k wherein S_k (n_i) are non-zero;

adding values of the V(n) corresponding to indices n_k,i to form sums Q(k);

identifying the value k=j corresponding to the largest value Q(k=j); and

synthesizing.speech using S_k =j(n).

14. The method of claim 13 wherein successive vectors of the set of second vectors are determined by overlap of the preceding second vector according to an overlap amount Δ

k,Δ

n, wherein the identifying and adding steps comprise;

identifying for k=1 indices n₁,i of S_k (n) wherein S₁ (n_i) are non-zero;

starting from n₁,i and using the overlap amount Δ

k,Δ

n, determining further indices n_k,i'"'"' for k>

1 wherein S_k (n_i'"'"') are non-zero; and

adding values of the V(n) for such indices and further indices to form sums Q(k).

15. The method of claim 14 further comprising identifying for k≧

2, a first index n_k,i" not previously identified wherein S_k (n_i") is non-zero, and then, starting from index n_k,i" determining still further indices n_k,i"'"'"' for k≧

3 wherein S_k (n_i"'"'"') are non-zero using the overlap amount, and adding values of v(n) for such still further indices to further form sums Q(k).

16. An apparatus for CELP coding speech using a combination of a first vector V(n) having values identified by index n running from n=1 to N, and a set of the second vectors S_k (n) wherein each of the second vectors is identified by index k and wherein each of the second vectors has up to N values which are either zero or non-zero and are identified by index n from n=1 to N, comprising:

means for identifying indices n_k,i of S_k (n) for different k wherein S_k (n_i) are non-zero;

means for adding values of the V(n) corresponding to indices n_k,i to form sums Q(k);

means for identifying the value k=j corresponding to the largest value Q(k=j); and

means for synthesizing.speech using S_k =j(n).

17. The apparatus of claim 16 wherein successive vectors of the set of second vectors are determined by overlap of the preceding second vector according to an overlap amount Δ

k,Δ

n, wherein the means for identifying and adding comprise;

means for identifying for k=1 indices n₁,i of S_k (n) wherein S₁ (n_i) are non-zero;

means for determining further indices n_k,i'"'"' for k>

1 wherein S_k (n_i) are non-zero, starting from n₁,i and using the overlap amount Δ

k,Δ

n; and

means for adding values of the V(n) for such indices and further indices to form sums Q(k).

18. The apparatus of claim 17 wherein the means for identifying, determining and adding comprise, means for identifying for k≧

2, a first index n_k,i" not previously identified wherein S_k (n_i") is non-zero, means for determining still further indices n_k,i"'"'"' for k≧

3 wherein S_k (n_i"'"'"') are non-zero starting from index n_k,i" and using the overlap amount, and means for adding values of V(n) for such still further indices to further form sums Q(k).