Sub-partitioned vector quantization of probability density functions

Claim 3

The method of claim 1 wherein the step of vector quantizing the subpartitioned packets comprises the following steps: a) selecting an initial set of at least two trial cluster centroids; b) assigning packets to the trial cluster centroids by computing the distance between a given packet and the trial cluster centroids and assigning the given packet to the closest trial cluster centroid; c) computing an actual cluster centroid for each cluster corresponding to a trial centroid; d) computing an overall error value using the actual cluster centroids and if greater than a prescribed value selecting a new set of trial cluster centroids and returning to step (b), otherwise proceed to step (e); e) splitting the clusters corresponding to the actual cluster centroids of step (c) by selecting two or more trial cluster centroids for each actual cluster centroid and returning to step (b) unless a prescribed number of clusters has been created.

Claim 4

The method of claim 2 wherein the step of assigning packets to the trial cluster centroids by computing the distance between a given packet and the trial centroids is computed in probability-weighted-log-probability space.

Claim 5

The method of claim 2 wherein the step of splitting clusters is based on a weighted-log-probability space.

Claim 6

The method of claim 2 wherein the step of splitting clusters uses a binary splitting algorithm in weighted-log-probability space.

Claim 7

The method of claim 2 wherein the step of assigning packets to the trial cluster centroids by computing the distance is computed in log-probability space.

Claim 8

The method of claim 2 wherein the step of splitting clusters is based on a log-probability space.

Claim 9

The method of claim 1 further comprising steps for retrieving a packet specified by a packet index from a subpartitioned vector quantized (SVQ) memory for HMM log-pdfs, the SVQ memory comprising an address translation table and a SVQ vector table, the further steps comprising: a) addressing the address translation table by the packet index and retrieving a corresponding SVQ encoding index; and b) addressing the SVQ vector table by using the corresponding SVQ encoding index and retrieving a SVQ encoding vector corresponding to the SVQ encoding index.

Claim 10

The method of claim 8 further comprising a step for retrieving a HMM log-pdf value corresponding to a specified log-pdf element index of a specified packet index, the step comprising selecting the element of the SVQ encoding vector indicated by the specified log-pdf element index.

Claim 11

A subpartitioned vector quantization memory compression storage and retrieval system for HMM log-pdfs, addressable by a read address that includes a packet index corresponding to a packet location in uncompressed memory, comprising: a) an address translation table memory for storing and outputting SVQ encoding vector indices at an output port, each addressable through a read address port by a corresponding packet index; and b) a vector table memory for storing a set of SVQ encoding vectors, addressable by a corresponding encoding vector index, with a read address port connected to the output of the address translation table memory, and an output port for providing the encoded vector corresponding to a packet specified by the packet index.

Claim 12

A subpartitioned vector quantization memory compression storage and retrieval system for HMM log-pdfs, addressable by a read address that includes a packet index corresponding to a packet location in uncompressed memory, comprising: a) an address translation table memory for storing and outputting SVQ encoding vector indices at an output port, each addressable through a read address port by a corresponding packet index; and b) a vector table memory for storing a set of SVQ encoding vectors, addressable by a corresponding encoding vector index, with a read address port connected to the output of the address translation table memory, and an output port for providing the encoded vector corresponding to a packet specified by the packet index.

Claim 13

The memory .compression system of claim 10 further comprising means for selecting a specific element from the encoded vector corresponding to a packet specified by the packet index.

Claim 14

The memory compression system of claim 11 wherein the externally provided element index is a set of lower order bits in the read address supplied to the memory compression storage and retrieval system.

Claim 17

The method of claim 13 further comprising the step of converting the elements of a set of discrete probability density functions (pdfs), each set with an equal number of prescribed elements, by substituting the logarithm of the elements for forming a set of log-probability density functions (log-pdfs).

Claim 18

The method of claim 13 wherein the step of vector quantizing the subpartitioned packets comprises the following steps: a) selecting an initial set of at least two trial cluster centroids; b) assigning packets to the trial cluster centroids by computing the distance between a given packet and the trial cluster centroids and assigning the given packet to the closest trial cluster centroid; c) computing an actual cluster centroid for each cluster corresponding to a trial cluster centroid; d) computing an overall error value using the actual cluster centroids and if greater than a prescribed value selecting a new set of trial cluster centroids and returning to step (b), otherwise proceed to step (e); e) splitting the clusters corresponding to the actual cluster centroids of step (c) by selecting two or more trial cluster centroids for each actual cluster centroid and returning to step (b) unless a prescribed number of clusters has been created.

