Vector quantizer search arrangement

• US 5,010,574 A
• Filed: 06/13/1989
• Issued: 04/23/1991
• Est. Priority Date: 06/13/1989
• Status: Expired due to Term

• Current Assignee: American Telephone & Telegraph Company (AT&T, Inc.), Bell Telephone Laboratories, Inc. (Nokia Corporation)
• Original Assignee: AT&T, Inc.
• Inventors: Wang, Robert C.
• Primary Examiner(s): Kemeny, Emanuel S.
• Application Number:
  US07/365,642
• Time in Patent Office: 679 Days
• Field of Search: 381/42, 381/43
• US Class Current: 704/222
• 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

In an arrangement for coding multi-element signals such as used in speech or image processing, a plurality of N element reference signals representable in a prescribed vector space are stored. An N element input signal representable in the prescribed vector space is received and one of the reference signals is selected to represent the input signal. A set of signals each representative of the projection of one of the reference signals on a predetermined orientation in the prescribed vector space and a signal representative of the projection of the input signal on the predetermined orientation are formed. The reference signals are arranged according to their projections on the predetermined orientation. Candidates for the best matching reference signal are selected according to the differences between their projections on the prescribed orientation and the projection of the input signal on the prescribed orientation and the projection difference signals are utilized to determine the reference signal closest to the input signal in the prescribed vector space.

Claims

1. A method for coding a multi-element signal comprising the steps of:

storing a plurality of multi-element reference signals y₁, y₂, . . . , y_N in a codebook storage array representable in a prescribed vector space;

receiving a multi-element input signal x representable in the prescribed vector space; and

selecting one of the stored reference signals y_m to represent the multi-element input signal;

the selecting step including;

selecting a predetermined orientation of a reference line for projection mapping in the prescribed vector space,

forming a set of signals each representative of the projection p_y.sbsb.n of the reference signal y_n on the reference line with the predetermined orientation in the prescribed vector space,

forming a signal representative of the projection p_x of the input signal on the reference line with the predetermined orientation in the prescribed vector space,

choosing one or more of the stored reference signals y_i responsive to their projections p_y.sbsb.i on the reference line with the predetermined orientation,

generating for each chosen reference signal y_i, a signal representative of the difference between the reference signal projection and the input signal projection on the reference line with the predetermined orientation |p_y.sbsb.i -p_x | responsive to the reference signal projection p_x, and input signal projection p_x, and

determining the reference signal y_m that most closely matches the input signal responsive to the projection difference signals.

2. A method for coding a multi-element signal according to claim 1 wherein

the stored reference signals are arranged in the order of their projections on the reference line with the predetermined orientation p_y.sbsb.1 <

p_y.sbsb.2 <

. . . <

p_y.sbsb.N, and

the step of choosing one or more reference signals comprises successively selecting reference signals y_i in the order of increasing distance of their projections p_y.sbsb.i from the input signal projection p_x.

3. A method for coding a multi-element signal according to claim 2 wherein the step of determining the reference signal y_m that most closely matches the input signal responsive to the projection difference signals comprises

initially setting a signal m corresponding to the index of the most closely matching reference signal to a value greater than N and a signal d_m corresponding to the distance between the closest matching reference signal y_m and the input signal x to a value greater than the largest distance between any of the reference signals and the input signal in the prescribed vector space,

for each successively selected reference signal y_i, comparing the projection distance signal |p_y.sbsb.i -p_x | to the distance signal d_m,

responsive to the selected reference signal projection distance |p_y.sbsb.i -p_x | being less than prescribed vector space distance d_m in the comparing step,

(a) forming a signal corresponding to the vector space distance d(y_i, x) between the input signal x and the reference signal y_i in the prescribed vector space,

(b) replacing the vector space distance signal d_m with vector space distance signal d(y_i x) responsive to d(y_i,x)<

d_m,

(c) setting the selected reference signal index m equal to reference signal index i, and

(d) returning to the comparing step for the next successively chosen reference signal i, and

responsive to the selected reference signal projection distance p_y.sbsb.i being equal to or greater than vector space distance d_m in the comparing step, selecting reference signal m as the closest matching reference signal.

