US4907276A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Fast search method for vector quantizer communication and pattern recognition systems
Assignee: DSP Group Israel Ltd
•
Filing: 1988-04-05
•
Granted: 1990-03-06
•
Expires: 2008-04-05
Abstract
Abstract An encoder apparatus for communication and pattern recognition systems employing a nearest neighbor search method for signal and data compression, based on a vector encoding quantization technique which optimizes systems performance with substantially reduced computational complexity using a fast geometrically-oriented search procedure. The apparatus comprises pre-procesing apparatus for providing off-line reorganization of a codebook having a set of reference vector patterns constituting codevectors with which the input vector is to be compared in a search procedure, and on-line apparatus for encoding the random input vector through quantization in accordance with the search procedure in the codebook. The on-line encoding apparatus comprises: apparatus for providing a transform domain vector having a set of eigenvectors associated therewith; apparatus for determining a surface vector nearest to the transform domain vector on the axis having the largest variance; apparatus for determining a distance value providing the distortion between the transform domain vector and the surface vector, defined by the Euclidean distance; apparatus for determining a codebook contiguous sub-group range having contained therewithin codevectors and being bounded by a hypersphere having a k-dimensional radius defined as the square root of the distance value; and apparatus for performing a full search over the contiguous sub-group range within the hypersphere to select the one of the codevectors nearest to the transform domain vector for encoding it in accordance with the one selected codevector.
Inventors
- 👤 Shabtai Aldersberg
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 10:51
CPC Classifications
G; G06; G06T; G06T9/00; G06T9/005; G06F; G06F18/00; G06F18/20; G06F18/24; G06F18/241; G06F18/2413; G06F18/24133; G06F18/24137; G06T9/008; G10; G10L; G10L19/00; G10L19/02; G10L19/032; G10L19/038; H; H03; H03M; H03M7/00; H03M7/30; H03M7/3082
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
123 words
An apparatus for encoding speech signals represented by a random input vector having k components, said apparatus comprising: pre-processing means for providing off-line reorganization of a codebook having a set of reference vector patterns constituting codevectors with which the input vector is to be compared in a search procedure, said pre-processing means comprising: means for transforming each of said codebook codevectors to provide a transform domain representation of said codebook; means for determining a principal axis p having the largest variance in said codebook transform domain representation; and means for re-ordering said codebook codevectors according to their descending value on the p axis; and on-line means for encoding the random input vector through quantization in accordance with said search procedure in the codebook.
Claim 2
Independent Claim
123 words
An apparatus for encoding speech signals represented by a random input vector having k components, said apparatus comprising: pre-processing means for providing off-line reorganization of a codebook having a set of reference vector patterns constituting codevectors with which the input vector is to be compared in a search procedure, said pre-processing means comprising: means for transforming each of said codebook codevectors to provide a transform domain representation of said codebook; means for determining a principal axis p having the largest variance in said codebook transform domain representation; and means for re-ordering said codebook codevectors according to their descending value on the p axis; and on-line means for encoding the random input vector through quantization in accordance with said search procedure in the codebook.
Claim 3
Dependent Claim
196 words
The apparatus of claim 1 and wherein said on-line means for encoding comprise: on-line means for encoding the random input vector through quantization in accordance with said search procedure in the codebook, said on-line encoding means comprising: means for transforming the input vector to provide a transform domain vector having a set of eigenvectors associated therewith; means for determining a surface vector nearest to said transform domain vector on said principal axis; means for determining a distance value providing the distortion between said transform domain vector and said surface vector, said distance value being defined as the Euclidean distance between said vectors and being the Minimum Mean Square Error (MMSE) distortion criteria; means for determining a codebook contiguous sub-group range having contained therewithin codevectors and being bounded by a hypersphere having a k-dimensional radius defined as the square root of said distance value; means for performing a full search over said contiguous sub-group range within said hypersphere to select the one of said codevectors nearest to said transform domain vector by determining the distortion therebetween in accordance with said MMSE criteria; and means for encoding said transform domain vector in accordance with said one selected codevector.
Claim 4
Dependent Claim
26 words
The apparatus of claim 2 wherein said means for transforming the input vector to provide said transform domain vector is provided by a Karhunen-Loewe Transform (KLT).
Claim 5
Dependent Claim
27 words
The apparatus of claim 2 wherein said means for transforming the input vector to provide said transform domain vector is provided by a discrete cosine transform (DCT).
Claim 6
Dependent Claim
33 words
The apparatus of claim 1 wherein said search procedure is conducted over said contiguous sub-group range in said codebook by comparison between the input vector and the codevector to determine the proper coding.
Claim 7
Dependent Claim
27 words
The apparatus of claim 2 wherein said hypersphere is defined as a relatively small k-dimensional sub-space centered around the input vector and containing the best matching codevector.
Claim 8
Dependent Claim
52 words
The apparatus of claim 2 wherein said means for determining said surface vector nearest to said transform domain vector on the principal axis p operates in accordance with the following relation: Z.sub.s =(Z.sub.tp -Z.sub.sp).sup.2 ≦(Z.sub.tp -Z.sub.np).sup.2 1≦n≦N where Z s is the surface vector and Z t is the transform domain vector.
Claim 9
Dependent Claim
28 words
The apparatus of claim 7 wherein said principal axis search for said surface vector is by means of a binary search of the order of Log 2 N.
Claim 10
Dependent Claim
39 words
The apparatus of claim 2 wherein said means for determining the distance value providing the distortion between said transform domain vector Z t and said surface vector Z s applies the Euclidean distance in accordance with the relation: ##EQU2##
Claim 11
Dependent Claim
61 words
The apparatus of claim 2 wherein said means for determining said codebook contiguous sub-group range operates such that codevectors Z j contained therewithin are bounded by high and low bounds determined by Zh, Zl where: Z.sub.hp <Z.sub.tp +r.sub.p <Z.sub.(h+1)p ; and Z.sub.(l-1)p <Z.sub.tp -r.sub.p <Z.sub.lp thereby defining a hypersphere having a k-dimensional radius r p defined as: r.sub.p =SQRT (d(Z.sub.t, Z.sub.s)).
Claim 12
Dependent Claim
116 words
The apparatus of claim 2 wherein there is provided, in recursive fashion, a combined operation of the plurality of said means for determining said surface vector, means for determining said distance value, means for determining said codebook subgroup range in the hypersphere and means for performing said full search over the sub-group range within the hypersphere, such that each determination of a nearer codevector establishes it as the new nearest codevector, and initiates the repetition of said combined operation of the plurality of said means for determining the new hypersphere for the subsequent full search, wherein said means for determining said surface vector operates by substitution of the current surface vector for the new nearest codevector.
Claim 13
Independent Claim
274 words
A method for encoding speech represented by a random input vector having k components, said method comprising the steps of: pre-processing to provide off-line reorganization of a codebook having a set of reference vector patterns constituting codevectors with which the input vector is to be compared in a search procedure, said pre-processing step comprising the steps of: transforming each of said codebook codevectors to provide a transform domain representation of said codebook; determining a principal axis p having the largest variance in said codebook transform domain representation; and re-ordering said codebook codevectors according to their descending value on the p axis; and encoding the random input vector through on-line quantization in accordance with said search procedure in the codebook, said on-line encoding step comprising the steps of: transforming the input vector to provide a transform domain vector having a set of eigenvectors associated therewith; determining a surface vector nearest to said transform domain vector on said principal axis; determining a distance value providing the distortion between said transform domain vector and said surface vector, said distance value being defined as the Euclidean distance between said vectors and being the Minimum Mean Square Error (MMSE) distortion criteria; determining a codebook contiguous sub-group range having contained therewithin codevectors and being bounded by a hypersphere having a k-dimensional radius defined as the square root of said distance value; performing a full search over said contiguous sub-group range within said hypersphere to select the one of said codevectors nearest to said transform domain vector by determining the distortion therebetween in accordance with said MMSE criteria; and encoding said transform domain vector in accordance with said one selected codevector.
Claim 14
Independent Claim
274 words
A method for encoding speech represented by a random input vector having k components, said method comprising the steps of: pre-processing to provide off-line reorganization of a codebook having a set of reference vector patterns constituting codevectors with which the input vector is to be compared in a search procedure, said pre-processing step comprising the steps of: transforming each of said codebook codevectors to provide a transform domain representation of said codebook; determining a principal axis p having the largest variance in said codebook transform domain representation; and re-ordering said codebook codevectors according to their descending value on the p axis; and encoding the random input vector through on-line quantization in accordance with said search procedure in the codebook, said on-line encoding step comprising the steps of: transforming the input vector to provide a transform domain vector having a set of eigenvectors associated therewith; determining a surface vector nearest to said transform domain vector on said principal axis; determining a distance value providing the distortion between said transform domain vector and said surface vector, said distance value being defined as the Euclidean distance between said vectors and being the Minimum Mean Square Error (MMSE) distortion criteria; determining a codebook contiguous sub-group range having contained therewithin codevectors and being bounded by a hypersphere having a k-dimensional radius defined as the square root of said distance value; performing a full search over said contiguous sub-group range within said hypersphere to select the one of said codevectors nearest to said transform domain vector by determining the distortion therebetween in accordance with said MMSE criteria; and encoding said transform domain vector in accordance with said one selected codevector.
Claim 15
Dependent Claim
28 words
The method of claim 12 wherein said on-line encoding step is performed by a source coder in a communication system providing optimal vector quantization and reducing computational complexity.
Claim 16
Dependent Claim
26 words
The method of claim 12 wherein said step of transforming the input vector to provide said transform domain vector is performed by a Karhunen-Loewe Transform (KLT).
Claim 17
Dependent Claim
27 words
The method of claim 12 wherein said step of transforming the input vector to provide said transform domain vector is performed by a discrete cosine transform (DCT).
Claim 18
Dependent Claim
33 words
The method of claim 12 wherein said search procedure is conducted over said contiguous sub-group range in said codebook by comparison between the input vector and the codevector to determine the proper coding.
Claim 19
Dependent Claim
27 words
The method of claim 12 wherein said hypersphere is defined as a relatively small k-dimensional sub-space centered around the input vector and containing the best matching codevector.
Claim 20
Dependent Claim
50 words
The method of claim 12 wherein said surface vector determination nearest to said transform domain vector on the principal axis p is performed in accordance with the following relation: Z.sub.s =(Z.sub.tp -Z.sub.sp).sup.2 ≦(Z.sub.tp -Z.sub.np).sup.2 1≦n≦N where Z s is the surface vector and Z t is the transform domain vector.
Claim 21
Dependent Claim
27 words
The method of claim 18 wherein said principal axis search for said surface vector is performed as a binary search of the order of Log 2 N.
Claim 22
Dependent Claim
36 words
The method of claim 12 wherein said distance value determination providing the distortion between said transform domain vector Z t and said surface vector Z s applies the Euclidean distance in accordance with the relation: ##EQU3##
Claim 23
Dependent Claim
57 words
The method of claim 12 wherein said codebook contiguous sub-group range determination defines codevectors Z j contained therewithin which are bounded by high and low bounds determined by Zh, Zl where: Z.sub.hp <Z.sub.tp +r.sub.p <Z.sub.(h+1)p ; and Z.sub.(l-1)p <Z.sub.tp -r.sub.p <Z.sub.lp thereby defining a hypersphere having a k-dimensional radius r p defined as: r.sub.p =SQRT (d(Z.sub.t, Z.sub.s)).
Claim 24
Dependent Claim
111 words
The method of claim 12 wherein there is provided, in recursive fashion, a combined operation of the plurality of said steps of determining said surface vector, determining said distance value, determining said codebook sub-group range in the hypersphere and performing said full search over the sub-group range within the hypersphere, such that each determination of a nearer codevector establishes it as the new nearest codevector, and initiates the repetition of said combined operation of the plurality of said steps for determining the new hypersphere for the subsequent full search, wherein said step of determining said surface vector is performed by substitution of the current surface vector for the new nearest codevector.
References Cited (Backward Citations)
US3981443A
Cited
US4270025A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-03-05 | 1993-09-04 | 1994-03-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-03-05 | 1997-09-04 | 1998-03-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-03-05 | 2001-09-04 | 2002-03-06 | $7700.00 | Window Closed / Lapsed |