John Kieffer: Asymptotics of Viterbi Algorithm Encoded Trellis Coded Quantizers

This is a joint work with Yu Liao.

Let G be a finite connected directed graph with two outgoing edges per vertex (such as a DeBrujn graph). A one bit per source sample trellis coded quantizer for encoding a finite-alphabet memoryless information source is obtained by labelling each edge of G with a letter from the source alphabet. One encodes a source sequence of long finite length by finding a path in G of that length whose sequence of labels is closest in Hamming distance to the source sequence; finding the minimum distance path is a dynamic programming problem that is solved using the Viterbi algorithm. Given a trellis coded quantizer, we show how a Markov chain can be used to obtain a closed form expression for the asymptotic expected Hamming distortion per sample that results from the Viterbi algorithm encoder as the number of encoded source samples increases without bound. The Markov chain method provides conditions satisfied by some minimum distortion trellis coded quantizers that go beyond the Marcellin-Fischer conditions inspired by Ungerboeck's heuristics for trellis coded modulator design.

Back to the Index

Please send comments and corrections to Thomas Klausner.