4. A method for coding a multi-element signal according to claims 1, 2 or 3 wherein the predetermined orientation of the reference line in the prescribed vector space corresponds to a predetermined element of the multi-element input signal.

5. A method for coding a multi-element signal according to claims 1, 2 or 3 wherein the multi-element input signal is a speech representative signal.

6. A method for coding a multi-element signal according to claims 1, 2 or 3 wherein the multi-element input signal is an image representative signal.

7. In a signal processing system having a memory for storing a plurality of multi-element reference signals representable in a prescribed vector space, the method of coding a multi-element signal comprising the steps of;

receiving a multi-element input signal x representable in the prescribed vector space; and

selecting one of the stored reference signals y_m to represent the multi-element input signal;

the selecting step including;

selecting a predetermined orientation of a reference line for protection mapping in the prescribed vector space,

forming a set of signals each representative of the projection p_y.sbsb.n of the reference signal y_n on the predetermined orientation of the reference line in the prescribed vector space,

forming a signal representative of the projection p_x of the input signal on the reference line with the predetermined orientation in the prescribed vector space,

choosing one or more of the stored reference signals y_i responsive to their projections p_y.sbsb.i on the reference line with the predetermined orientation,

generating for each chosen reference signal y_i, a signal representative of the difference between the reference signal projection and the input signal projection on the reference line with the predetermined orientation |p_y.sbsb.i -p_x | responsive to the reference signal projection p_y.sbsb.i and input signal projection p_x, and

determining the reference signal y_m that most closely matches the input signal responsive to the projection difference signals.

8. In a signal processing system having a memory for storing a plurality of multi-element reference signals representable in a prescribed vector space, the method of coding a multi-element signal according to claim 7 wherein

the stored reference signals are arranged in the order of their projections on the reference line with the predetermined orientation p_y.sbsb.1 <

p_y.sbsb.2 <

. . . <

p_y.sbsb.N, and

the step of choosing one or more reference signals comprises successively selecting reference signals y_i in the order of increasing distance |p_y.sbsb.i -p_x | from the input signal projection p_x.

9. In a signal processing system having a memory for storing a plurality of multi-element reference signals representable in a prescribed vector space, the method of coding a multi-element signal according to claim 8 wherein the step of determining the reference signal y_m that most closely matches the input signal responsive to the projection difference signals comprises

initially setting a signal m corresponding to the index of the most closely matching reference signal to a value greater than N and a signal d_m corresponding to the distance d(y_m,x) between the closest matching reference signal y_m and the input signal x to a value greater than the largest distance between any of the reference signals and the input signal in the prescribed vector space,

for each successively selected reference signal y_i, comparing the projection distance signal |p_y.sbsb.i -p_x | to the distance signal d_m,

responsive to the selected reference signal projection distance |p_y.sbsb.i -p_x | being less than prescribed vector space distance d_m in the comparing step,

(a) forming a signal corresponding to the vector space distance d(y_i,x) between the input signal x and the reference signal y_i in the prescribed vector space,

(b) replacing the vector space distance signal d_m with vector space distance signal d(y_i,x) responsive to d(y_i,x)<

d_m,

(c) setting the selected reference signal index m equal to reference signal index i, and

(d) returning to the comparing step for the next successively chosen reference signal i, and

responsive to the selected reference signal projection distance |p_y.sbsb.i -p_x | being equal to or greater than vector space distance d_m in the comparing step, selecting reference signal y_m as the closest matching reference signal.

10. In a signal processing system having a memory for storing a plurality of multi-element reference signals representable in a prescribed vector space, the method of coding a multi-element signal according to claim 7, 8 or 9 wherein the predetermined orientation at the reference line in the prescribed vector space corresponds to a predetermined element of the multi-element input signal.

11. In a signal processing system having a memory for storing a plurality of multi-element reference signals representable in a prescribed vector space, the method of coding a multi-element signal according to claims 7, 8 or 9 wherein the multi-element input signal is a speech representative signal.

12. In a signal processing system having a memory for storing a plurality of multi-element reference signals representable in a prescribed vector space, the method of coding a multi-element signal according to claims 7, 8 or 9 wherein the multi-element input signal is an image representative signal.

13. Apparatus for coding a multi-element signal comprising:

