Method and system for multi-rate lattice vector quantization of a signal
View Patent ↗The present invention relates to a method and system for multi-rate lattice vector quantization of a source vector x representing a frame from a source signal to be used, for example, in digital transmission and storage systems. The multi-rate lattice quantization encoding method comprises the steps of associating to x a lattice point y in a unbounded lattice Λ; verifying if y is included in a base codebook C derived from the lattice Λ; if it is the case then indexing y in C so as to yield quantization indices if not then extending the base codebook using, for example a Voronoi based extension method, yielding an extended codebook; associating to y a codevector c from the extended codebook, and indexing y in the extended codebook C. The extension technique allows to obtain higher bit rate codebooks from the base codebooks compared to quantization method and system from the prior art.
1. A multi-rate lattice quantization encoding method comprising:
i) providing a source vector x representing a frame from a source signal;
ii) providing a base codebook C derived from a lattice Λ;
iii) associating to x a lattice point y in said lattice Λ;
iv) if y is included in said base codebook C then indexing y in said base codebook C yielding quantization indices, and ending the method, if not then
v) extending said base codebook, yielding an extended codebook;
vi) associating to y a codevector c from said extended codebook; and
vii) indexing y in said extended codebook yielding quantization indices.
2. A method as recited in claim 1 , wherein said extended codebook is represented by the expression mC+V, wherein C is said base codebook, V is an appropriate set of points in said lattice Λ.
3. A method as recited in claim 1 , wherein in iii) said lattice point y in said lattice Λ is selected as the nearest neighbor of x in said lattice Λ.
4. A method as recited in claim 1 , wherein step v) includes providing an integer scaling factor m>=2; step vi) includes computing a Voronoi codevector v corresponding to lattice point y using m and providing an offset; and vi) includes computing said codevector c using v and m.
5. A method as recited in claim 4 , wherein in step v) said scaling factor m is set to 2 r and step v) further includes computing a Voronoi index k; step vi) includes computing a Voronoi codevector v corresponding to said lattice point y using k and m.
6. A method as recited in claim 4 , wherein in vi) said codevector c is computed as c=(y−v)/m, wherein m is an integer greater than or equal to 2.
7. A method as recited in claim 4 , wherein step vi) further includes verifying if c is in said base codebook C, then
a) step vii) further includes indexing y as a base codevector and multiplexing j and k yielding quantization indices, where j is the index of c in the base codebook C and k is the Voronoi index corresponding to the vector v; if not then
b) b) increasing said scale factor and said order of said Vorenoi extension and repeating steps v) to vi).
8. A method as recited in claim 4 , further comprising in vii) defining the lossless encoding of the codebook number corresponding to said extension order r and the index i of the codevector y in said base codebook, yielding an encoded codebook number n E and an encoded index i E ; and multiplexing n E and i E .
9. A method as recited in claim 1 , further comprising:
vii) storing said said quantization indices in storing means.
10. A method as recited in claim 1 , further comprising:
vii) transmitting said said quantization indices over a communication channel.
11. A multi-rate lattice quantization encoding method comprising:
providing a source vector x representing a frame from a source signal;
providing finite subsets C and V of an infinite lattice L of points;
associating x with y, y being one of said points in said lattice L; and
indexing y into an integer codebook number n and an index i as y=mc+v, wherein c is an element of C, v is an element of V, and m is an integer greater than or equal to two;
wherein said subsets C and V of the lattice L, the value of m and the size of i being uniquely defined from n.
12. A method as recited in claim 11 , wherein n is represented by a unary code.
13. A method as recited in claim 11 , wherein said subset V of an infinite lattice L is a Voronoi codebook and said index of v is a Voronoi index.
14. A method as recited in claim 11 , wherein said index i is the concatenation of an index of c and an index of v.
15. A method as recited in claim 11 , wherein y=[0 . . . 0] and n is set to a predetermined value when a number of allocated bits available in implementing the method is not sufficient to represent said source vector x in said infinite lattice L.
16. A method as recited in claim 11 , wherein m=2 r ; said subset C being predetermined; said codebook number n being equal to r plus a predetermined integer; r being an integer greater than or equal to 1.
17. A multi-rate lattice quantization encoding method comprising:
i) providing an 8-dimension source vector x representing a frame from a source signal;
ii) providing low-rate lattice base codebooks Q 0 , Q 2 , Q 3 , and Q 4 derived from a RE 8 lattice;
iii) determining a lattice point y in said lattice RE 8 which is the nearest neighbor of x in said lattice RE 8 ;
iv) if y is included in Q z , where z equals 0, 2, 3, or 4 then a) memorizing the number z and an identifier k a identifying one of absolute leaders defining Q z , b) if z>0 then b1) indexing y in Q z yielding quantization indices, if m=0 then b2) y is outputted as a zero vector, and c) ending the method;
v) providing an extension order r, and setting a scaling factor m to 2 r ;
vi) setting an iteration number iter=0;
vii) computing a Voronoi index k of the lattice point y,
viii) computing a Voronoi code vector v corresponding to said lattice point y using k and m;
ix) computing a codevector c as c=(y−v)/m;
x) if c is included in Q z , wherein z equals 2, 3, or 4, then
aa) providing z and k a ; if n=2, setting n=3; incrementing n by 2r; storing the values of k, c, z, and k a ; dividing m by 2; decreasing r from 1; if not, then
bb) multiplying m by 2; increasing r by 1;
xi) increasing said iteration number by 1;
xii) if said iteration number=2 then aaa) retrieving said values of k, c, z, and k a ; indexing j of c in Q 3 or in Q 4 , given k a ; multiplexing j and k to form index i, where l is the index of the codevector y and j is the index of c; if not then bbb) repeating steps vii) to xii).
18. A method as recited in claim 17 , wherein in vii) k is computed as being:
k =mod m ( yG −1 RE 8 )
where G RE 8 is a generator matrix defined as
G
RE
g
=
[
4
0
0
0
0
0
0
0
2
2
0
0
0
0
0
0
2
0
2
0
0
0
0
0
2
0
0
2
0
0
0
0
2
0
0
0
2
0
0
0
2
0
0
0
0
2
0
0
2
0
0
0
0
0
2
0
1
1
1
1
1
1
1
1
]
=
[
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
]
and mod m (•) is the component wise modulo-m operation.
19. A method as recited in claim 17 , further comprising down-scaling said source vector x as x/g prior to step iii); g being chosen so as to be greater then 1 and as to avoid an overrun in a memory used in implementing the method.
20. A multi-rate lattice quantization decoding method comprising:
i) providing a base codebook C derived from a lattice Λ;
ii) providing a codebook number n and a quantization index i;
iii) demultiplexing said quantization index i using said codebook number n;
iv) if n=0 then decoding said index i using said base codebook, yielding a quarterized vector y, and ending the method;
v) if n>0 then
a) providing a preselected Voronoi codebook V (r) ;
b) setting an extension order to r=n and a scale factor m=2 r ;
c) demultiplexing indices j and k from i;
d) decoding j into c in said base codebook C;
e) decoding k into v in said Voronoi codebook V (r) ; and
f) reconstructing a quantized vector as
y=mc+v.
21. A method as recited in claim 20 , wherein in ii) an encoded codebook number n E and an encoded index i E are first provided; then a predetermined lossless coding technique is applied on said encoded codebook number n E to get said codebook number n and said quantization index i.
22. A decoding method as recited in claim 20 , wherein said codebook number n and said index i are read from a communication channel.
23. A decoding method as recited in claim 20 , wherein said codebook number n and said index i are read from storing means.
24. A method as recited in claim 20 , wherein n is reconstructed from a unary code.
25. A method as recited in claim 20 , wherein said subset V of L is a Voronoi code and said index of v is a Voronoi index.
26. A multi-rate lattice quantization decoding method comprising:
providing finite subsets C and V of an infinite lattice L of points;
providing a codebook number n and an index i;
using n and i to reconstruct a vector y in a lattice L as y=mc+v, where m is an integer greater than or equal to two, and c and v are points included in L; said point c being reconstructed as an element of a finite subset C of L; said point v is reconstructed as an element of a finite subset V of L; indices of v and of c being computed using i;
wherein said subsets C and V of the lattice L, the value of m and the size of i being uniquely defined from n.
27. A multi-rate lattice quantization decoding method comprising:
providing low-rate lattice base codebooks Q 0 , Q 2 , Q 3 , and Q 4 derived from a RE 8 lattice;
providing a codebook number n and an index i;
if n=0, then reconstructing y as a zero vector;
if 0<n≦4, then demultiplexing a codevector index i, decoding i as an index of a base codebook Q 2 , Q 3 , or Q 4 and reconstructing y;
if n>4 then demultiplexing said codevector index i as a base codebook index j and a Voronoi index k from i; providing an extension order r and a scaling factor m from n; using n to identify either Q 3 or Q 4 , and decoding said index j; computing y=m c+v, where m=2 r is an extension scaling factor, c is a codevector of said base codebook and v is a codevector of a Voronoi codebook.
28. A method for lattice vector quantization of a source vector x comprising:
i) providing a subset of vectors from a lattice of vectors of dimension N, yielding a base codebook requiring NR bits for indexing, where R is the bit rate per dimension of said base codebook;
ii) determining the nearest vector y of x in said lattice of vectors;
iii) if said nearest vector y is comprised within said base codebook then indexing y in said base codebook yielding quantization indices, outputting said quantization indices, and ending the method; if not then:
iv) providing a predetermined scale factor;
v) scaling said base codebook by said scale factor, yielding a scaled codebook including scaled covectors;
vi) inserting a Voronoi codebook around each said scaled codevectors, yielding an extended codebook requiring N(R+r) bits for indexing, where r is the order of said Vorenoi codebook; and
vii) if said nearest neighbour y is comprised within said extended codebook then indexing y in said extended codebook yielding quantization indices, outputting said quantization indices, and ending the method; if not then
viii) if the number of bits required for indexing said extended codebook has not exceeded a predetermined threshold then increasing said scale factor and said order of said Vorenoi codebook and repeating steps v) to viii); if not then said nearest neighbor is considered a remote outlier and outputting predetermined corresponding quantization indices.
29. A method as recited in claim 28 , wherein in step iv) said predetermined scale factor is 2, and in step viii) said scale factor is increased by 2.
30. A method as recited in claim 28 , wherein in step viii) said order of said Voronoi codebook is increased by 1.
31. A multi-rate lattice quantization encoder comprising:
receiving means for providing a source vector x representing a frame from a source signal;
memory means including a base codebook C derived from a lattice Λ;
means associating to x a lattice point y in said lattice Λ;
means for verifying if y is included in said base codebook C and for indexing y in said base codebook C yielding quantization indices;
means for extending said base codebook and for yielding an extended codebook;
means for associating to y a codevector c from said extended codebook; and
means for indexing y in said extended codebook C and for yielding quantization indices.
32. A multi-rate lattice quantization encoder comprising:
means for receiving a source vector x representing a frame from a source signal;
means for providing finite subsets C and V of an infinite lattice L of points;
means for associating x with y, one of said points in said lattice L;
means for indexing y into an integer codebook number n and an index i as y=mc+v, wherein c is an element of C, v is an element of V, and m is an integer greater than or equal to two; wherein said subsets C and V of the lattice L, the value of m and the size of i being uniquely defined from n.
33. A multi-rate lattice quantization decoder comprising:
memory means for providing a base codebook C derived from a lattice Λ;
receiving means for providing an encoded codebook number n and an encoded index i;
means for demultiplexing said quantization index i using said codebook number n;
means for verifying if n=0, and a) for decoding said index i using said base codebook, yielding a quantized vector y;
means for verifying if n>0;
means for providing a preselected Voronoi codebook V (r) ;
means for setting an extension order to r=n and a scale factor m=2 r ;
means for demultiplexing indices j and k from i;
means for decoding j into c in said base codebook C;
means for decoding k into v in said Voronoi codebook V (r) ; and
means for reconstructing a quantized vector as y=m c+v.
34. A multi-rate lattice quantization decoder:
memory means for providing finite subsets C and V of an infinite lattice L of points;
receiving means for providing a codebook number n and an index i;
means for using n and i to reconstruct a vector y in a lattice L as y=mc+v, where m is an integer greater than or equal to two, and c and v are points included in L; said point c being reconstructed as an element of a finite subset C of L; said point v is reconstructed as an element of a finite subset V of L; indices of v and of c being computed using i; wherein said subsets C and V of the lattice L, the value of m and the size of i being uniquely defined from n.