Computational complexity of optimum multiuser detection

Sergio Verdu

Research output: Contribution to journalArticlepeer-review

134 Scopus citations

Abstract

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
JournalAlgorithmica
Volume4
Issue number1
DOIs
StatePublished - Dec 1 1989

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

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

Cite this