US 4,907,276 A · Fast search method for vector quantizer communication and pattern recognition systems

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.

Claims22

Dependent claims

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.

4 more elements

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.

11 more elements

Dependencies are inferred from the claim text.

Fast search method for vector quantizer communication and pattern recognition systems

Life of this patent

Fast search method for vector quantizer communication and pattern recognition systems

Life of this patent

Abstract

Claims22