Lattice and trellis-coded quantization

• US 5,297,170 A
• Filed: 08/21/1990
• Issued: 03/22/1994
• Est. Priority Date: 08/21/1990
• Status: Expired due to Term

• Current Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Original Assignee: Codex Corporation (Motorola Solutions, Inc.)
• Inventors: Forney, G. David Jr., Eyuboglu, Vedat M.
• Primary Examiner(s): Kuntz, Curtis
• Assistant Examiner(s): Bocure, Tesfaldet
• Application Number:
  US07/570,413
• Time in Patent Office: 1,309 Days
• Field of Search: 375/39, 375/122, 375/25, 375/34, 375/27, 341/200, 341/67, 341/26, 381/31, 358/133, 358/433
• US Class Current: 375/242
• CPC Class Codes: G06T 9/008 Vector quantisation
• CPC Class Codes: H03M 7/3082 Vector coding for television signals, see H04N19/94

Abstract

Vectors are quantized by representing the vectors by quantized values using a codebook having granular regions which are based on a coset code, and which lie inside a boundary region which is based on another coset code, the boundary region being other than an N-cube and other than the Voronoi region of a sublattice Λ_b =MΛ_g of a lattic Λ_g upon which the granular regions may have been based.

Claims

1. Apparatus for quantizing signal vectors whose components represent signal samples, comprising

means for providing a codebook having codewords based on a coset code, and which lie inside a boundary region which is based on another coset code, said boundary region being other than an N-cube and other than the Voronoi region of a sublattice Λ

_b =MΛ

_g of a lattice Λ

_g upon which said codewords may have been based, M being a scaling factor, and

means for selecting codewords from said codebook as quantized values representing said signal vectors.

2. The apparatus of claim 1 wherein said codeword as based on said lattice Λ

_g, or a translate Λ

_g +a of said lattice Λ

_g.

3. The apparatus of claim 1 wherein said codewords are based on a trellis code or a translate of a trellis code.

4. The apparatus of claim 1 wherein said boundary region is based on a lattice.

5. The apparatus of claim 1 wherein said boundary region is based on a trellis code.

6. The apparatus of claim 1 wherein said codeword are fundamental regions of a lattice Λ

_g or a translate or said lattice Λ

_g.

7. The apparatus of claim 6 wherein said fundamental regions are Voronoi regions.

8. The apparatus of claim 1 wherein said codewords are fundamental regions of a trellis code or a translate of a trellis code.

9. The apparatus of claim 8 wherein said fundamental regions are Voronoi regions.

10. The apparatus of claim 1 wherein said boundary region is a fundamental region of a lattice Λ

_b.

11. The apparatus of claim 10 wherein said fundamental region is a Voronoi region.

12. The apparatus of claim 1 wherein said boundary region is a fundamental region of a trellis code.

13. The apparatus of claim 12 wherein said fundamental region is a Voronoi region.

14. The apparatus of claim 1 further comprising a quantizer for selecting one of said codewords to represent each vector.

15. The apparatus of claim 14 wherein said quantizer includes means for detecting an overload.

16. The apparatus of claim 15 wherein said means includes a decoder for said coset code on which said boundary region is based to determine said overload.

17. The apparatus of claim 16 further comprising a second quantizer for quantizing said vector when an overload is detected.

18. The apparatus of claim 17 wherein said second quantizer is a scalar quantizer.

19. The apparatus of claim 17 further comprising means for inserting an extra bit to identify the quantizer.

20. The apparatus of claim 1 wherein each said codeword comprises a fundamental region of said lattice Λ

_g, and lies within a fundamental region of said sublattice Λ

_b.

21. The apparatus of claim 20 further comprising a quantizer for selecting one of said codewords to represent each said vector.

22. The apparatus of claim 20 wherein each said codeword is represented by a coset leader of said sublattice Λ

_b in Λ

_g or a translate of Λ

_g.

23. The apparatus of claim 22 further comprising a mapper for representing said coset leader by bits.

24. The apparatus of claim 23 further comprising a binary decoder G_g for the lattice Λ

_g and a binary syndrome former H_b^T for the sublattice Λ

_b.

25. The apparatus of claim 23 further comprising a reconstructor for mapping said bits into a coset representative, and for translating said coset representative to said coset leader using a decoder for the sublattice Λ

_b.

26. The apparatus of claim 25 wherein said decoder is a minimum distance decoder for the sublattice Λ

_b.

27. The apparatus of claim 25 wherein said mapping of bits to coset representatives includes a binary encoder G_g for the lattice Λ

_g and an inverse syndrome former (H_b^-1)^T for the sublattice Λ

_b.

28. The apparatus of claim 1 wherein said codewords are based on a trellis code C_g (Λ

_g /Λ

_g '"'"';

C_g) which comprises sequences whose elements lie in a sequence of cosets of Λ

_g '"'"' in Λ

_g of a translate Λ

_g +a of Λ

_g selected by the convolutional code C_g.

29. The apparatus of claim 1 wherein said boundary region is based on a trellis code C_b (Λ

_b /Λ

_b '"'"';

C_b) which comprises sequences whose elements lie in a sequence of cosets of Λ

_b '"'"' in Λ

_b of a translate Λ

_b +a of Λ

_b selected by the convolutional code C_b.

30. The apparatus of claim 28 or 29 further comprising a quantizer for selecting one of said codewords in said boundary region.

31. The apparatus of claim 30 wherein said quantizer includes means for detecting an overload.

32. The apparatus of claim 31 further comprising a second quantizer for quantizing said vector when an overload is detected.

