Vector quantizer search arrangement - Patent Review 5010574

I claim:

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

storing a plurality of multi-element reference signals y.sub.1, y.sub.2, . . . , y.sub.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.sub.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.sub.y.sbsb.n of the reference signal y.sub.n on the reference line with the predetermined orientation in the prescribed vector space,

forming a signal representative of the projection p.sub.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.sub.i responsive to their projections p.sub.y.sbsb.i on the reference line with the predetermined orientation,

generating for each chosen reference signal y.sub.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 .vertline.p.sub.y.sbsb.i -p.sub.x .vertline. responsive to the reference signal projection p.sub.x, and input signal projection p.sub.x, and

determining the reference signal y.sub.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.sub.y.sbsb.1 <p.sub.y.sbsb.2 < . . . <p.sub.y.sbsb.N, and

the step of choosing one or more reference signals comprises successively selecting reference signals y.sub.i in the order of increasing distance of their projections p.sub.y.sbsb.i from the input signal projection p.sub.x.

3. A method for coding a multi-element signal according to claim 2 wherein the step of determining the reference signal y.sub.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.sub.m corresponding to the distance between the closest matching reference signal y.sub.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.sub.i, comparing the projection distance signal .vertline.p.sub.y.sbsb.i -p.sub.x .vertline. to the distance signal d.sub.m,

responsive to the selected reference signal projection distance .vertline.p.sub.y.sbsb.i -p.sub.x .vertline. being less than prescribed vector space distance d.sub.m in the comparing step,

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

(b) replacing the vector space distance signal d.sub.m with vector space distance signal d(y.sub.i x) responsive to d(y.sub.i,x)<d.sub.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.sub.y.sbsb.i being equal to or greater than vector space distance d.sub.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.sub.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.sub.y.sbsb.n of the reference signal y.sub.n on the predetermined orientation of the reference line in the prescribed vector space,

forming a signal representative of the projection p.sub.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.sub.i responsive to their projections p.sub.y.sbsb.i on the reference line with the predetermined orientation,

generating for each chosen reference signal y.sub.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 .vertline.p.sub.y.sbsb.i -p.sub.x .vertline. responsive to the reference signal projection p.sub.y.sbsb.i and input signal projection p.sub.x, and

determining the reference signal y.sub.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.sub.y.sbsb.1 <p.sub.y.sbsb.2 < . . . <p.sub.y.sbsb.N, and

the step of choosing one or more reference signals comprises successively selecting reference signals y.sub.i in the order of increasing distance .vertline.p.sub.y.sbsb.i -p.sub.x .vertline. from the input signal projection p.sub.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.sub.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.sub.m corresponding to the distance d(y.sub.m,x) between the closest matching reference signal y.sub.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.sub.i, comparing the projection distance signal .vertline.p.sub.y.sbsb.i -p.sub.x .vertline. to the distance signal d.sub.m,

responsive to the selected reference signal projection distance .vertline.p.sub.y.sbsb.i -p.sub.x .vertline. being less than prescribed vector space distance d.sub.m in the comparing step,

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

(b) replacing the vector space distance signal d.sub.m with vector space distance signal d(y.sub.i,x) responsive to d(y.sub.i,x)<d.sub.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 .vertline.p.sub.y.sbsb.i -p.sub.x .vertline. being equal to or greater than vector space distance d.sub.m in the comparing step, selecting reference signal y.sub.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.sub.1,y.sub.2, . . . , y.sub.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.sub.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.sub.y.sbsb.n of the reference signal y.sub.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.sub.x of the input signal on the reference line with the predetermined orientation in the prescribed vector space,

means responsive to the projections p.sub.y.sbsb.n on the reference line with the predetermined orientation of the reference signals y.sub.n for choosing one or more of the stored reference signals y.sub.i,

means responsive to the reference signal projection p.sub.y.sbsb.i and input signal projection p.sub.x for generating for each chosen reference signal y.sub.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 .vertline.p.sub.y.sbsb.i -p.sub.x .vertline., and

means responsive to the projection difference signals for determining the reference signal y.sub.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.sub.y.sbsb.1 <p.sub.y.sbsb.2 < . . . <p.sub.y.sbsb.N, and

the means for choosing one or more reference signals comprises means responsive to the reference projection signal p.sub.y.sbsb.n and the input projection signal p.sub.x for successively selecting reference signals y.sub.i in the order of increasing distance from the input signal projection p.sub.x.

