Trellis Coded Quantization of Memoryless and Gauss-Markov Sources

Exploiting the duality between modulation for digital communications and source coding, trellis coded quantization (TCQ) is developed and applied to the encoding of memoryless and Gauss-Markov sources. The theoretical justification for the approach is alphabet constrained rate distortion theory, which is a dual to the channel capacity argument that motivates trellis coded modulation (TCM). We adopt the notions of signal set expansion, set partitioning, and branch labeling of TCM, but modify the techniques to account for the source distribution, to design TCQ coders of low complexity with excellent mean squared error (MSE) performance. For a memoryless uniform source, TCQ provides a MSE within 0.21 dB of the distortion rate bound at all positive (integral) rates. The performance is superior to that promised by the coefficient of quantization for all of the best lattices known in dimensions 24 or less. For a memoryless Gaussian source, the TCQ performance at rates of 0.5, 1, and 2 bitsAample, is superior to all previous results we have found in the literature, including stochastically populated trellis codes and entropy coded scalar quantization. The encoding complexity of TCQ is very modest. In the most important case, the encoding for an N-state trellis requires only 4 multiplications, 4 + 2N additions, N comparisons, and 4 scalar quantizations per data sample. TCQ is incorporated into a predictive coding structure for the encoding of Gauss-Markov sources. Simulation results for first-, second-, and third-order Gauss-Markov sources (with coefficients selected to model sampled speech) demonstrate that for encoding rates of 1, 2, or 3 bits/Sample, predictive TCQ yields distortions ranging between 0.75 dB and 1.3 dB from the respective distortion rate bounds.