Single-codebook vector quantization for multiple-rate applications

• US 20070055509A1
• Filed: 08/29/2005
• Published: 03/08/2007
• Est. Priority Date: 08/29/2005
• Status: Active Grant

• Current Assignee: Nokia Technologies Oy (Nokia Corporation)
• Original Assignee: Nokia Corporation
• Inventors: Vasilache, Adriana, Ramo, Anssi
• Granted Patent: US 7,587,314 B2
• Time in Patent Office: Days
• US Class Current: 704/229
• CPC Class Codes: G10L 19/24 Variable rate codecs, e.g. for generating different qualities using a scalable representation such as hierarchical encoding or layered encoding
• CPC Class Codes: G10L 2019/0004 Design or structure of the codebook
• CPC Class Codes: G10L 2019/0007 Codebook element generation
• CPC Class Codes: H03M 7/3082 Vector coding for television signals, see H04N19/94

Abstract

This invention relates to a method, a device and a software application product for N-level quantization of vectors, wherein N is selectable prior to said quantization from a set of at least two pre-defined values that are smaller than or equal to a pre-defined maximum number of levels M. A reproduction vector for each vector is selected from an N-level codebook of N reproduction vectors that are, for each N in said set of at least two pre-defined values, represented by the first N reproduction vectors of the same joint codebook of M reproduction vectors. The invention further relates to a method, a device and a software application product for retrieving reproduction vectors for vectors that have been N-level quantized, to a system for transferring representations of vectors, to a method, a device and a software application product for determining a joint codebook, and to such a joint codebook itself.

Claims

1. A method for N-level quantization of vectors, wherein N is selectable prior to said quantization from a set of at least two pre-defined values that are smaller than or equal to a pre-defined maximum number of levels M, said method comprising:

selecting a reproduction vector for each vector from an N-level codebook of N reproduction vectors that are, for each N in said set of at least two pre-defined values, represented by the first N reproduction vectors of the same joint codebook of M reproduction vectors.

2. The method according to claim 1, wherein N=2ⁿ and M=2^m holds, with n and m being integer values.

3. The method according to claim 1, wherein each reproduction vector in said N-level codebook is identified by an n-bit binary word.

4. The method according to claim 1, wherein said vectors comprise parameters related to Linear Predictive Coding of an data sequence.

5. The method according to claim 1, wherein said step of selecting is performed by a portable communication device.

6. A device for N-level quantization of vectors, wherein N is selectable prior to said quantization from a set of at least two pre-defined values that are smaller than or equal to a pre-defined maximum number of levels M, said device comprising:

means for selecting a reproduction vector for each vector from an N-level codebook of N reproduction vectors that are, for each N in said set of at least two pre-defined values, represented by the first N reproduction vectors of the same joint codebook of M reproduction vectors.

7. The device according to claim 6, wherein said device is a portable communication device.

8. A software application product, comprising a storage medium having a software application for N-level quantization of vectors embodied therein, wherein N is selectable prior to said quantization from a set of at least two pre-defined values that are smaller than or equal to a pre-defined maximum number of levels M, said software application comprising:

program code for selecting a reproduction vector for each vector from an N-level codebook of N reproduction vectors that are, for each N in said set of at least two pre-defined values, represented by the first N reproduction vectors of the same joint codebook of M reproduction vectors.

9. A method for retrieving reproduction vectors for vectors that have been N-level quantized, wherein N is selectable prior to said quantization of said vectors from a set of at least two pre-defined values that are smaller than or equal to a pre-defined maximum number of levels M, said method comprising:

receiving an identifier of a reproduction vector that has been selected for a vector in said quantization; and

retrieving, based on said identifier, said reproduction vector from an N-level codebook of N reproduction vectors that are, for each N in said set of at least two pre-defined values, represented by the first N reproduction vectors of the same joint codebook of M reproduction vectors.

10. A device for retrieving reproduction vectors for vectors that have been N-level quantized, wherein N is selectable prior to a quantization of said vectors from a set of at least two pre-defined values that are smaller than or equal to a pre-defined maximum number of levels M, said device comprising:

means for receiving an identifier of a reproduction vector that has been selected for a vector in said quantization; and

means for retrieving, based on said identifier, said reproduction vector from an N-level codebook of N reproduction vectors that are, for each N in said set of at least two pre-defined values, represented by the first N reproduction vectors of the same joint codebook of M reproduction vectors.

11. A software application product, comprising a storage medium having a software application for retrieving reproduction vectors for vectors that have been N-level quantized embodied therein, wherein N is selectable prior to a quantization of said vectors from a set of at least two pre-defined values that are smaller than or equal to a pre-defined maximum number of levels M, said software application comprising:

