Single-codebook vector quantization for multiple-rate applications

• US 7,587,314 B2
• Filed: 08/29/2005
• Issued: 09/08/2009
• 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
• Primary Examiner(s): Hudspeth; David R
• Assistant Examiner(s): SHAH, PARAS D
• Application Number:
  US11/214,484
• Publication Number:
  US 20070055509A1
• Time in Patent Office: 1,471 Days
• Field of Search: 704/219, 704/222, 704/243, 704500-503, 382/253, 382/243, 370/240.22
• US Class Current: 704/222
• 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 comprising:

selecting, in an N-level quantization of a vector, 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 said 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, and

providing an identifier signal that identifies said selected reproduction vector, said method further comprising processing said identifier signal for storage in a storage medium or for transmission on a transmission channel of a communication system.

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 2, 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 selecting is performed by a portable communication device.

6. An apparatus comprising:

means for selecting, in an N-level quantization of a vector, 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 said 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 and for providing an identifier signal that identifies said selected reproduction vector; and

means for processing said identifier signal for storage in a storage medium or for transmission on a transmission channel of a communication system.

7. A computer-readable medium having a computer program stored thereon, the computer program comprising:

instructions operable to cause a processor to select, in an N-level quantization of a vector, 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 said 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 and to provide an identifier signal that identifies said reproduction vector for further processing for storage in a storage medium or for transmission on a transmission channel of a communication system.

8. A method comprising:

receiving an identifier signal from a storage medium or over a communication channel, said identifier signal indicative of a reproduction vector that has been selected for a vector in an N-level quantization of said vector, wherein N is selectable prior to said quantization of said vector 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

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 said retrieved reproduction vector for output to further processing stages.

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

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

10. An apparatus comprising:

means for receiving an identifier signal from a storage medium or over a communication channel, said identifier signal indicative of a reproduction vector that has been selected for a vector in an N-level quantization of said vector, wherein N is selectable prior to said quantization of said vector 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

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 said retrieved reproduction vector for output to further processing stages.

11. A computer-readable medium having a computer program stored thereon, said computer program comprising:

instructions operable to cause a processor to receive an identifier signal from a storage medium or over a communication channel, said identifier signal indicative of a reproduction vector that has been selected for a vector in an N-level quantization of said vector, wherein N is selectable prior to said quantization of said vector 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

instructions operable to cause a processor to retrieve, 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 said retrieved reproduction vector for output to further processing stages.

12. A system, comprising:

means for selecting a reproduction vector for a 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 comprising:

generating reproduction vectors for a joint codebook of M reproduction vectors for us in an N-level quantization of vectors by a training algorithm at least partially based on a plurality of training 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; and

storing and arranging said generated reproduction vectors in a memory according to an arrangement algorithm so as to form said joint codebook in such a way 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;

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;

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;

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;

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;

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;

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. An apparatus comprising:

means for generating reproduction vectors for a joint codebook of M reproduction vectors for use in an N-level quantization of vectors by a training algorithm at least partially based on a plurality of training 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; and

means for storing and arranging said generated reproduction vectors in a memory according to an arrangement algorithm so as to form said joint codebook in such a way 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 computer-readable medium having a computer program stored thereon, the computer program comprising:

instructions operable to cause a processor to generate reproduction vectors for a joint codebook of M reproduction vectors for use in an N-level quantization of vectors by a training algorithm at least partially based on a plurality of training 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; and

instructions operable to cause a processor to store and arrange said generated reproduction vectors in a memory according to an arrangement algorithm so as to form said joint codebook in such a way 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. An apparatus comprising:

a selector configured to select, in an N-level quantization of a vector, 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 said 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 and configured to provide an identifier signal that identifies said selected reproduction vector; and

a processor for processing said identifier signal for storage in a storage medium or for transmission via a transmission channel of a communication system.

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

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

