US5031037A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for vector quantizer parallel processing
Assignee: Utah State University Foundation
•
Filing: 1989-04-06
•
Granted: 1991-07-09
•
Expires: 2009-04-06
Abstract
Abstract An electronic circuit for quantizing vector signals is provided. The circuit compares input vectors with codebook entries that are representative of a vector space. Processors simultaneously compute the distance between the image vectors and the codebook entries. Selection circuitry is provided which compares the distance values and generates outputs which are representative of the codebook vector having the smallest distance and the distance itself.
Inventors
- 👤 Paul D. Israelsen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 20:53
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/3082; G; G06; G06T; G06T9/00; G06T9/008; H04; H04N; H04N19/00; H04N19/90; H04N19/94
Claims Analysis
Total Claims: 59
Claim 1
Independent Claim
61 words
A circuit for quantizing multi-component vectors, comprising: (a) means responsive to an input vector and a plurality of codebook vectors for implementing a full search of the codebook by simultaneously computing distance values between the input vector and each of the plurality of codebook vectors, and (b) means responsive to the simultaneously computed distance values for identifying the smallest distance value.
Claim 2
Dependent Claim
61 words
A circuit for quantizing multi-component vectors, comprising: (a) means responsive to an input vector and a plurality of codebook vectors for implementing a full search of the codebook by simultaneously computing distance values between the input vector and each of the plurality of codebook vectors, and (b) means responsive to the simultaneously computed distance values for identifying the smallest distance value.
Claim 3
Dependent Claim
24 words
A circuit in accordance with claim 1 further comprising means for generating an output indicative of the codebook vector having the smallest distance value.
Claim 4
Dependent Claim
22 words
A circuit in accordance with claim 1 further comprising a means for generating an output representative of the identified smallest distance value.
Claim 5
Dependent Claim
51 words
A circuit in accordance with claim 1 in which the means for computing distance values between the input vector and each codebook entry comprises a plurality of processor means, each processor means being capable of computing a distance value between the input vector and one of the plurality of codebook vectors.
Claim 6
Dependent Claim
50 words
A circuit in accordance with claim 4 in which the processor means comprises: (a) means for storing component values of a codebook vector, (b) means for storing component values of an input vector, and (c) arithmetic means for computing a distance value between the input vector and the codebook vector.
Claim 7
Dependent Claim
44 words
A circuit in accordance with claim 5 in which the arithmetic means comprises: (a) means for computing an arithmetic relationship between corresponding component values of the input vector and the codebook vector, and (b) means for combining the computed relationships into a distance value.
Claim 8
Dependent Claim
31 words
A circuit in accordance with claim 6 in which the arithmetic relationship is the absolute value of the difference between corresponding component values of the input vector and the codebook vector.
Claim 9
Dependent Claim
33 words
A circuit in accordance with claim 5 in which the distance value is the sum of the absolute values of the differences between component values of the input vector and the codebook vector.
Claim 10
Dependent Claim
19 words
A circuit in accordance with claim 5 in which stored component values of a codebook vector can be replaced.
Claim 11
Dependent Claim
32 words
A circuit in accordance with claim 8 in which stored component values of a codebook vector can be replaced during the time period when the arithmetic means is computing the arithmetic relationships.
Claim 12
Dependent Claim
32 words
A circuit in accordance with claim 5 in which the means for storing components of the codebook vector includes a latch for storing at least one component value of the codebook vector.
Claim 13
Dependent Claim
33 words
A circuit in accordance with claim 5 in which the means for storing component values of the codebook vector includes a register for simultaneously storing a plurality of components of the codebook vector.
Claim 14
Dependent Claim
32 words
A circuit in accordance with claim 5 in which the means for storing component values of the input vector includes a latch for at least one component value of the input vector.
Claim 15
Dependent Claim
43 words
A circuit in accordance with claim 5 in which the means for computing an arithmetic relationship between corresponding component values of the input vector and the codebook vector includes means capable of adding together or subtracting from one another the corresponding component values.
Claim 16
Dependent Claim
19 words
A circuit in accordance with claim 6 in which the means for combining the computed relationships is an accumulator.
Claim 17
Dependent Claim
14 words
A circuit in accordance with claim 14 in which the accumulator includes an adder.
Claim 18
Dependent Claim
19 words
A circuit in accordance with claim 14 in which the accumulator includes a register for storing an accumulated sum.
Claim 19
Dependent Claim
29 words
A circuit in accordance with claim 1 in which the means responsive to the simultaneously computed distance values for identifying the smallest distance value includes at least one comparator.
Claim 20
Dependent Claim
29 words
A circuit in accordance with claim 1 in which the means responsive to the simultaneously computed distance values for identifying the smallest distance value includes at least one multiplexer.
Claim 21
Dependent Claim
34 words
A circuit in accordance with claim 2 in which the means for generating an output indicative of the codebook vector for which the smallest distance value was computed includes at least one logic gate.
Claim 22
Dependent Claim
19 words
A vector quantizing circuit in accordance with claim 1 for receiving and processing individual components of a multi-component vector.
Claim 23
Dependent Claim
21 words
A vector quantizing circuit in accordance with claim 1 for receiving and processing vectors having a dimension greater than three (3).
Claim 24
Dependent Claim
24 words
A system for quantizing multi-component vectors comprising a plurality of circuits, each of said circuits being in accordance with the circuit of claim 1.
Claim 25
Dependent Claim
24 words
A system in accordance with claim 23 further comprising means for generating an output indicative of the circuit having computed the smallest distance value.
Claim 26
Dependent Claim
91 words
A circuit for quantizing multi-component vectors, comprising: (a) means responsive to an input vector and a plurality of codebook vectors for simultaneously computing distance values between the input vector and each codebook vector, and (b) means responsive to the simultaneously computed distance values for identifying the smallest distance value comprising a cascade of sets of comparators and multiplexers operating so that each set in the cascade makes pair-wise comparisons of the simultaneously computed distance values, and passes the smaller value of each pair-wise comparison to the next set in the cascade.
Claim 27
Dependent Claim
91 words
A circuit for quantizing multi-component vectors, comprising: (a) means responsive to an input vector and a plurality of codebook vectors for simultaneously computing distance values between the input vector and each codebook vector, and (b) means responsive to the simultaneously computed distance values for identifying the smallest distance value comprising a cascade of sets of comparators and multiplexers operating so that each set in the cascade makes pair-wise comparisons of the simultaneously computed distance values, and passes the smaller value of each pair-wise comparison to the next set in the cascade.
Claim 28
Independent Claim
49 words
A method for quantizing multi-component vectors, comprising the following steps: (a) implementing a full search of a codebook containing a plurality of codebook vectors by substantially simultaneously computing distance values between an input vector and each of the plurality of codebook vectors, and (b) identifying the smallest distance value.
Claim 29
Independent Claim
49 words
A method for quantizing multi-component vectors, comprising the following steps: (a) implementing a full search of a codebook containing a plurality of codebook vectors by substantially simultaneously computing distance values between an input vector and each of the plurality of codebook vectors, and (b) identifying the smallest distance value.
Claim 30
Dependent Claim
24 words
A method in accordance with claim 26 further comprising a step for indicating the codebook vector for which the smallest distance value was computed.
Claim 31
Dependent Claim
17 words
A method in accordance with claim 26 further comprising a step for indicating the smallest distance value.
Claim 32
Dependent Claim
38 words
A method in accordance with claim 26 in which the step for computing distance values comprises a plurality of processing operations in which each processing operation computes a distance value between the input vector and one codebook vector.
Claim 33
Dependent Claim
51 words
A method in accordance with claim 29 in which each processing operation comprises the following steps: (a) storing component values of a codebook vector, (b) storing component values of an input vector, (c) combining the stored component values to compute a distance value between the input vector and the codebook vector.
Claim 34
Dependent Claim
55 words
A method in accordance with claim 30 in which the step for computing a distance value between the the input vector and the codebook vector comprises the following steps: (a) computing arithmetic relationships between corresponding component values of the input vector and the codebook vector, and (b) combining the computed relationships into a distance value.
Claim 35
Dependent Claim
36 words
A method in accordance with claim 31 in which the arithmetic relationship is the absolute value of the difference between a component value of the input vector and the corresponding component value of the codebook vector.
Claim 36
Dependent Claim
34 words
A method in accordance with claim 31 in which the distance value is the sum of the absolute values of the differences between corresponding component values of the input vector and the codebook vector.
Claim 37
Dependent Claim
21 words
A vector quantizing circuit in accordance with claim 33 for receiving and processing vectors having a dimension greater than three (3).
Claim 38
Dependent Claim
73 words
A circuit for quantizing multi-component vectors, comprising: (a) means responsive to an input vector and a plurality of codebook vectors for implementing a full search of the codebook by substantially simultaneously computing distance values between the input vector and each of the plurality of codebook vectors, (b) means responsive to the computed distance values for identifying the smallest distance value, and (c) means for generating an output indicative of the smallest distance value.
Claim 39
Dependent Claim
73 words
A circuit for quantizing multi-component vectors, comprising: (a) means responsive to an input vector and a plurality of codebook vectors for implementing a full search of the codebook by substantially simultaneously computing distance values between the input vector and each of the plurality of codebook vectors, (b) means responsive to the computed distance values for identifying the smallest distance value, and (c) means for generating an output indicative of the smallest distance value.
Claim 40
Dependent Claim
31 words
A circuit in accordance with claim 35 further comprising means for generating an output indicative of the codebook vector for which the smallest distance value to the input vector was computed.
Claim 41
Dependent Claim
51 words
A circuit in accordance with claim 35 in which the means for computing distance values between the input vector and each codebook entry comprises a plurality of processor means being, each processor means capable of computing a distance value between the input vector and one of the plurality of codebook vectors
Claim 42
Dependent Claim
50 words
A circuit in accordance with claim 37 in which the processor means comprises: (a) means for storing component values of a codebook vector, (b) means for storing component values of an input vector, and (c) arithmetic means for computing a distance value between the input vector and the codebook vector.
Claim 43
Dependent Claim
45 words
A circuit in accordance with claim 38 in which the arithmetic means comprises: (a) means for computing an arithmetic relationship between corresponding component values of the input vector and the codebook vector, and (b) means for combining the computed relationships into a total distance value.
Claim 44
Dependent Claim
31 words
A circuit in accordance with claim 39 in which the arithmetic relationship is the absolute value of the difference between corresponding component values of the input vector and the codebook vector.
Claim 45
Dependent Claim
34 words
A circuit in accordance with claim 38 in which the distance value is the sum of the absolute values of the differences between corresponding component values of the input vector and the codebook vector.
Claim 46
Dependent Claim
19 words
A circuit in accordance with claim 38 in which stored component values of a codebook vector can be replaced.
Claim 47
Dependent Claim
32 words
A circuit in accordance with claim 38 in which stored component values of a codebook vector can be replaced during the time period when the arithmetic means is computing the arithmetic relationships.
Claim 48
Dependent Claim
33 words
A circuit in accordance with claim 387 in which the means for storing component values of the codebook vector includes a register for simultaneously storing a plurality of components of the codebook vector.
Claim 49
Dependent Claim
32 words
A circuit in accordance with claim 38 in which the means for storing component values of the input vector includes a latch for at least one component value of the input vector.
Claim 50
Dependent Claim
43 words
A circuit in accordance with claim 38 in which the means for computing an arithmetic relationship between corresponding component values of the input vector and the codebook vector includes means capable of adding together or subtracting from one another the corresponding component values.
Claim 51
Dependent Claim
19 words
A circuit in accordance with claim 39 in which the means for combining the computed relationships is an accumulator.
Claim 52
Dependent Claim
14 words
A circuit in accordance with claim 47 in which the accumulator includes an adder.
Claim 53
Dependent Claim
19 words
A circuit in accordance with claim 47 in which the accumulator includes a register for storing an accumulated sum.
Claim 54
Dependent Claim
25 words
A circuit in accordance with claim 35 in which the means responsive to the computed distance values for identifying the smallest distance value includes comparators.
Claim 55
Dependent Claim
25 words
A circuit in accordance with claim 35 in which the means responsive to the computed distance values for identifying the smallest distance value includes multiplexers.
Claim 56
Dependent Claim
31 words
A circuit in accordance with claim 36 in which the means for generating an output indicative of the codebook vector for which the smallest distance value was computed includes logic gates.
Claim 57
Dependent Claim
24 words
A system for quantizing multi-component vectors comprising a plurality of circuits, each of said circuits being in accordance with the circuit of claim 35.
Claim 58
Dependent Claim
101 words
A circuit for quantizing multi-component vectors, comprising: (a) means responsive to an input vector and a plurality of codebook vectors for computing distance values between the input vector and each codebook vector; (b) means responsive to the computed distance values for identifying the smallest distance value comprising a cascade of sets of comparators and multiplexers operating so that each set n the cascade makes a pair-wise comparison of the computed distance values and passes the smaller value of each pair-wise comparison to the next set in the cascade; and (c) means for generating an output indicative of the smallest distance value.
Claim 59
Dependent Claim
101 words
A circuit for quantizing multi-component vectors, comprising: (a) means responsive to an input vector and a plurality of codebook vectors for computing distance values between the input vector and each codebook vector; (b) means responsive to the computed distance values for identifying the smallest distance value comprising a cascade of sets of comparators and multiplexers operating so that each set n the cascade makes a pair-wise comparison of the computed distance values and passes the smaller value of each pair-wise comparison to the next set in the cascade; and (c) means for generating an output indicative of the smallest distance value.
References Cited (Backward Citations)
US3540002A
Cited
US4084260A
Cited
US4613948A
Cited
US4811265A
Cited
US4837632A
Cited
US4800425A
Cited
US4868867A
Cited
US4922508A
Cited
US4897720A
Cited
US4907276A
Cited
US4963030A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1994-07-08 | 1995-01-07 | 1995-07-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1998-07-08 | 1999-01-07 | 1999-07-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2002-07-08 | 2003-01-07 | 2003-07-09 | $7700.00 | Window Closed / Lapsed |