An Overview of Matrix Quantizer Design using the Generalized Lloyd Algorithm

This paper gives a tutorial review of extensions of the Lloyd vector quantizer called matrit quantizers. The Lloyd matrix quantizer arises naturally from the minimization step in linear prediction, where the minimization takes place over a codebook of inverse filter models. Rate-distortion theory predicts possible bit-rate savings for increasing block length N when such a code-book is optimized. Experimental results on LPC speech indicate that this is the case. On single-speaker tests, a 3-vector matrix quantizer at 3 bits per frame for the LPC model achieved average distortion comparable to a vector quantizer at 7 bits per frame. However, such savings are obtained at the expense of exponentially rising complexity. Shape-gain matrix quantizers provide a compromise between complexity and very low bit rate. In this case, N-vector shape matrices are combined with K-dimensional gain vectors to form a generalized product codebook. We have simulated a shape-gain matrix quantizer operating at 6 bits per frame (or 300 bits per second) for the LPC model having average distortion comparable to a vector quantizer operating at 9 bits per frame (or 450 bits per second), with less than 1.7 times the complexity.