26. The apparatus according to claim 23, wherein said vectors comprise parameters related to Linear Predictive Coding of a data sequence.

27. The apparatus according to claim 23, wherein said selecting is performed by a portable communication device.

28. The apparatus according to claim 23, wherein said apparatus is a portable communication device.

29. An apparatus comprising:

a receiver configured to receive an identifier signal from a storage medium or over a communication channel, said identifier signal indicative of a reproduction vector that has been selected for a vector in an N-level quantization of said vector, wherein N is selectable prior to said quantization of said vector 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

a retriever configured to retrieve, 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, said retrieved reproduction vector for output to further processing stages.

30. The apparatus according to claim 29, wherein said apparatus is a portable communication device.

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

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

31. A system comprising:

a selector configured to select a reproduction vector for a 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 and configured to provide an identifier signal that identifies said selected reproduction vector;

a transmitter configured to process said identifier signal and configured to transmit said identifier signal via a transmission channel;

a receiver configured to receive said identifier signal; and

a retriever configured to retrieve, 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 for output to further processing stages.

32. An apparatus comprising:

a generator configured to generate reproduction vectors for a joint codebook of M reproduction vectors for use in an N-level quantization of vectors by a training algorithm at least partially based on a plurality of training 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; and

a storage and an arranger configured to arrange said generated reproduction vectors in a memory according to an arrangement algorithm so as to form said joint codebook in such a way 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.

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

35. The apparatus according to claim 34, wherein said apparatus is configured to generate an initial codebook of M reproduction vectors by said training algorithm;

wherein said apparatus is configured to generate a 2-level codebook of 2 reproduction vectors by said training algorithm;

wherein said apparatus is configured to select those 2 reproduction vectors from said initial codebook that are most similar to said 2 reproduction vectors in said 2-level codebook;

wherein said apparatus is configured to copy said 2 selected reproduction vectors from said initial codebook to the first 2 positions in said joint codebook and to delete said 2 selected reproduction vectors from said initial codebook; and

wherein said apparatus is configured to repeat, for 1<

i ≦

m, the following;

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.

36. The apparatus according to claim 34, wherein said apparatus is configured to generate a 2-level codebook of 2 reproduction vectors by said training algorithm;

wherein said apparatus is configured to copy said 2 reproduction vectors from said 2-level codebook to the first 2 positions in said joint codebook; and

wherein said apparatus is configured to repeat, for 1<

i≦

m, the following;

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.

37. The apparatus according to claim 32, wherein said apparatus is configured to generate an initial codebook of M reproduction vectors by said training algorithm based on a plurality of training vectors;

wherein said apparatus is configured to select, from said initial codebook, the two reproduction vectors that are most different to each other;

wherein said apparatus is configured to copy 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

wherein said apparatus is configured to repeat, while said initial codebook is non-empty, the following;

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.

38. The apparatus according to claim 32, wherein said apparatus is configured to generate an initial codebook of M reproduction vectors by said training algorithm based on a plurality of training vectors;

wherein said apparatus is configured to select, from said initial codebook, the reproduction vector that is most similar to all of said training vectors;

wherein said apparatus is configured to copy 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

wherein said apparatus is configured to repeat, while said initial codebook is non-empty, the following;

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.

39. The apparatus according to claim 32, wherein said apparatus is configured to generate an initial codebook of M reproduction vectors by said training algorithm;

wherein said apparatus is configured to repeat, while said initial codebook is non-empty, the following;

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.

40. The apparatus according to claim 32, 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, wherein said apparatus is configured to generate an initial codebook of M reproduction vectors by said training algorithm based on a plurality of training vectors;

wherein said apparatus is configured to select, 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;

wherein said apparatus is configured to copy said selected reproduction vectors from said initial codebook to said joint codebook and to delete said selected reproduction vectors from said initial codebook; and

wherein said apparatus is configured to repeat, for each N_i with 1<

i≦

K, the following;

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.