Method and apparatus for multiplexed vector quantization

• US 4,922,508 A
• Filed: 10/25/1988
• Issued: 05/01/1990
• Est. Priority Date: 10/30/1987
• Status: Expired due to Term

• Current Assignee: Nippon Telegraph and Telephone Corporation
• Original Assignee: Nippon Telegraph and Telephone Corporation
• Inventors: Moriya, Takehiro
• Primary Examiner(s): Safourek, Benedict V.
• Assistant Examiner(s): Chin, Stephen
• Application Number:
  US07/261,859
• Time in Patent Office: 553 Days
• Field of Search: 375/25, 375/26, 375/27, 375/37, 375/122, 375/37, 358/133, 358/135, 381/31, 381/36, 381/37, 381/40, 381/41, 381/43
• US Class Current: 375/254
• CPC Class Codes: G06T 9/008 Vector quantisation
• CPC Class Codes: H03M 7/3082 Vector coding for television signals, see H04N19/94
• CPC Class Codes: H04N 19/94 Vector quantisation

Abstract

A vector quantization method and apparatus utilizes a plurality of codebooks each of which has a predetermined number of candidate vectors. A distortion between each input vector and an averaged vector of a set of candidate vectors, each selected from one of the codebooks, is calculated for all combinations of candidate vectors, and a combination of candidate vectors which provides the smallest distortion is determined. Codes representing the candidate vectors thus determined are multiplexed, thereafter being outputted.

Claims

1. A multiplexed vector quantizer comprising:

a plurality of codebook storage means, each having prestored therein a predetermined number of candidate vectors;

selection means for selecting a set of candidate vectors each from one of the plurality of codebook storage means;

averaging means for averaging the set of candidate vectors and producing an averaged vector;

distortion calculating means whereby a distortion between an input vector and the averaged vector of the set of candidate vectors is calculated for each of a plurality of different sets of candidate vectors;

minimum distortion determining means for determining the set of candidate vectors whose averaged vector provides the smallest distortion; and

multiplexing means for multiplexing and outputting the codes representing the candidate vectors of the sets determined by the minimum distortion determining means.

2. The multiplexed vector quantizer of claim 1, wherein the multiplexing means is means for time-multiplexing the codes representing the candidate vectors.

3. The multiplexed vector quantizer of claim 1, wherein the distortion calculating means is means for calculating, as the distortion, a squared distance between the input vector and the averaged vector.

4. The multiplexed vector quantizer of claim 1, wherein the distortion calculating means is means for calculating, as the distortion, a weighted squared distance between the input vector and the averaged vector.

5. The multiplexed vector quantizer of claim 1, wherein the distortion calculating means includes substracting means for computing a difference vector between the averaged vector and the input vector and square summing means for calculating the sum of squares of respective elements of the difference vector and outputting the sum as the distortion.

6. The multiplexed vector quantizer of claim 1, wherein the distortion calculating means includes:

table memory means wherein sums of squares of respective elements of a vector, which is the sum of the candidate vectors of each of the sets, each selected from one of the plurality of codebook storage means, have been stored corresponding to the respective sets of candidate vectors;

inner product calculating means for calculating an inner product of the input vector and each set of candidate vectors, each selected from one of the plurality of codebook storage means; and

subtracting means for calculating a difference between the sum of the inner products from the inner product calculating means and the sum of squares corresponding to the selected set of candidate vectors read out of the table memory and outputting the calculated difference as the distortion.

7. The multiplexed vector quantizer of claim 1, wherein the distortion calculating means includes:

multiplying means which multiplies the input vector and a weighting vector input corresponding thereto and outputs a weighted input vector;

table memory means wherein a constant vector, which uses as each of its elements, the square of the sum of corresponding elements of respective candidate vectors of each of the sets, each selected from one of the plurality of codebook storage means, has been stored corresponding to each of the sets;

first inner product calculating means for calculating inner products of the candidate vectors of the sets selected from the plurality of codebook storage means and the weighted input vector from the multiplying means;

second inner product calculating means for calculating an inner product of the constant vector read out of the table memory means corresponding to the selected set of candidate vectors and the weighting vector; and

adding means for outputting, as the distortion, the difference between the inner products from the first and second inner product calculating means.

8. The multiplexed vector quantizer of any one of claims 1 to 7, wherein two codebooks are provided.

9. The multiplexed vector quantizer of claim 1, wherein the input vector is composed of k elements and the plurality of codebook storage means has stored therein an X-codebook which has N candidate vectors x_j, wherein j=0, 1, . . . , N-1, each consisting of k elements, and a Y-codebook which has N candidate vectors y_m, where m=0, 1, . . . , N-1, each consisting of k elements, k being a positive integer and N being an integer equal to or greater than 2.

