Methods and apparatuses for variable dimension vector quantization

A method for codebook optimization, comprising:

• (A) collecting a training data set, wherein the training data set includes at least one input vector xk, wherein each of the at least one input vector xk includes at least one input vector element xk,j and a variable input vector dimension N(Tk);
• (B) defining a codebook, wherein the codebook includes a plurality of codevectors;
• (C) defining a partition rule;
• (D) defining a distortion measure d(xk,C(Tk)yi) for the partition rule;
• (E) finding a plurality of current optimum codevectors yi corresponding to the plurality of codevectors, wherein each of the plurality of current optimum codevectors yi includes at least one current optimum codevector element yi,m;
• (F) updating the plurality of current optimum codevectors yi using gradient-descent to create a plurality of new optimum codevectors yi;
• (G) determining whether an optimization criterion has been met;
• wherein if the optimization criterion has not been met, repeating updating the codebook with the new optimum codevectors and steps (E), (F) and (G) until it is determined in step (G) that the optimization criterion has been met;
• wherein if the optimization criterion has been met, designating the plurality of current optimum codevectors as the optimum codevectors.

A variable dimension vector quantization procedure for mapping an harmonic magnitude vector xk to one of at least one codevectors yi, wherein the harmonic magnitude vector includes at least one actual codevector element and a variable harmonic magnitude vector dimension N(Tk);

• and wherein the at least one codevector yi includes a codevector dimension Nv, the variable dimension vector quantization procedure comprising:
• extracting an actual codevector ui from each of the at least one codevectors yi in the codebook, including for each of the at least one codevectors yi:
• defining an index relationship, including:
• calculating a codevector index INDEX(T,j) according to an interpolation index relationship;
• and
• determining whether the codevector index is an integer;
• wherein if the codevector index is an integer, defining the index relationship according to a known index relationship;
• and wherein if the codevector index is not an integer, defining the index relationship according to the interpolation index relationship;
• and
• determining the actual codevector ui as a function of the index relationship including determining the at least one actual codevector element, wherein if the index relationship is the known index relationship, the at least one actual codevector element is determined as a function of the known index relationship;
• and wherein if the index relationship is the interpolation index relationship, the at least one actual codevector element is determined by an interpolation of a first and a second adjacent codevector elements;
• computing a distortion between the harmonic magnitude vector and each actual codevector wherein an actual codevector with which the distortion is minimized is designated as an optimum actual codevector;
• and
• quantizing the harmonic magnitude vector to the codevector from which the optimum actual codevector was extracted.

A method for creating an optimum partition for a codebook, wherein the codebook includes at least one codevector yi, wherein each of the at least one codevectors yi includes a codevector dimension Nv and at least one codevector element yi,m, comprising:

• (A) collecting a training data set, wherein the training data set comprises a plurality of input vectors, wherein each input vector is denoted xk and includes a variable training vector dimension N(Tk);
• (B) defining a partition rule;
• (C) defining a distortion measure for the partition rule, wherein the distortion measure defines an average distortion;
• and
• (D) finding a nearest codevector for each of the plurality of input vectors using an interpolation index relationship.

A method for harmonic coding that produces an encoded bit-stream from an input signal, comprising:

• determining at least one linear prediction coefficient for the input signal s[n] using linear prediction analysis;
• producing an excitation signal u[n] using the at least one linear prediction coefficient and the input signal;
• determining at least one pitch period Tk and at least one harmonic magnitude xk of the excitation signal u[n], wherein the at least one harmonic magnitude xk includes at least one harmonic magnitude element xk,j and a variable harmonic magnitude dimension N(Tk);
• determining other parameters using the linear prediction coefficients;
• and
• quantizing the other parameters, the pitch period and the at least one harmonic magnitude xk to produce an encoded bit-stream, wherein the at least one harmonic magnitude is quantized using an improved variable dimension vector quantization procedure.

A computer readable storage medium storing computer readable program code for extracting an actual codevector from a codevector, the computer readable program code comprising:

• data encoding a codevector;
• and
• a computer code implementing a method for extracting an actual codevector from a codevector in response to an harmonic magnitude vector, wherein the method for extracting an actual codevector includes:
• defining an index relationship, including:
• calculating a codevector index according to an interpolation index relationship;
• and
• determining whether the codevector index is an integer;
• wherein if the codevector index is an integer, defining the index relationship according to a known index relationship;
• and wherein if the codevector index is not an integer, defining the index relationship according to an interpolation index relationship;
• and
• determining the actual codevector as a function of the index relationship including determining the at least one actual codevector element;
• wherein if the index relationship is the known index relationship, the at least one actual codevector element is determined as a function of the known index relationship;
• and wherein if the index relationship is the interpolation index relationship, the at least one actual codevector element is determined by an interpolation of a first and a second adjacent codevector element.

A computer readable storage medium storing computer readable program code for mapping a harmonic magnitude vector Xk to one of at least one codevector yi, wherein the harmonic magnitude vector includes a variable harmonic magnitude vector dimension N(Tk) and the at least one codevector yi includes a codevector dimension Nv, the computer readable program code comprising:

• data encoding a codebook wherein the codebook includes the at least one codevector yi, wherein each of the at least one codevector yi includes at least one codevector element yi,m;
• and
• a computer code implementing a variable dimension vector quantization procedure, wherein the variable dimension vector quantization procedure includes:
• extracting an actual codevector ui from each of the at least one codevectors yi in the codebook, including for each of the at least one codevectors yi:
• defining an index relationship, including:
• calculating a codevector index INDEX(T,j) according to an interpolation index relationship;
• and
• determining whether the codevector index is an integer;
• wherein if the codevector index is an integer, defining the index relationship according to a known index relationship;
• and wherein if the codevector index is not an integer, defining the index relationship according to the interpolation index relationship;
• and
• determining the actual codevector ui as a function of the index relationship including determining the at least one actual codevector element, wherein if the index relationship is the known index relationship, the at least one actual codevector element is determined as a function of the known index relationship;
• and wherein if the index relationship is the interpolation index relationship, the at least one actual codevector element is determined by an interpolation of a first and a second adjacent codevector;
• computing a distortion between the harmonic magnitude vector and each actual codevector wherein an actual codevector with which the distortion is minimized is designated as an optimum actual codevector;
• and
• quantizing the harmonic magnitude vector to the codevector from which the optimum actual codevector was extracted.

A computer readable storage medium storing computer readable program code for creating an optimum partition, the computer readable program code comprising:

• data encoding a codebook and a training data set;
• wherein the codebook includes the at least one codevector yi, wherein the at least one codevector yi includes at least one codevector element yi,m;
• and wherein the training data asset includes a plurality of input vectors;
• and
• a computer code implementing a method for creating an optimum partition in response to the plurality of input vectors, wherein the method for creating an optimum partition includes:
• (A) collecting a training data set, wherein the training data set comprises a plurality of input vectors, wherein each input vector is denoted xk and includes a variable training vector dimension N(Tk);
• (B) defining a partition rule;
• (C) defining a distortion measure for the partition rule, wherein the distortion measure defines an average distortion;
• and
• (D) finding a nearest codevector for each of the plurality of input vectors using an interpolation index relationship.

A computer readable storage medium storing computer readable program code for optimizing a codebook, comprising:

• data encoding a codebook and a training data set;
• wherein the codebook includes at least one codevector yi and a partition, wherein each of the at least one codevectors yi includes a codebook element dimension Nv and at least one codebook element yi,m;
• and wherein the training data set includes a plurality of input vectors;
• and
• a computer code implementing a method for codebook optimization in response to the plurality of input vectors, wherein the method for codebook optimization includes:
• (A) collecting a training data set, wherein the training data set includes at least one input vector xk, wherein each of the at least one input vector xk includes at least one input vector element xk,j and a variable input vector dimension N(Tk);
• (B) defining a codebook, wherein the codebook includes a plurality of codevectors;
• (C) defining a partition rule;
• (D) defining a distortion measure d(xk,C(Tk)yi) for the partition rule;
• (E) finding a plurality of current optimum codevectors yi corresponding to the plurality of codevectors, wherein each of the plurality of current optimum codevectors yi includes at least one current optimum codevector element yi,m;
• (F) updating the plurality of current optimum codevectors yi using gradient-descent to create a plurality of new optimum codevectors yi;
• (G) determining whether an optimization criterion has been met;
• wherein if the optimization criterion has not been met, repeating updating the codebook with the new optimum codevectors and steps (E), (F) and (G) until it is determined in step (G) that the optimization criterion has been met;
• wherein if the optimization criterion has been met, designating the plurality of current optimum codevectors as the optimum codevectors.

A computer readable storage medium storing computer readable program code for harmonic coding of an input signal, comprising:

• data encoding a codebook, wherein the codebook includes at least one codevector yi and wherein each of the at least one codevectors yi includes a codevector magnitude Nv and at least one codevector element yi,m;
• and
• a computer code implementing a method for harmonic coding in response to the input signal, wherein the method for harmonic coding includes:
• determining at least one linear prediction coefficient for the input signal s[n] using linear prediction analysis;
• producing an excitation signal u[n] using the at least one linear prediction coefficient and the input signal;
• determining at least one pitch period Tk and at least one harmonic magnitude xk of the excitation signal u[n], wherein the at least one harmonic magnitude xk includes at least one harmonic magnitude element xk,j and a variable harmonic magnitude dimension N(Tk);
• determining other parameters using the linear prediction coefficients;
• and
• quantizing the other parameters, the pitch period and the at least one harmonic magnitude xk to produce an encoded bit-stream, wherein the at least one harmonic magnitude is quantized using an improved variable dimension vector quantization procedure.

A variable dimension vector quantization device for mapping an harmonic magnitude vector xk to one of at least one codevectors yi, wherein the harmonic magnitude vector includes a variable harmonic magnitude vector dimension N(Tk) and the at least one codevectors yi includes a codevector dimension Nv, comprising:

• an interface unit for receiving the harmonic magnitude vector xk;
• a quantization unit coupled to the interface unit, wherein the quantization unit includes a memory and a processor coupled to the memory;
• wherein the memory stores the at least one codevector yi and a variable dimension vector quantization procedure;
• and wherein the processor, using the variable dimension vector quantization procedure and the at least one codevector yi communicated from the memory, extracts an actual codevector ui from each of the at least one codevectors yi, computes a distortion between the harmonic magnitude vector and designates the actual codevector with which the distortion is minimized as an optimum actual codevector, quantizes the harmonic magnitude vector to the codevector from which the optimum actual codevector was extracted to create a quantized harmonic magnitude vector, and communicates the quantized harmonic magnitude vector to the memory and/or the interface.

An optimum partition creation device for a codebook, wherein the codebook includes at least one codevector yi, wherein each of the at least one codevectors yi includes a codevector dimension Nv and at least one codevector element yi,m, comprising:

• an interface unit for receiving a training data set, a partition rule, and a distortion measure, wherein the training data set includes a plurality of input vectors, wherein the plurality of input vectors includes a variable training dimension N(Tk);
• and wherein the distortion measure defines an average distortion;
• and
• a partition creation unit coupled to the interface unit, wherein the partition creation unit includes a memory and a processor coupled to the memory unit;
• wherein the memory stores the at least one codevector yi, the distortion measure, the partition rule, and a method for creating an optimum partition for the codebook;
• and wherein the processor, using the method for creating the optimum partition for the codebook, the at least one codevector yi, the partition rule and the distortion measure communicated from the memory, finds the nearest codevector for each of the plurality of input vectors using an interpolation index relationship.

A codebook optimization device, wherein the codebook includes at least one codevector yi, wherein each of the at least one codevector yi includes at least one codevector element yi,m, wherein each of the at least one codevector elements includes a codevector element dimension Nv, wherein the codebook optimization device comprises:

• an interface unit for receiving a training data set, a partition rule and a distortion measure;
• wherein the training data set includes a plurality of input vectors, wherein the input vectors include a variable input vector dimension N(Tk);
• and
• a codebook optimization unit coupled to the interface unit, wherein the codebook optimization unit includes a memory and a processor coupled to the memory, wherein the memory stores the at least one codevector, the plurality of input vectors, the partition rule, the distortion measure, an optimization criterion, and an improved method for codebook optimization;
• and wherein the processor, using the at least one codevector, the partition rule, the distortion measure, the optimization criterion, the plurality of input vectors and the improved method for codebook optimization communicated to it by the memory in response to the plurality of input vectors:
• finds a current optimum codevector for each input vector;
• updates the current optimum codevectors using gradient-descent to create new optimum codevectors;
• determines whether the optimization criterion has been met, wherein if the optimization criterion has been met, repeats updating the codebook with the new optimum codevectors, finding a current optimum codevector for each input vector, updating the current optimum codevectors using gradient-descent to create new optimum codevectors, and determining whether the optimization criterion has been met, until the optimization criterion has been met;
• wherein if the optimization criterion has been met, designating the current optimum codevectors as the optimum codevectors.

An optimized harmonic coder for encoding an input signal s[n] as an encoded bit-stream, comprising:

• a linear prediction analysis device, wherein the linear prediction analysis device receives the input signal and produces a plurality of linear prediction coefficients;
• an other processing device coupled to the linear prediction analysis device, wherein the other processing device produces at least one other parameter;
• an inverse filter defined by the plurality of LP coefficients;
• wherein the inverse filter receives the input signal, is coupled to the linear prediction analysis device receiving the linear prediction coefficients therefrom, and produces an excitation signal;
• a harmonic analysis device coupled to the inverse filter and receiving the excitation signal therefrom, wherein the harmonic analysis device produces a pitch period T and at least one harmonic magnitude xj, wherein the harmonic magnitude includes a variable harmonic dimension N(Tk);
• and
• a variable dimension vector quantizer coupled to the harmonic analysis device and the other processing device, wherein the variable dimension vector quantizer receives the pitch period T and the at least one harmonic magnitude xj from the harmonic analysis device, and receives the other parameters from the other processing device;
• wherein the variable dimension vector includes a codebook which includes at least one codevector yi and wherein the at least one codevector yi includes a codevector dimension Nv and at least one codebook element yi,m;
• and wherein the variable dimension vector quantizer quantizes the pitch period, the at least one other parameter and the at least one harmonic magnitude xj to produce the encoded bit-stream, wherein quantizing the at least one harmonic magnitude xj, includes:
• determining at least one linear prediction coefficient for the input signal s[n] using linear prediction analysis;
• producing an excitation signal u[n] using the at least one linear prediction coefficient and the input signal;
• determining at least one pitch period Tk and at least one harmonic magnitude xk of the excitation signal u[n], wherein the at least one harmonic magnitude xk includes at least one harmonic magnitude element xk,j and a variable harmonic magnitude dimension N(Tk);
• determining other parameters using the linear prediction coefficients;
• and
• quantizing the other parameters, the pitch period and the at least one harmonic magnitude xk to produce an encoded bit-stream, wherein the at least one harmonic magnitude is quantized using an improved variable dimension vector quantization procedure.