33. The apparatus of claim 32 wherein said second quantizer is a scalar quantizer.

34. The apparatus of claim 32 further comprising means for inserting an extra bit to identify the quantizer.

35. The apparatus of claim 31 wherein said means includes a decoder for said trellis code C_b.

36. The apparatus of claim 30 further comprising a mapper for representing said selected codeword by bits.

37. The apparatus of claim 36 wherein said mapper further comprises an inverse syndrome former (H_b^-1)^T for the convolutional code C_b.

38. The apparatus of claim 30 further comprising a decoder G_g^-1 for the convolutional code C_g and a syndrome former H_b^T for the convolutional code C_b.

39. The apparatus of claim 30 further comprising a reconstructor for mapping said bits to code sequences.

40. The apparatus of claim 39 further comprising means for mapping boundary bits to coset representatives for said convolutional code C_b to identify a label translate of said trellis code C_b.

41. The apparatus of claim 40 wherein said a decoder of said label translate of said trellis code C_b determines said code sequence.

42. The apparatus of claim 40 further comprising means for mapping granular and scaling bits to identify a signal space translate of said label translate of said trellis code C_b.

43. The apparatus of claim 40 wherein said mapper of said granular bits comprises an encoder G_g for the convolutional code C_g.

44. The apparatus of claim 1 further comprising multiple said codebooks forming a super codebook, at least two of said codebooks having codewords with different volumes.

45. The apparatus of claim 44 further comprising means for selecting one of said codebooks and one of said codewords in said selected codebook to represent said vector.

46. The apparatus of claim 44 further comprising means for representing said selected codebook and said selected codeword by bits.

47. The apparatus of claim 46 further comprising means to represent the selected codebook as a variable length prefix code so that a fixed number of bits can be used to represent the combination of the selected codebook and the codeword.

48. The apparatus of claim 46 further comprising a reconstructor to determine from said bits a codebook and a codeword.

49. The apparatus of claim 48 further comprising a decoder for the prefix code.

50. The apparatus of claim 44 wherein said multiple codebooks are translates of one another either in label space or in signal space.

51. Apparatus for quantizing signal vectors whose components represent signal samples, comprising

means for providing a codebook having codewords based on a coset code and which lie inside a boundary region which is based on a finite field code and a finite set of subregions, said boundary region being other than an N-cube and other than the Voronoi region of a sublattice Λ

_b =MΛ

_g of a lattice Λ

_g upon which said codewords may have been based, M being a scaling factor, and

means for selecting code words from said codebook as quantized values representing said signal vectors.

52. The apparatus of claim 51 further comprising means for selecting one of said codewords to represent each said vector.

53. The apparatus of claim 52 further comprising a mapper for representing said codewords by bits.

54. The apparatus of claim 53 wherein said mapper further comprises means for extracting a label representing a sequence of subregions.

55. The apparatus of claim 54 wherein said mapper further comprises a binary encoder γ

_g^-1 for said coset code upon which said codewords are based and the syndrome former H_b^T for the said finite field code.

56. The apparatus of claim 54 further comprising a reconstructor for mapping said bits into codeword using a decoder for said finite field code.

57. The apparatus of claim 56 wherein said reconstructor further comprises a mapper for mapping boundary bits to a coset representative of the finite field code, said decoder selecting an element from the coset of the finite field code identified by the coset representative, said element subsequently selecting the sequence of subregions.

58. The apparatus of claim 56 wherein said decoder also uses granular and scaling bits to select said element.

59. The apparatus of claim 56 wherein said mapper further comprises a binary encoder G_g for said coset code upon which said codewords are based, and in inverse syndrome former (H_b^-1)^T for said finite field code.

60. Apparatus for quantizing signal vectors comprising multiple codebooks forming a super codebook, at least two of said codebooks having different densities of codewords, the apparatus further comprising means for selecting one of said codebooks and one of said codewords in said selected codebook to represent said vector, the apparatus further comprising means for representing said selected codebook and said selected codeword by bits, and further comprising means for representing the selected codebook as a variable length prefix code to represent the selected codebook so that a fixed number of bits can be used to represent the combination of the selected codebook and the codeword.

61. The apparatus of claim 60 further comprising a reconstructor to determine from said bits a codebook and a codeword.

62. The apparatus of claim 61 further comprising a decoder for the prefix code.

63. A method for quantizing signal vectors whose components represent signal samples, comprising

providing a codebook having codewords based on a coset code, and which lie inside a boundary region which is based on another coset code, said boundary region being other than an N-cute and other than the Voronoi region of a sublattice Λ

_b =MΛ

_g of a lattice Λ

_g upon which said codewords may have been based, M being a scaling factor, and

selecting codewords from said codebook as quantized values representing said signal vectors using said codebook.

64. A method for quantizing signal vectors whose components represent signal samples, comprising

providing a codebook having codewords based on a coset code, and which lie inside a boundary region which is based on a finite field code and a finite set of subregions, said boundary region being other than an N-cube and other than the Voronoi region of a sublattice Λ

_b =MΛ

_g of a lattice Λ

_g upon which said codewords may have been based, M being scaling factor, and

selecting codewords from said codebook as quantized values representing said signal vectors using said codebook.

65. A method for quantizing signal vectors comprising

providing multiple codebooks forming a super codebook, at least two of said codebooks having codewords with different volumes,

selecting one of said codebooks and one of said codewords in said selected codebook to represent said vector,

representing said selected codebook and said selected codeword by bits, and

providing a variable length prefix code to represent the selected codebook so that a fixed number of bits can be used to represent the combination of the selected codebook and the codeword.