System for selecting best fit vector code in vector quantization encoding
First Claim
1. A system for deriving the best fit codebook vector associated with an input vector having "r" dimensions (input vector components) comprising, in combination:
- (a) memory means for storing codebook vectors wherein each particular codebook vector includes precalculated error data representing the error between each possible input vector component and said each particular codebook vector, said memory means receiving said "r" input vector components;
(b) sequencing means for effectuating an index search of said memory means to develop a series of n vector component error signals where each error signal represents the difference between the indexed codebook vector and the input vector;
(c) comparison-selection means for comparing each presently indexed vector component error signal with the previously indexed error signal to latch the smaller-valued of minimal error signal in a latching means during the period of the said index search said comparison-selection means including;
(c1) latching means for holding the said minimal valued error signal after each index search of said sequencing means and for latching the count number of that index search which corresponds to the minimal valued error signal which occurred during the search sequence.
1 Assignment
0 Petitions
Accused Products
Abstract
A system and apparatus for encoding a set of input vector components by initiating a sequential search through a codebook memory to put out a series of associated error code vectors which can be compared in sequence over a period of time in order to select the minimum error code vector (best fit). A clocking-sequencing means enables an output latch to hold (after termination of the sequence period) the index number which represents the particular error code vector presently having the minimum distortion. Each new set of input vector components will be sequenced to search for the minimum error code vector (and index) for that particular set of input vector components.
305 Citations
14 Claims
-
1. A system for deriving the best fit codebook vector associated with an input vector having "r" dimensions (input vector components) comprising, in combination:
-
(a) memory means for storing codebook vectors wherein each particular codebook vector includes precalculated error data representing the error between each possible input vector component and said each particular codebook vector, said memory means receiving said "r" input vector components; (b) sequencing means for effectuating an index search of said memory means to develop a series of n vector component error signals where each error signal represents the difference between the indexed codebook vector and the input vector; (c) comparison-selection means for comparing each presently indexed vector component error signal with the previously indexed error signal to latch the smaller-valued of minimal error signal in a latching means during the period of the said index search said comparison-selection means including; (c1) latching means for holding the said minimal valued error signal after each index search of said sequencing means and for latching the count number of that index search which corresponds to the minimal valued error signal which occurred during the search sequence. - View Dependent Claims (2, 3, 4, 5)
-
-
6. Apparatus for determining which codebook vector in a codebook most closely approximates an input vector, said apparatus comprising:
-
(a) memory means having "r" memory units, where "r" is the dimensionality of the input vector, for storing sub-sized codebook vectors which include precalculated error data for each of said vectors which represent error deviation between each said sub-sized codebook vectors and each possible input vector, said memory means including receiving means for receiving an input vector; (b) sequencing means for providing an index search of said memory means for each said input vector to provide an output signal for each index search during a series of n index searches where n is a number equal or greater than "O" and equal to or less than 2k-1 where k is a whole number, said output signal representing the precalculated error data for a given codebook vector in a given index search; (c) summation means for adding the outputs of each one of said "r" memory units after each index search to establish the total error deviation on each index search; (d) comparison-selection means to receive n series of total error deviations during said n index searches and to select that particular total error deviation which presented the minimal error value. - View Dependent Claims (7, 8, 9)
-
-
10. An apparatus for selecting the best fit codebook vector to an input vector comprising:
-
(a) means to search through codebook vectors in a memory means, said search providing a series of n search steps wherein each search step generates a total error deviation signal to a determination means; (b) said memory means holding a plurality of said codebook vectors where each codebook vector includes precalculated error deviation data between each said codebook vector and all possible input vectors; (c) said determination means operating to select the minimal-valued total error deviation signal which occured in said series of n search steps.
-
-
11. Apparatus for compressing input vector data through use of a vector codebook by selecting a codebook symbol "n" representing the vector having the closest match to said input vector by a predetermined distortion measure, said apparatus comprising:
-
(a) memory means having a table of codebook vectors (X) defined by a vector-quantization algorithm, said memory means including; (a1) "r" tables of component error terms (Pi -Xni) for all possible input vectors, said error terms showing the distortion between each possible input vector component (Pi) and each code vector component (Xni); (a2) means to output a plurality of specific error-terms, one for each input vector component, to a summation circuit means; (b) summation circuit means for adding said plurality of output component error terms and providing a summation output signal which represents a vector error signal, to a comparison-selection means; (c) comparison-selection means for selecting the codebook vector index "n" representing the closest vector (least distortion) to the original input vector.
-
-
12. An encoder apparatus for vector quantization encoding for selecting a codebook vector index which most closely matches, by a predefined distortion measure, an input vector, comprising, in combination:
-
(a) a memory means including a plurality of "r" memories wherein each one of said "r" memories receives an input of one vector-component of a multidimensional vector, each of said "r" memories including; (a1) a codebook of 2k of precalculated component error terms for all possible input vector components to that memory, where 2k equals the number of vector codebook entries; (a2) said error terms having been calculated by the least means squares method formula; (a3) means to output a component error signal to a summation device means; (b) clock timing means for sequencing said memory means in a search mode to find the closest matching codebook vector signal; (c) said summation device means for receiving and summing each component error signal from each of said memories for each of said clock sequences to provide a vector error signal for each index; (d) a comparison-selection means for receiving each vector error signal for each clock sequence, and selecting that vector error signal for that particular clock sequence which represents the best fit to the input vector.
-
-
13. An operating system for a vector quantizer encoder comprising:
-
(a) a plurality of "r" memories wherein each memory receives an input vector-component of a vector having "r" components, each of said memories including; (a1) a codebook component memory having precalculated error measurement data which stores the distortion error for each possible input vector component for each possible vector codebook component signal from said memory, said memory transmitting a component error signal of "m" bits to a summation means; (b) summation means for simultaneously adding up said component error signals from each of said "r" memories for each set of provided input vector components in a given index number; (c) counting-indexing means to establish a sequence of indices of periods where there is counted one index count per time period to provide searching indices of each codebook component and each output code word to a latching means; (d) means to compare each vector error signal for each index number with the previously latched minimum error signals of each set of minimum error signals to establish a new vector error minimum signal and associated index number "n".
-
-
14. A method for operation of a vector quantizer encoder comprising the steps of:
-
(a) inputting a set of "r" input vector component signals into a set of "r" memory units;
said "r" memory units, said error data representing the error (distortion) between each possible input vector component signal and each one of a set of codebook vectors defined by a vector quantization codebook design algorithm;(c) sequencing each codebook vector component of said "r" memory units simultaneously to operate as a search index of a vector codebook wherein each of said "r" memory units outputs a vector component error signal representing a given codebook index; (d) summing the vector component error signals to provide the total vector error for a given codebook index; (e) comparing the previously latched minimum (distortion) error signal with the presently indexed error signal, and providing clock pulses to first and second latches if the presently indexed error signal is smaller than the previously latched minimum error signal; (f) latching into said first latch, the new minimum error signal if it is smaller than the previously latched error signal; (g) latching, into said second latch, a new index code associated with the presently latched minimum error signal in said first latch which represents the index of the vector codebook entry presently being read.
-
Specification