program code for receiving an identifier of a reproduction vector that has been selected for a vector in said quantization; and

program code for retrieving, based on said identifier, said reproduction vector from an N-level codebook of N reproduction vectors that are, for each N in said set of at least two pre-defined values, represented by the first N reproduction vectors of the same joint codebook of M reproduction vectors.

12. A system for transferring representations of vectors, comprising:

means for selecting a reproduction vector for each vector from an N-level codebook of N reproduction vectors, wherein N is selectable prior to said selecting from a set of at least two pre-defined values that are smaller than or equal to a pre-defined maximum number of levels M, and wherein said N reproduction vectors are, for each N in said set of at least two pre-defined values, represented by the first N reproduction vectors of a first joint codebook of M reproduction vectors;

means for transmitting an identifier of said selected reproduction vector via a transmission channel;

means for receiving said identifier; and

means for retrieving, based on said identifier, said reproduction vector from an N-level codebook of N reproduction vectors represented by the first N reproduction vectors of a second joint codebook of M reproduction vectors that equals said first codebook.

13. A method for determining a joint codebook of M reproduction vectors for use in an N-level quantization of vectors, wherein M is a pre-defined maximum number of levels, wherein N is selectable prior to said quantization from a set of at least two pre-defined values that are smaller than or equal to M, and wherein in said quantization, a reproduction vector for each vector is selected from an N-level codebook of N reproduction vectors that are, for each N in said set of at least two pre-defined values, represented by the first N reproduction vectors of said joint codebook, said method comprising:

generating said reproduction vectors by a training algorithm at least partially based on a plurality of training vectors; and

arranging said generated reproduction vectors in said joint codebook according to an arrangement algorithm so that for each N, the first N reproduction vectors in said joint codebook form an N-level codebook that allows for a small average distortion of said vectors when used in said quantization of said vectors.

14. The method according to claim 13, wherein N=2ⁿ and M=2^m holds, with n and m being integer values.

15. The method according to claim 14, comprising:

generating an initial codebook of M reproduction vectors by said training algorithm;

generating a 2-level codebook of 2 reproduction vectors by said training algorithm;

selecting those 2 reproduction vectors from said initial codebook that are most similar to said 2 reproduction vectors in said 2-level codebook;

copying said 2 selected reproduction vectors from said initial codebook to the first 2 positions in said joint codebook and deleting said 2 selected reproduction vectors from said initial codebook; and

repeating, for 1<

i≦

m, the following steps;

generating an I-level codebook of I=2ⁱ reproduction vectors by said training algorithm;

identifying those I/2 reproduction vectors from said I-level codebook that are most similar to said I/2 reproduction vectors already copied to said joint codebook;

for the remaining non-identified I/2 reproduction vectors in said I-level codebook, selecting those I/2 reproduction vectors from said initial codebook that are most similar to said remaining non-identified I/2 reproduction vectors; and

copying said I/2 selected reproduction vectors from said initial codebook to the next free positions in increasing sense in said joint codebook and deleting said I/2 selected reproduction vectors from said initial codebook.

16. The method according to claim 14, comprising:

generating a 2-level codebook of 2 reproduction vectors by said training algorithm;

copying said 2 reproduction vectors from said 2-level codebook to the first 2 positions in said joint codebook; and

repeating, for 1<

i≦

m, the following steps;

generating an I-level codebook of I=2ⁱ reproduction vectors by said training algorithm, wherein in said training algorithm, the I/2 reproduction vectors already copied to said joint codebook form the first part of a codebook of I reproduction vectors, which serves as an initialization of said I-level codebook generated by said training algorithm, and are assumed fixed throughout said training algorithm; and

copying the I/2 last reproduction vectors of said generated I-level codebook to the next free I/2 positions in increasing sense in said joint codebook.

17. The method according to claim 13, comprising:

generating an initial codebook of M reproduction vectors by said training algorithm based on a plurality of training vectors;

selecting, from said initial codebook, the two reproduction vectors that are most different to each other;

copying said two selected reproduction vectors from said initial codebook to the first two positions in said joint codebook and deleting said two selected reproduction vectors from said initial codebook; and

repeating, while said initial codebook is non-empty, the following steps;

selecting the reproduction vector from said initial codebook that is most different with respect to all reproduction vectors already copied to said joint codebook;

copying said selected reproduction vector from said initial codebook to the next free position in increasing sense in said joint codebook and deleting said selected reproduction vector from said initial codebook.

18. The method according to claim 13, comprising:

generating an initial codebook of M reproduction vectors by said training algorithm based on a plurality of training vectors;