15. Apparatus for coding a multi-element signal according to claim 14 wherein the means for determining the reference signal y.sub.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.sub.m corresponding to the distance between the closest matching reference signal y.sub.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.sub.i for comparing the projection distance signal .vertline.p.sub.y.sbsb.i -p.sub.x .vertline. to the distance signal d.sub.m,

means responsive to the selected reference signal projection distance .vertline.p.sub.y.sbsb.i -p.sub.x .vertline. being less than prescribed vector space distance d.sub.m in the comparing means for forming a signal corresponding to the vector space distance d(y.sub.i,x) between the input signal x and the reference signal y.sub.i in the prescribed vector space,

means responsive to d(y.sub.i,x)<d.sub.m for replacing the vector space distance signal d.sub.m with the vector space distance signal d(y.sub.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 .vertline.p.sub.y.sbsb.i -p.sub.x .vertline. being equal to or greater than vector space distance d.sub.m in the comparing means for selecting reference signal y.sub.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.sub.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.sub.1, a.sub.2, . . . , a.sub.N representable in the prescribed vector space; and

selecting one of the stored reference signals a.sub.m to represent the multi-element input signal x.sub.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.sub.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.sub.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.sub.i responsive to their projections p.sub.a.sbsb.i on the reference line with the predetermined orientation,

generating for each chosen reference signal a.sub.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 .vertline.p.sub.a.sbsb.i -p.sub.x.sbsb.a .vertline. responsive to the reference signal projection p.sub.a.sbsb.i and input signal projection p.sub.x.sbsb.a, and

determining the reference signal a.sub.m that most closely matches the input signal responsive to the projection difference signals .vertline.p.sub.a.sbsb.i -p.sub.x.sbsb.a .vertline..

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.sub.a.sbsb.1 <p.sub.a.sbsb.2 < . . . <p.sub.a.sbsb.N, and

the step of choosing one or more reference signals comprises successively selecting reference signals a.sub.i in the order of increasing distance of their projections p.sub.a.sbsb.i from the input signal projection p.sub.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.sub.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.sub.m corresponding to the distance between the closest matching reference signal a.sub.m and the input signal x.sub.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.sub.i, comparing the projection distance signal .vertline.p.sub.a.sbsb.i -p.sub.x.sbsb.a .vertline. to the distance signal d.sub.m,

responsive to the selected reference signal projection distance .vertline.p.sub.a.sbsb.i -p.sub.x.sbsb.a .vertline. being less than prescribed vector space distance d.sub.m in the comparing step

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

(b) replacing the vector space distance signal d.sub.m with vector space distance signal d(a.sub.i,x.sub.a) responsive to d(a.sub.i,x.sub.a)<d.sub.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 .vertline.p.sub.a.sbsb.i -p.sub.x.sbsb.a .vertline. being equal to or greater than vector space distance d.sub.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.sub.e corresponding to the excitation for the speech signal of each time frame interval,

converting the multi-element excitation signal x.sub.e into a signal x.sub.e.sup.t representable in a prescribed transform domain vector space,

storing a plurality of multi-element reference signals e.sub.1.sup.t, e.sub.2.sup.t, . . . , e.sub.N.sup.t representable in the prescribed transform domain vector space; and

selecting one of the stored reference signals e.sub.m.sup.t to represent the multi-element input signal x.sub.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.sub.e.sbsb.n.sup.t of the reference signal e.sub.n.sup.t on the reference line with the predetermined orientation in the prescribed transform domain vector space,

forming a signal representative of the projection p.sub.x.sbsb.e.sup.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.sub.i.sup.t responsive to their projections p.sub.e.sbsb.i.sup.t on the reference line with the predetermined orientation,

generating for each chosen reference signal e.sub.i.sup.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 .vertline.p.sub.e.sbsb.i.sup.t -p.sub.x.sbsb.e.sup.t .vertline. responsive to the reference signal projection p.sub.e.sbsb.i.sup.t and input signal projection p.sub.x.sbsb.e.sup.t, and

determining the reference signal e.sub.m.sup.t that most closely matches the input signal responsive to the projection difference signals .vertline.p.sub.e.sbsb.i.sup.t -p.sub.x.sbsb.e.sup.t .vertline..

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.sub.e.sbsb.1.sup.t <p.sub.e.sbsb.2.sup.t.sbsp.2 < . . . <p.sub.e.sbsb.N.sup.t, and

the step of choosing one or more reference signals comprises successively selecting reference signals e.sub.i.sup.t in the order o increasing distance of their projections p.sub.e.sbsb.i.sup.t from the input signal projection p.sub.x.sbsb.e.sup.t.

Description Submit all comments and votes

FIELD OF THE INVENTION

The invention relates to signal coding and more particularly to vector quantizing arrangements for coding digital speech and image signals.

BACKGROUND OF THE INVENTION

In digital speech and image transmission systems, the complex nature of signals to be transmitted requires high bit rates and time consuming processing. As is well known in the art, it is usually sufficient to transmit an approximation of a speech or image signal that is perceptually acceptable. Consequently, the transmission arrangements may be simplified by determining a set of indexed codes covering the range of expected signals and transmitting the indexed code closest to the signal. The process is known as vector quantization wherein vectors representing speech or image signals from a given vector space are mapped into a reduced set of vectors within the original vector space or some other representative vector space by well known clustering techniques. The reduced set of vectors, along with the associated mapping, is chosen to minimize error according to some distortion measure. This representative set of vectors is referred to as a codebook and is stored in fixed memory.

In transmission systems, the codebooks generated by vector quantization are stored at both the transmitter and the receiver. An input signal to be transmitted is processed at the transmitter by searching the stored codes for the one that best matches the signal. The index of the best matching code is transmitted as representative of the input signal. A code corresponding to the transmitted index is retrieved from the codebook at the receiver so that the transmission bit rate is greatly reduced.

The best matching code, however, only approximates the input signal. A codebook with only a few entries permits a rapid search. The selected code, however, may be a poor representation of the input signal so that it is difficult to obtain accurate signal representation. If a codebook contains sufficient entries to accurately represent all possible input signals, a time consuming search through a very large set of codes is needed to determine the closest matching code. The processing delay may exceed the time allotted for transmission of the signal. In some cases, vector quantization cannot meet the signal quality standards. In other cases, a compromise must be made between the accuracy of signal representation and the speed of transmission. Various improvements in search processing have been proposed to obtain the advantages of vector quantization with a large codebook.

U.S. Pat. No. 4,727,354 issued Feb. 23, 1988 to R. A. Lindsay discloses a system for selecting a best fit vector code in vector quantization encoding in which a sequential search through a codebook memory puts out a series of prestored associated error code vectors. These error code vectors are compared in sequence over a period of time in order to select the minimum error code vector (best fit). A clocking-sequencing arrangement enables an output latch to hold the index number which represents the particular error code vector presently having the minimum distortion. Each new set of input vector components will be sequenced to search for the minimum error code vector and index for that particular set of input vector components.

U.S. Pat. No. 4,797,925 issued Jan. 10, 1989 to Daniel Lin discloses a method for coding speech at low bit rates in which each code sequence is related to a previous code sequence so that the computational complexity of using a stored codebook is reduced. The article "Efficient Procedures for Finding the Optimum Innovation in Stochastic Coders" by I. M. Trancoso and B. S. Atal appearing in the Proceedings of the International Conference on Acoustics, Speech and Signal Processing (ICASSP), 1986, at pages 2375-2378, discloses an arrangement in which the signal and vectors are transformed into the frequency domain to simplify the search processing.

The article "Effect of Ordering the Codebook on the Efficiency of Partial Distance Search Algorithm for Vector Quantization" by K. K. Paliwal and V. Ramasubramanian appearing in the IEEE Transactions on Communications, Vol. 37, No. 3, May 1989, at pages 538-540, describes a search algorithm in which the distance between a codebook vector and a signal is evaluated as it is being calculated to remove vectors from consideration as early as possible. The algorithm is further improved by ordering the vectors in the codebook according to the sizes of their corresponding clusters.

The aforementioned schemes require complex signal processing for searching through complete codebooks to obtain accurate matching. It is an object of the invention to provide improved vector codebook searching with reduced signal processing requirements.

SUMMARY OF THE INVENTION

The foregoing object is achieved by an arrangement in which code search for a multi-component input signal is speeded up by generating a set of signals corresponding to the projection of the multi-component codes of a codebook on a predetermined orientation in a prescribed vector space. The projection of the input signal on the predetermined orientation is compared to the code projections from the codebook to reduce the signal processing in searching for the best matching code of the codebook.

The invention is directed to an arrangement for coding digital signals in which a plurality of N element reference signals representable in a prescribed vector space and a set of signals indexing the reference signals 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. The selection includes forming a set of signals each representative of the projection of one of the reference signals on the predetermined orientation and a signal representative of the projection of the input signal on the predetermined orientation in the prescribed vector space. Reference signals are chosen responsive to the differences in their projections with the projection of the input signal on the predetermined orientation. The projection difference signals determine the reference signal having the minimum distance to the input signal.

BRIEF DESCRIPTION OF THE DRAWING

FIG. 1 is a flowchart of a vector selection method illustrative of the invention;

FIG. 2 is a general block diagram of a vector quantization speech coding arrangement illustrative of the invention;

FIG. 3 is a general block diagram of a signal processor that may be used to implement the flowchart of FIG. 1;

FIG. 4 is a general block diagram of a vector quantization speech decoding arrangement illustrative of the invention;

FIG. 5 is a flowchart illustrating the operation of the linear predictive vector quantization search arrangements in FIG. 2;

FIG. 6 is a flowchart illustrating the operation of the excitation vector search arrangements in FIG. 2;

FIG. 7 is more detailed flowchart of the partial distance comparison operations of the flowchart of FIG. 6;

FIG. 8 is a flowchart illustrating the operation of the decoder of FIG. 4; and

FIG. 9 is a graph illustrating the search operations shown in the flowchart of FIG. 1.

DETAILED DESCRIPTION

FIG. 1 is a flowchart showing an arrangement for searching through a codebook of N element reference signals to select the reference signal that best matches a N element input signal illustrative of the invention. The multi-element input signal

x=(x.sub.1, x.sub.2, . . . , x.sub.N) (1)

may represent a portion of image or speech pattern. Each reference signal may be a multi-element speech or image representative signal

y.sub.n =y.sub.n1, y.sub.n2, . . . , y.sub.nN (2)

representable as a vector in a prescribed N dimension vector space. According to the invention, the time required for codebook searching is reduced by projecting the input signal and the reference signals on a predetermined orientation or dimension of the prescribed vector space. The comparison of the projections of the input signal to the projections of the reference signals greatly reduces the signal processing needed to obtain a best matching reference signal. By selecting a prescribed component as the predetermined orientation for projection, the signal processing required for the comparisons is further reduced. An additional reduction is obtained by arranging reference signals in the codebook in increasing projection order. In this way, the number of comparisons is also reduced.

Referring to FIG. 1, each of a set of reference signal vectors y.sub.1, y.sub.2, . . . , y.sub.N representable as in equation (2) in a Euclidean space R.sup.N is projected on a line in the space. A projection value P.sub.y.sbsp.n is obtained for each reference signal vector. The reference signal vectors are sorted in order of increasing projection values p in step 101 and stored in a codebook in that order (step 101). Any of the well known sorting techniques such as the binary sort described in "Fundamentals of Data Structures" by E. Horowitz and S. Sahni published by Computer Science Press, 1976, may be used. The projection ordered codebook is formed once and may be used thereafter for any input signal or sequence of input signals.

Each reference signal vector y.sub.n and each input signal vector has N dimensions. The line selected for the projections of the vectors may coincide with one of the components of the multi-component signal in the prescribed vector space. The projection should be a contraction mapping so that the projected distance e(u,v) between any two vectors, e.g., u and v defined as

.vertline.p(u)-p(v).vertline..ltoreq.d(u,v) (3)

where d(u,v) is the distance between vectors u and v in the Euclidean space R.sup.K. In this way, the projection mapping preserves the closeness between vectors to increase the searching speed. As is well known in the art, the contraction requirement does not restrict the selection of the line for projection.

The search begins in step 103 after the codebook is stored. A signal corresponding to the projection of the input signal p.sub.x is formed as per step 103. In step 105, the codebook is searched to find the index s of the vector y.sub.s closest to the projection of the input signal with a projection p.sub.s less than or equal to the input signal projection p.sub.x. This may be done by any of the searching methods well known in the art such as the binary search described in the aforementioned "Fundamentals of Data Structures" by E. Horowitz and S. Sahni. Once index s is determined, an index

t=s+1 (4)

is formed in step 110. The input signal projection p.sub.x is bounded by

p.sub.s .ltoreq.p.sub.x .ltoreq.p.sub.t (5)

the reference signal vectors having projections closest thereto.

A minimum vector distance signal d.sub.m and its index m are initially set to the largest possible number usable in the signal processor in step 115. The loop from step 120 to step 160 is then entered to determine the reference signal vector closest to the input signal vector, i.e., that provides the minimum distance signal d.sub.m. In step 120, the difference between reference signal projection p.sub.t and input signal projection p.sub.x is compared to the difference between reference signal projection p.sub.s and input signal projection p.sub.x. If projection p.sub.t is closer to p.sub.x than projection p.sub.s, closest projection index i is set to t and index t is incremented (step 125). Otherwise index i is set to s and index s is decremented (step 130). In the first iteration of the loop from step 120 to step 160, the reference signal vectors found in steps 105 and 110 are used in step 120 as the candidates for the best matching vectors.

A signal

e=.vertline.p.sub.i -p.sub.x .vertline. (6)

corresponding to the distance between the input signal projection and the closest reference signal projection from step 125 or step 130 is produced in step 135. If projection difference signal e is greater than the current minimum distance signal d.sub.m, the previously considered reference signal vector is closest to input signal x. This is so because the distance d(y.sub.i,x) is always greater than the corresponding projection distance e. Signal e is larger for each successive iteration since the projections of the initial codebook vector candidates are closest to the projection of the input signal. In accordance with the invention, the selection of the best matching reference signal is limited to a relatively small number of reference signals. Additionally, the signal processing for projection distances is considerably simpler than for vector space distances.

In the event, projection distance signal e of equation (5) is not greater than d.sub.m in step 140, y.sub.i is a possible candidate for the best matching reference signal. Step 145 is entered wherein the distance between q.sub.i, the projection of y.sub.i along another or secondary line in the prescribed vector space, and q.sub.x, the projection of x along the secondary line in the vector space is formed. This secondary projection .vertline.q.sub.y.sbsb.i -q.sub.x .vertline. is compared with the previously obtained minimum distance signal d.sub.m (step 145). Where d.sub.m is exceeded, reference signal y.sub.i cannot be accepted as the best matching reference signal. This is evident since any projection distance e for y.sub.i is always less than the corresponding vector space distance d(y.sub.i,x). Control is then returned to step 120 to consider the reference signal with the next closest projection.

If the secondary projection in step 145 is less than d.sub.m, reference signal is a better candidate than reference signal y.sub.m. The vector space distance d(y.sub.i, x) generated (step 150) is compared to the minimum distance signal d.sub.m (step 155). Step 160 is entered from step 155 when vector space distance d(y.sub.i,x) is less than d.sub.m. The codebook index m for the minimum distance vector is then set equal to i and d.sub.m is set equal to d(y.sub.i,x). Control is then passed to step 120 for the next iteration. Where d(y.sub.i,x) is greater than d.sub.m in step 155, control is passed directly to step 120. The minimum distance signal d.sub.m remains unaltered.

FIG. 9 shows the locations of an input signal and a plurality of reference vectors in a two dimensional view that illustrates the quantization method of the invention. Primary projections are taken along the horizontal dimension 901 and secondary projections are taken along the vertical dimension 903. Reference signal vectors y.sub.1 through y.sub.8 are located at points 910-1 through 910-8, respectively. The primary projections of vectors y.sub.1 through y.sub.8 are at points 915-1 through 915-8. Input signal x is located at point 920 and its primary projection is at point 925 between the projection points 915-4 and 915-5 for reference signals y.sub.4 and y.sub.5. Circle 930 centered at the location of input signal x (point 920) indicates the distance d(x,y.sub.5) to closest reference signal y.sub.5.

Table 1 lists the reference signal vector coordinates, the primary projections (.vertline.p.sub.y.sbsp.i -p.sub.x .vertline.), the secondary projections (.vertline.q.sub.y.sbsb.i -q.sub.x .vertline.), and the distances d(x,y.sub.i).

TABLE 1 ______________________________________ Prim. Sec. Prim. Sec. Dist. to Ref. Sig. Coord. Coord. Proj. Proj. Input Sig. ______________________________________ y.sub.1 2 6 12 12 16.97 y.sub.2 5 21 9 3 9.49 y.sub.3 7 14 7 4 8.06 y.sub.4 12 5 2 13 13.15 y.sub.5 17 22 3 4 5.00 y.sub.6 18 10 4 8 8.94 y.sub.7 20 16 6 2 6.32 y.sub.8 24 2 10 16 18.87 ______________________________________

Referring to FIG. 1, The reference signal vectors are arranged in a codebook store according to the primary projections 915-1 through 915-8 as per step 101. Since the projections correspond to the primary projection coordinate, these values are already stored. There is no need to calculate the projection values. The coordinates of input signal x (14, 18) are obtained in step 103 and the codebook search of steps 105 and 110 results in the initial projection indices s=4 and t=5. The minimum vector distance and the corresponding vector index are initially set arbitrarily to a number larger than the largest possible distance signal (LPN) in step 115.

At the start of the first iteration, s=4, t=5 and d.sub.m =LPN. Primary projection .vertline.p.sub.x -p.sub.y.sbsp.4 .vertline. is determined to be less than primary projection .vertline.p.sub.y.sbsp.5 -p.sub.x .vertline. in step 120. i is then set to 4 and s is decremented to 3 in step 130. The projection signal e=2 is formed in step 135. Since primary projection signal e is less than d.sub.m =LPN, the secondary projection .vertline.q.sub.y.sbsb.4 -q.sub.x .vertline. is compared to d.sub.m =LPN in step 145. The distance signal d(x,y.sub.4)=13.15 generated (step 150) is found to be less than d.sub.m =LPN (step 155). d.sub.m is set to d(x,y.sub.4) in step 160 and step 120 is reentered for the second iteration.

During the second iteration, i is set to 5 and t is incremented to 6 in step 125 since primary projection .vertline.p.sub.y.sbsb.5 -p.sub.x .vertline. is less than .vertline.p.sub.y.sbsb.3 -p.sub.x .vertline.. Projection .vertline.p.sub.y.sbsb.5 -p.sub.x .vertline.=3 is less than d.sub.m =13.15 (step 135) and secondary projection .vertline.q.sub.y.sbsb.4 -q.sub.x .vertline.=4 is less than 13.15 (step 140). Distance signal d(x,y.sub.5)=5 is generated in step 150 and is compared to 13.15 in step 155. As a result, minimum distance signal d.sub.m becomes 5 and m becomes 5 in step 160.

i is set to 6 and t is incremented to 7 in step 125 of the third iteration since primary projection .vertline.p.sub.y.sbsb.6 -p.sub.x .vertline.=4 is less than .vertline.p.sub.y.sbsb.3 -p.sub.x .vertline. (step 120). The primary projection

e=.vertline.p.sub.y.sbsb.6 -p.sub.x .vertline.=4

is less than d.sub.m but the secondary projection

.vertline.q.sub.y.sbsb.6 -q.sub.x .vertline.=8

is greater than d.sub.m. Signal d.sub.m is not altered and the fourth iteration is initiated in step 120. Index i changes to 7 and t is incremented to 8 (step 125). Since primary projection

e=.vertline.p.sub.y.sbsb.7 -p.sub.x .vertline.=6

is greater than minimum distance signal d.sub.m =5 (step 140), the selection loop is exited from step 140. The best fitting reference signal vector has been determined as y.sub.5 and the corresponding index signal m=5 is available for transmission.

Advantageously, the projection arrangement according to the invention reduces the scope of a search through a reference signal codebook and reduces the signal processing needed to compare the input signal to each reference signal vector in the limited search. Two dimensions have been used in the foregoing example for purposes of illustration. It is to be understood that the method is readily extendible to multidimensional vector spaces such as those employed to represent complex speech and image signals.

FIG. 2 shows a general block diagram of a speech processor illustrative of the invention. In FIG. 2, a speech pattern such as a spoken message is received by a transducer 201 such as a microphone. The analog speech signal obtained from the microphone is band limited and converted into a sequence of pulse samples in filter and sampler 203. The filtering may be arranged to remove frequency components of the speech signal above 4.0 KHz and the sampling may be at an 8 KHz rate as is well known in the art. The timing of the samples is controlled by sample clock signal CL from clock generator 225. Each sample from filter and sampler 203 is transformed into an amplitude representative digital signal in analog-to-digital converter 205.

The sequence of digital speech samples from converter 205 is applied to linear predictive processor 215. This processor, as is well known in the art, partitions the speech samples into time intervals or frames of 10 to 20 milliseconds and generates a set of linear prediction coefficient signals x.sub.a =x.sub.1, x.sub.2, . . . , x.sub.p for each time frame. The coefficient signals represent the predicted short term spectrum of the N>p speech sample of the time interval. A signal R corresponding to the autocorrelation coefficient for the time frame is also generated in processor 215. Delay circuit 210 delays the digital samples from converter 205 to allow time to form coefficient signals x.sub.a for a time interval. The delayed digital samples supplied to residual signal generator 220 in which the delayed speech samples and the prediction parameters x.sub.a to form a signal corresponding to the difference therebetween. The formation of the predictive parameter and residual signals may be performed according to the arrangement disclosed in U.S. Pat. No. 3,740,476 issued to B. S. Atal, June 19, 1973, or by other techniques well known in the art.

According to the invention, a line