Dynamic Programming in Digital Communications: Viterbi Decoding to Turbo Multiuser Detection

Many important signal processing tasks in digital communications are based on integer programming problems whose raw complexity is extremely high. Such problems include the decoding of convolutional codes, channel equalization, multiuser detection, and the joint performance of these tasks. In each of these problems, the high complexity arises from the need to perform simultaneous processing on long sequences of finite-valued symbols in order to optimally detect or decode them. Fortunately, the complexity of these optimization problems can often be greatly reduced through the use of dynamic programming, which efficiently finds optimal [e.g., maximum likelihood (ML) or maximum a posteriori probability (MAP)] decisions in long sequences of symbols. This paper reviews four decades of progress in this area: the Viterbi algorithm for ML decoding of convolutional codes of the 1960s; the ML sequence detectors for channel equalization and the BCJR algorithm for MAP decoding of convolutional codes of the 1970s; the ML and MAP multiuser detectors of the 1980s; and combinations of these through the turbo processing of the 1990s.