Claim 19

The method of claim 15 wherein the step of assigning packets to the trial cluster centroids by computing the distance between a given packet and the trial centroids is computed in probability-weighted-log-probability space.

Claim 20

The method of claim 15 wherein the step of splitting clusters is based on a weighted-log-probability space.

Claim 21

The method of claim 15 wherein the step of splitting clusters uses a binary splitting algorithm in weighted-log-probability space.

Claim 22

The method of claim 15 wherein the step of assigning packets to the trial cluster centroids by computing the distance is computed in log-probability space.

Claim 23

The method of claim 15 wherein the step of splitting clusters is based on a log-probability space.

Claim 24

The method of claim 13 further comprising steps for retrieving a packet specified by a packet index from a subpartitioned vector quantized (SVQ) memory for log-probability density functions (log-pdfs), the SVQ memory comprising an address translation table and a SVQ vector table, the further steps comprising: a) addressing the address translation table by the packet index and retrieving a corresponding SVQ encoding index; and b) addressing the SVQ vector table by using the corresponding SVQ encoding index and retrieving a SVQ encoding vector corresponding to the SVQ encoding index.

Claim 25

The method of claim 21 further comprising a step for retrieving a log-probability density function (log-pdf) value corresponding to a specified log-pdf element index of a specified packet index, the step comprising selecting the element of the SVQ encoding vector indicated by the specified log-pdf element index.

Claim 26

A speech recognition system comprising: a) a speech transducer for generating an electrical signal representative of the input acoustical speech signal; b) an analog-to-digital converter for scalar quantization of the electrical signal at its output, having an input port connected to the output of the speech transducer; c) a speech signal feature extraction processor connected to the output of the analog-to-digital converter for extracting a speech feature vector; d) a vector quantizer having an input connected to the output of the feature extraction processor for producing a vector quantized speech feature vector at an output; e) a phoneme probability processor connected to the output of the vector quantifier for operating on the vector quantized speech feature vector and computing a set of probabilities that a given hidden Markov model produced the speech feature vector based on a prescribed set of hidden Markov models; f) a hidden Markov model memory for storing a prescribed set of hidden Markov models which is implemented as a sub-partitioned vector quantization storage and retrieval system, addressable by the phoneme probability processor and for producing at an output phone probabilities, the output connected to the phoneme probability processor; and g) a search engine for searching for a candidate sentence, given the phone probabilities, and for outputting a word sequence identifier for the most probable word sequence of the candidate sentence.

Claim 27

A speech recognition system comprising: a) a speech transducer for generating an electrical signal representative of the input acoustical speech signal; b) an analog-to-digital converter for scalar quantization of the electrical signal at its output, having an input port connected to the output of the speech transducer; c) a speech signal feature extraction processor connected to the output of the analog-to-digital converter for extracting a speech feature vector; d) a vector quantizer having an input connected to the output of the feature extraction processor for producing a vector quantized speech feature vector at an output; e) a phoneme probability processor connected to the output of the vector quantifier for operating on the vector quantized speech feature vector and computing a set of probabilities that a given hidden Markov model produced the speech feature vector based on a prescribed set of hidden Markov models; f) a hidden Markov model memory for storing a prescribed set of hidden Markov models which is implemented as a sub-partitioned vector quantization storage and retrieval system, addressable by the phoneme probability processor and for producing at an output phone probabilities, the output connected to the phoneme probability processor; and g) a search engine for searching for a candidate sentence, given the phone probabilities, and for outputting a word sequence identifier for the most probable word sequence of the candidate sentence.

Claim 28

The speech recognition system of claim 23 wherein the speech feature extraction processor comprises: (a) a linear predictive coding processing for producing at output a set of linear predictive coding coefficients representative of the acoustic speech signal with its input connected to the analog-to-digital converter output. (b) a cepstral processor with it input connected to the linear predictive encoding processor output for producing a cepstral vector with a set of coefficients representative of the linear predictive coding coefficients.

Claim 29

The speech recognition system of claim 23 wherein the system further comprises a multiplicity of vector quantizers, one for each distinct feature vector.