Computational complexity of optimum multiuser detection

Sergio Verdú

Research output: Contribution to journalArticlepeer-review

154 Scopus citations


Optimum centralized demodulation of the independent data streams transmitted simultaneously by several users through a Code Division Multiple-Access channel is considered. Each user sends an arbitrary assigned signal waveform, which is linearly modulated by symbols drawn from a finite alphabet. If the users are asynchronous, the optimum multiuser detector can be implemented by a Viterbi algorithm whose time-complexity is linear in the number of symbols transmitted by each user and exponential in the number of users. It is shown that the combinatorial problem of selecting the most likely transmitted data stream given the sufficient statistics (sequence of matched filter outputs), and the signal energies and cross-correlations is nondeterministic polynomial-time hard (NP-hard) in the number of users. And it remains so even if the users are restricted to be symbol-synchronous. The performance analysis of optimum multiuser detection in terms of the set of multiuser asymptotic efficiencies is equivalent to the computation of the minimum Euclidean distance between any pair of distinct multiuser signals. This problem is also shown to be NP-hard and a conjecture on a longstanding open problem in single user data communication theory is presented.

Original languageEnglish (US)
Pages (from-to)303-312
Number of pages10
Issue number1
StatePublished - Dec 1989

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics


  • Code Division Multiple Access
  • Gaussian communication channels
  • Hypothesis testing
  • Maximum-likelihood sequence detection
  • NP-complete


Dive into the research topics of 'Computational complexity of optimum multiuser detection'. Together they form a unique fingerprint.

Cite this