selecting, from said initial codebook, the reproduction vector that is most similar to all of said training vectors;

copying said selected reproduction vector from said initial codebook to the first position in said joint codebook and deleting said selected reproduction vector from said initial codebook; and

repeating, while said initial codebook is non-empty, the following steps;

selecting the reproduction vector from said initial codebook that is most different with respect to all reproduction vectors already copied to said joint codebook;

copying said selected reproduction vector from said initial codebook to the next free position in increasing sense in said joint codebook and deleting said selected reproduction vector from said initial codebook.

19. The method according to claim 13, comprising:

generating an initial codebook of M reproduction vectors by said training algorithm;

repeating, while said initial codebook is non-empty, the following steps;

selecting those 2 reproduction vectors from said initial codebook that are most similar to each other;

copying the first of said two selected reproduction vectors from said initial codebook to the next free position, in decreasing sense starting from the last position, in said joint codebook and deleting said first of said two selected reproduction vectors from said initial codebook.

20. The method according to claim 13, wherein said set of at least two pre-defined values for N that are smaller than or equal to M contains K values N_i with i=1, . . . ,K and N_j−

1<

N_j≦

M for j=2, . . . , K, said method comprising;

generating an initial codebook of M reproduction vectors by said training algorithm based on a plurality of training vectors;

selecting, from said initial codebook, N₁ reproduction vectors so that a distortion of a codebook that contains said selected reproduction vectors with respect to all of said training vectors is minimum;

copying said selected reproduction vectors from said initial codebook to said joint codebook and deleting said selected reproduction vectors from said initial codebook; and

repeating, for each N_i with 1<

i≦

K, the following steps;

selecting, from said initial codebook, N_i-N<sub>i−

1</sub> reproduction vectors so that a distortion of a codebook that contains the N<sub>i−

1</sub> reproduction vectors already copied to said joint codebook and said selected reproduction vectors with respect to all of said training vectors is minimum; and

copying said selected reproduction vectors from said initial codebook to the next free positions in increasing sense in said joint codebook and deleting said selected reproduction vectors from said initial codebook.

21. A device for determining a joint codebook of M reproduction vectors for use in an N-level quantization of vectors, wherein M is a pre-defined maximum number of levels M, wherein N is selectable prior to said quantization from a set of at least two pre-defined values that are smaller than or equal to M, and wherein in said quantization, a reproduction vector for each vector is selected from an N-level codebook of N reproduction vectors that are, for each N in said set of at least two pre-defined values, represented by the first N reproduction vectors of said joint codebook, said device comprising:

means for generating said reproduction vectors by a training algorithm at least partially based on a plurality of training vectors; and

means for arranging said generated reproduction vectors in said joint codebook according to an arrangement algorithm so that for each N, the first N reproduction vectors in said set of M reproduction vectors form an N-level codebook that allows for a small average distortion of said vectors when used in said quantization of said vectors.

22. A software application product, comprising a storage medium having a software application for determining a joint codebook of M reproduction vectors for use in an N-level quantization of vectors embodied therein, wherein M is a pre-defined maximum number of levels M, wherein N is selectable prior to said quantization from a set of at least two pre-defined values that are smaller than or equal to M, and wherein in said quantization, a reproduction vector for each vector is selected from an N-level codebook of N reproduction vectors that are, for each N in said set of at least two pre-defined values, represented by the first N reproduction vectors of said joint codebook, said software application comprising:

program code for generating said reproduction vectors by a training algorithm at least partially based on a plurality of training vectors; and

program code for arranging said generated reproduction vectors in said joint codebook according to an arrangement algorithm so that for each N, the first N reproduction vectors in said set of M reproduction vectors form an N-level codebook that allows for a small average distortion of said vectors when used in said quantization of said vectors.

23. A joint codebook for use in an N-level quantization of vectors, wherein M is a pre-defined maximum number of levels, wherein N is selectable prior to said quantization from a set of at least two pre-defined values that are smaller than or equal to M, and wherein in said quantization, a reproduction vector for each vector is selected from an N-level codebook of N reproduction vectors that are, for each N in said set of at least two pre-defined values, represented by the first N reproduction vectors of said joint codebook of M reproduction vectors, said joint codebook comprising:

a set of M reproduction vectors, wherein said reproduction vectors in said set of M reproduction vectors are generated by a training algorithm at least partially based on a plurality of training vectors; and

wherein said reproduction vectors are arranged in said set of M reproduction vectors according to an arrangement algorithm so that for each N, the first N reproduction vectors in said set of M reproduction vectors form an N-level codebook that allows for a small average distortion of said vectors when used in said quantization of said vectors.