10. The multiplexed vector quantizer of claim 9, wherein, letting i-th elements of the input vector and the candidate vectors x_j and y_m be represented by u(i), x(i,j) and y(i,m), respectively, the distortion calculating means is means for calculating, as the distortion for the candidate vectors x_j and y_m of the selected set (j, m), a distortion d'"'"'_j,m which is defined by the following equations:

##EQU16##

11. The multiplexed vector quantizer of claim 10, wherein the distortion calculating means includes table memory means wherein values obtained by calculating F(j,m) from Eq. (2) for all combinations (j,m) of the candidate vectors x_j and y_m have been stored corresponding to the combinations (j, m), and the distortion calculating means reads out of the table memory means the value of F(j,m) corresponding to the selected set of candidate vectors (j, m) and then calculates the distortion defined by Eq. (1).

12. The multiplexed vector quantizer of claim 9, wherein, letting i-th elements of an input weighting vector w, the input vector u and the candidate vectors x_j and y_m be represented by w(i), u(i), x(i,j) and y(i,m), respectively, the distortion calculating means is means for calculating, as the distortion for the candidate vectors x_j and y_m of the selected set (j, m), a distortion d'"'"'_j,m which is defined by the following equations:

##EQU17##

space="preserve" listing-type="equation">F(i,j,m)={x(i,j)+y(i,m)}.sup.2 (

     2)

13. The multiplexed vector quantizer of claim 12, wherein the distortion calculating means includes a table memory for storing precalculated values of at least one portion of the calculation of the constant vector F(i,j,m) expressed by Eq. (2) for the selected set of candidate vectors x_j and y_m.

14. The multiplexed vector quantizer of claim 1, wherein the multiplexing means is means for frequency multiplexing the codes respectively representing the candidate vectors.

15. A multiplexed vector quantization method in which an input signal sequence is divided into a plurality of groups, each consisting of plurality of samples and forming one input vector, and each input vector is quantized, comprising the steps of:

(a) selecting one candidate vector from each of a plurality of channels of codebooks, each having a predetermined number of candidate vectors;

(b) calculating a distortion between an averaged vector of the set of the selected candidate vectors and the input vector;

(c) repeating the steps (a) and (b) for candidate vectors of a plurality of different sets selected from the plurality of codebooks and determining the set of candidate vectors which yields the smallest one of the distortions respectively calculated; and

(d) multiplexing and outputting codes respectively representing the candidate vectors of the determined set.

16. The multiplexed vector quantization method of claim 15, wherein a squared distance between the input vector and the averaged vector is calculated as the distortion in step (b).

17. The multiplexed vector quantization method of claim 15, wherein a weighted squared distance between the input vector and the averaged vector is calculated as the distortion in step (b).

18. The multiplexed vector quantization method of claim 15, wherein each input vector is composed of k elements, one of the plurality of codebooks is an X-codebook which has N candidate vectors x_j, wherein j=0, 1, . . . , N-1, each consisting of k elements, and another of the codebooks is a Y-codebook which has N candidate vectors y_m, where m=0, 1, . . . , N-1, each consisting of k elements, k being a positive integer and N being an integer equal to or greater than 2.

19. The multiplexed vector quantization method of claim 18, wherein, letting i-th elements of the input vector u, the candidate vectors x_j and y_m be represented by u(i), x(i,j) and y(i,m), respectively, step (b) is a step of calculating, as the distortion for the candidate vectors x_j and y_m of the selected set (j, m), a distortion d'"'"'_j,m which is defined by the following equations:

##EQU18##

20. The multiplexed vector quantization method of claim 19, wherein step (b) is a step of calculating the distortion d'"'"'_j,m defined by Eq. (1), using a table memory having stored therein values obtained by precalculating, for all sets (j, m), the constants F(j,m) defined by Eq. (2).

21. The multiplexed vector quantization method of claim 20, wherein step (b) is a step of calculating the inner product of the input vector u and each of the candidate vectors x_j and y_m and calculating, as the distortion d'"'"'_j,m, the difference between the sum of the inner products and the constant F(j,m) read out of the table memory.

22. The multiplexed vector quantization method of claim 18, wherein, letting i-th elements of an input weighting vector w, the input vector u and the candidate vectors x_j and y_m be represented by w(i), u(i), x(i,j) and y(i,m), respectively, step (b) is a step of calculating, as the distortion for the candidate vectors x_j and y_m of the selected set (j, m), a distortion d'"'"'_j,m which is defined by the following equations:

##EQU19##

space="preserve" listing-type="equation">F(i,j,m)={x(i,j)+y(i,m)}.sup.2 (

     2)

23. The multiplexed vector quantization method of claim 22, wherein step (b) is a step of calculating the distortion d'"'"'_j,m defined by Eq. (1), using a table memory having stored therein precalculated values of at least one portion of the calculation of the constant vector F(i,j,m) defined by Eq. (2) for the selected set of candidate vectors x_j and y_m.

