Dynamic programming algorithms for maximum likelihood decoding
Stuart Geman, Kevin Geoffrey Kochanek · 1998
The Viterbi algorithm is the traditional prototype dynamic programming algorithm for maximum likelihood decoding. Seen from the perspective of formal language theory, this algorithm recursively parses a trellis code's regular grammar. This thesis discusses generalized Viterbi algorithms for the maximum likelihood decoding of codes generated by context-free grammars and transmitted across either memoryless or Markov communications channels. Among the codes representable by context-free grammars are iterated squaring constructions--including the Reed-Muller codes. Two additional strategies are introduced for handling large Reed-Muller-like codes. First, by systematically discarding information bits, a code's grammatical and decoding complexities can be reduced to manageable levels without seriously reducing its information capacity. Second, a coarse-to-fine dynamic programming algorithm for the maximum likelihood decoding of Reed-Muller-like codes is presented; this algorithm almost uniformly outperforms the Viterbi algorithm.