US5010574A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Vector quantizer search arrangement
Assignee: Nokia Bell Labs
•
Filing: 1989-06-13
•
Granted: 1991-04-23
•
Expires: 2009-06-13
Abstract
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.
Inventors
- 👤 Robert C. Wang
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 11:54
CPC Classifications
H; H03; H03M; H03M7/00; H04; H04N; H04N19/00; H04N19/90; H04N19/94; G; G06; G06T; G06T9/00; G06T9/008; H03M7/30; H03M7/3082
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
248 words
A method for coding a multi-element signal comprising the steps of: storing a plurality of multi-element reference signals y 1 , y 2 , . . . , 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.
Claim 2
Independent Claim
248 words
A method for coding a multi-element signal comprising the steps of: storing a plurality of multi-element reference signals y 1 , y 2 , . . . , 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.
Claim 3
Dependent Claim
82 words
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 .
Claim 4
Dependent Claim
276 words
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.
Claim 5
Independent Claim
37 words
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.
Claim 6
Independent Claim
24 words
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.
Claim 7
Independent Claim
24 words
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.
Claim 8
Dependent Claim
240 words
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.
Claim 9
Dependent Claim
240 words
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.
Claim 10
Dependent Claim
104 words
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 .
Claim 11
Dependent Claim
304 words
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.
Claim 12
Dependent Claim
59 words
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.
Claim 13
Dependent Claim
46 words
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.
Claim 14
Dependent Claim
46 words
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.
Claim 15
Dependent Claim
285 words
Apparatus for coding a multi-element signal comprising: means for storing a plurality of multi-element reference signals y 1 ,y 2 , . . . , 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.
Claim 16
Dependent Claim
285 words
Apparatus for coding a multi-element signal comprising: means for storing a plurality of multi-element reference signals y 1 ,y 2 , . . . , 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.
Claim 17
Dependent Claim
93 words
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 .
Claim 18
Dependent Claim
272 words
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.
Claim 19
Dependent Claim
32 words
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.
Claim 20
Dependent Claim
23 words
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.
Claim 21
Dependent Claim
23 words
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.
Claim 22
Independent Claim
276 words
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 1 , a 2 , . . . , 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 |.
Claim 23
Independent Claim
276 words
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 1 , a 2 , . . . , 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 |.
Claim 24
Dependent Claim
82 words
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.
Claim 25
Dependent Claim
289 words
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.
Claim 26
Independent Claim
317 words
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 1 t , e 2 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 |.
Claim 27
Independent Claim
317 words
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 1 t , e 2 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 |.
Claim 28
Dependent Claim
91 words
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 .
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1994-04-22 | 1994-10-22 | 1995-04-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1998-04-22 | 1998-10-22 | 1999-04-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2002-04-22 | 2002-10-22 | 2003-04-23 | $7700.00 | Window Closed / Lapsed |