24. The multiplexed vector quantization method of claim 22, wherein the calculation of Eq. (1) in step (b) includes a step of multiplying the input vector u and the weighting vector w and a step of calculating the inner product of the multiplied result and each of the candidate vectors x_j and y_m.

25. The multiplexed vector quantization method of claim 18, wherein, letting i-th elements of an input weighting vector w, the input vector u and the candidate vectors x_j and y_m be represented by w(i), u(i), x(i,j) and y(i,m), respectively, step (b) is a step of calculating, as the distortion for the candidate vectors x_j and y_m of the selected set (j, m), a distortion d_j,m which is defined by the following equation:

##EQU20## where τ

is an arbitrary positive integer.

26. The multiplexed vector quantization method of claim 18, wherein step (b) is a step of calculating, as the distortion for the candidate vectors x_j and y_m of the selected set (j, m), a distortion d_j,m which is defined by the following equations:

space="preserve" listing-type="equation">d.sub.j,m =μ

|u-v.sub.j,m |.sup.2 +(1-μ

){|u-x.sub.j |.sup.2 +|u-y.sub.m |.sup.2 }/4

space="preserve" listing-type="equation">v.sub.j,m =(x.sub.j +y.sub.m)/2

where μ

is an arbitrary constant in the range of 0≦

μ

≦

1.

27. The multiplexed vector quantization method of claim 18, wherein step (b) is a step of calculating, as the distortion for the candidate vectors x_j and y_m of the selected set (j, m), a distortion d_j,m which is defined by the following equation:

##EQU21## where q(f|j) and q(g|m) represent the conditional probability that the codes j and m indicating the candidate vectors x_j and y_m erroneously change to g and f in a transmission channel, respectively.

28. The multiplexed vector quantization method of claim 15, wherein a step of preparing the plurality of codebooks includes:

(1) a step in which a predetermined number of input sample vectors are arbitrarily divided into a plurality of groups to produce a plurality of initial codebooks;

(2) a step in which training vectors of a number sufficiently larger than the predetermined number are used as input vectors and they are sequentially quantized by the multiplexed vector quantization method using the plurality of codebooks, thereby determining the set of candidate vectors to which each training vector corresponds;

(3) a step in which the contents of the plurality of codebooks except an arbitrary one of them are fixed, an arbitrary candidate vector of the said one codebook is regarded as a variable vector, an equation in which the sum of distortions for all training vectors containing the said one candidate vector in their corresponding sets of candidate vectors is partially differentiated by the variable vector, is set to zero, and a vector value obtained by solving the equation for the variable vector is replaced, as a new candidate vector, for the said one candidate vector;

(4) a step in which step (3) is repeated for all the other candidate vectors of the said one initial codebook and they are replaced with new candidate vectors, thereby renewing the contents of the said one initial codebook; and

(5) a step in which steps (2), (3), and (4) are repeated for all the other initial codebooks to renew their contents.

29. The multiplexed vector quantization method of claim 28, wherein the step of producing the plurality of codebooks includes a step of repeating the steps (2), (3) and (4) a plurality of times for the same codebook.

30. The multiplexed vector quantization method of claim 28, wherein the step of producing the plurality of codebooks includes a step of repeating the steps (2), (3), (4) and (5) a plurality of times.

31. The multiplexed vector quantization method of claim 15, wherein the step (d) is a step of time multiplexing and outputting the respective codes representing candidate vectors of the determined set.

32. The multiplexed vector quantization method of claim 15, wherein the step (d) is a step of frequency multiplexing and outputting the respective codes representing candidate vectors of the determined set.

33. The multiplexed vector quantization method of claim 31 or 32, wherein the codes representing the candidate vectors of the determined set are indices indicating the respective candidate vectors.

34. The multiplexed vector quantization method of claim 18, wherein the averaged vector is defined by the following equation:

space="preserve" listing-type="equation">v.sub.j,m ={2.sup.2r(x) x.sub.j +2.sup.2r(y) y.sub.m }/{2.sup.2r(x) +2.sup.2r(y) }

where r(x) and r(y) are transmission rates of the codes representing the candidate vectors x_j and y_m, respectively.

35. The multiplexed vector quantization method of claim 18, wherein, letting an i-th element of the input vector u and g-th elements of the candidate vectors x_j and y_m be represented by u(i), x(g,j) and y(g,m), respectively, the step (b) is a step of calculating, as the distortion for the candidate vectors x_j and y_m of the selected set, a distortion d_j,m which is defined by the following equation:

##EQU22## where h(i,g) is an element at an i-th row and a g-th column of a matrix for obtaining a convolution product and τ

is a parameter which minimizes the distortion d_j,m.