means for storing a plurality of multi-element reference signals y₁,y₂, . . . , y_n in a codebook storage array representable in a prescribed vector space;

means for receiving a multi-element input signal x representable in the prescribed vector space; and

means for selecting one of the stored reference signals y_m to represent the multi-element input signal;

the selecting means including;

means for selecting a predetermined orientation of a reference line for projection mapping in the prescribed vector space,

means responsive to the reference signals and the predetermined orientation for forming a set of signals each representative of the projection p_y.sbsb.n of the reference signal y_n on the reference line with the predetermined orientation in the prescribed vector space,

means responsive to the input signal and the predetermined orientation for forming a signal representative of the projection p_x of the input signal on the reference line with the predetermined orientation in the prescribed vector space,

means responsive to the projections p_y.sbsb.n on the reference line with the predetermined orientation of the reference signals y_n for choosing one or more of the stored reference signals y_i,

means responsive to the reference signal projection p_y.sbsb.i and input signal projection p_x for generating for each chosen reference signal y_i, a signal representative of the difference between the reference signal projection and the input signal projection on the reference line with the predetermined orientation |p_y.sbsb.i -p_x |, and

means responsive to the projection difference signals for determining the reference signal y_m that most closely matches the input signal.

14. Apparatus for coding a multi-element signal according to claim 13 wherein

the stored reference signals are arranged in the order of their projections on the reference line with the predetermined orientation p_y.sbsb.1 <

p_y.sbsb.2 <

. . . <

p_y.sbsb.N, and

the means for choosing one or more reference signals comprises means responsive to the reference projection signal p_y.sbsb.n and the input projection signal p_x for successively selecting reference signals y_i in the order of increasing distance from the input signal projection p_x.

15. Apparatus for coding a multi-element signal according to claim 14 wherein the means for determining the reference signal y_m that most closely matches the input signal responsive to the projection difference signals comprises

means for initially setting a signal m corresponding to the index of the most closely matching reference signal to a value greater than N and a signal d_m corresponding to the distance between the closest matching reference signal y_m and the input signal x to a value greater than the largest distance between any of the reference signals and the input signal in the prescribed vector space,

means operative for each successively selected reference signal y_i for comparing the projection distance signal |p_y.sbsb.i -p_x | to the distance signal d_m,

means responsive to the selected reference signal projection distance |p_y.sbsb.i -p_x | being less than prescribed vector space distance d_m in the comparing means for forming a signal corresponding to the vector space distance d(y_i,x) between the input signal x and the reference signal y_i in the prescribed vector space,

means responsive to d(y_i,x)<

d_m for replacing the vector space distance signal d_m with the vector space distance signal d(y_i,x) and for setting the selected reference signal index m equal to reference signal index i, and

means responsive to the selected reference signal projection distance |p_y.sbsb.i -p_x | being equal to or greater than vector space distance d_m in the comparing means for selecting reference signal y_m as the closest matching reference signal.

16. Apparatus for coding a multi-element signal according to claims 13, 14 or 15 wherein the predetermined orientation in the prescribed vector space corresponds to a predetermined element of the multi-element input signal.

17. Apparatus for coding a multi-element signal according to claims 13, 14 or 15 wherein the multi-element input signal is a speech representative signal.

18. Apparatus for coding a multi-element signal according to claims 13, 14 or 15 wherein the multi-element input signal is an image representative signal.

19. A method for coding a speech signal comprising:

partitioning the speech signal into a sequence of time frame intervals,

generating a multi-element signal x_a corresponding to the predictive parameters for the speech signal of each time frame interval and representable in a prescribed vector space,

storing a plurality of multi-element reference signals a₁, a₂, . . . , a_N representable in the prescribed vector space; and

selecting one of the stored reference signals a_m to represent the multi-element input signal x_a ;

the selecting step including;

selecting a predetermined orientation of a reference line for projecting mapping in the prescribed vector space,

forming a set of signals each representative of the projection p_a.sbsb.n of the reference signal on the reference line with the predetermined orientation in the prescribed vector space,

forming a signal representative of the projection p_x.sbsb.a of the input signal on the reference line with the predetermined orientation in the prescribed vector space,

choosing one or more of the stored reference signals a_i responsive to their projections p_a.sbsb.i on the reference line with the predetermined orientation,

