Dynamic programming in digital communications: Viterbi decoding to turbo multiuser detection

Research output: Contribution to journalReview articlepeer-review

5 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)629-657
Number of pages29
JournalJournal of Optimization Theory and Applications
Issue number3
StatePublished - Dec 2002

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Applied Mathematics
  • Management Science and Operations Research


  • Dynamic programming
  • channel decoding
  • channel equalization
  • maximum a posteriori probability detection
  • maximum likelihood detection
  • multiuser detection
  • sequence detection
  • turbo processing


Dive into the research topics of 'Dynamic programming in digital communications: Viterbi decoding to turbo multiuser detection'. Together they form a unique fingerprint.

Cite this