generating for each chosen reference signal a_i, a signal representative of the difference between the reference signal projection and the input signal projection on the reference line with the predetermined orientation |p_a.sbsb.i -p_x.sbsb.a | responsive to the reference signal projection p_a.sbsb.i and input signal projection p_x.sbsb.a, and

determining the reference signal a_m that most closely matches the input signal responsive to the projection difference signals |p_a.sbsb.i -p_x.sbsb.a |.

20. A method for coding a multi-element signal according to claim 19 wherein

the stored reference signals are arranged in the order of their projections on the reference line with the predetermined orientation p_a.sbsb.1 <

p_a.sbsb.2 <

. . . <

p_a.sbsb.N, and

the step of choosing one or more reference signals comprises successively selecting reference signals a_i in the order of increasing distance of their projections p_a.sbsb.i from the input signal projection p_x.sbsb.a.

21. A method for coding a multi-element signal according to claim 20 wherein the step of determining the reference signal a_m that most closely matches the input signal responsive to the projection difference signals comprises

initially setting a signal m corresponding to the index of the most closely matching reference signal to a value greater than N and a signal d_m corresponding to the distance between the closest matching reference signal a_m and the input signal x_a to a value greater than the largest distance between any of the reference signals and the input signal in the prescribed vector space,

for each successively selected reference signal a_i, comparing the projection distance signal |p_a.sbsb.i -p_x.sbsb.a | to the distance signal d_m,

responsive to the selected reference signal projection distance |p_a.sbsb.i -p_x.sbsb.a | being less than prescribed vector space distance d_m in the comparing step

(a) forming a signal corresponding to the vector space distance d(a_i,x_a) between the input signal x_a and the reference signal a_i in the prescribed vector space,

(b) replacing the vector space distance signal d_m with vector space distance signal d(a_i,x_a) responsive to d(a_i,x_a)<

d_m,

(c) setting the selected reference signal index m equal to reference signal index i, and

(d) returning to the comparing step for the next successively chosen reference signal i, and

responsive to the selected reference signal projection distance |p_a.sbsb.i -p_x.sbsb.a | being equal to or greater than vector space distance d_m in the comparing step, selecting reference signal m as the closest matching reference signal.

22. A method for coding a speech signal comprising:

partitioning the speech signal into a sequence of time frame intervals,

generating a multi-element signal x_e corresponding to the excitation for the speech signal of each time frame interval,

converting the multi-element excitation signal x_e into a signal x_e^t representable in a prescribed transform domain vector space,

storing a plurality of multi-element reference signals e₁^t, e₂^t, . . . , e_N^t representable in the prescribed transform domain vector space; and

selecting one of the stored reference signals e_m^t to represent the multi-element input signal x_e ;

the selecting step including;

selecting a predetermined orientation of a reference line for protection mapping in the prescribed transform domain vector space;

forming a set of signals each representative of the projection p_e.sbsb.n^t of the reference signal e_n^t on the reference line with the predetermined orientation in the prescribed transform domain vector space,

forming a signal representative of the projection p_x.sbsb.e^t of the input signal on the reference line with the predetermined orientation in the prescribed transform domain vector space,

choosing one or more of the stored reference signals e_i^t responsive to their projections p_e.sbsb.i^t on the reference line with the predetermined orientation,

generating for each chosen reference signal e_i^t, a signal representative of the difference between the reference signal projection and the input signal projection on the reference line with the predetermined orientation |p_e.sbsb.i^t -p_x.sbsb.e^t | responsive to the reference signal projection p_e.sbsb.i^t and input signal projection p_x.sbsb.e^t, and

determining the reference signal e_m^t that most closely matches the input signal responsive to the projection difference signals |p_e.sbsb.i^t -p_x.sbsb.e^t |.

23. A method for coding a multi-element signal according to claim 22 wherein

the stored reference signals are arranged in the order of their projections on the reference line with the predetermined orientation p_e.sbsb.1^t <

p_e.sbsb.2^t.sbsp.2 <

. . . <

p_e.sbsb.N^t, and

the step of choosing one or more reference signals comprises successively selecting reference signals e_i^t in the order o increasing distance of their projections p_e.sbsb.i^t from the input signal projection p_x.sbsb.e^t.