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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
S. Verdú, Minimum Probability of Error for Asynchronous Gaussian Multiple-Access Channels,IEEE Trans. Inform. Theory,32, pp. 85–96 (January 1986).
G. D. Forney, The Viterbi Algorithm,Proc. IEEE,61, pp. 268–278 (March 1973).
K. S. Schneider, Optimum Detection of Code Division Multiplexed Signals,IEEE Trans. Aerospace Electron. Systems,15, pp. 181–185 (January 1979).
M. R. Garey and D. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, San Francisco (1979).
S. Verdú, Optimum Multi-user Signal Detection, Ph.D. Dissertation, Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign. Report T-151, Coordinated Science Laboratory, Urbana, IL (August 1984).
S. Verdú, Optimum Multiuser Asymptotic Efficiency,IEEE Trans. Comm.,34, pp. 890–897 (September 1986).
C. H. Papadimitrou and K. Steiglitz,Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Englewood Cliffs, NJ (1982).
S. Verdú, Multiple-Access Channels with Point-Process Observations: Optimum Demodulation,IEEE Trans. Inform. Theory,32, pp. 642–651 (September 1986).
M. K. Simon, J. K. Omura, R. A. Scholtz, and B. K. Levitt,Spread Spectrum Communications, Vol. 3, Computer Science Press, Rockville, MD (1985).
R. Lupas and S. Verdú, Linear Multiuser Detectors for Synchronous Code-Division Multiple-Access Channels,IEEE Trans. Inform. Theory,35 (January 1989).
A. J. Viterbi and J. K. Omura,Principles of Digital Communication and Coding, McGraw-Hill, New York (1979).
G. J. Foschini, A Reduced State Variant of Maximum Likelihood Sequence Detection Attaining Optimum Performance for High Signal-to-Noise Ratios,IEEE Trans. Inform. Theory,23, pp. 605–609 (September 1977).
A. P. Clark,Advanced Data-Transmission Systems, Halsted Press, New York (1977).
D. Kazakos, Computational Savings and Implementation of Maximum Likelihood Detectors,IEEE Trans. Inform. Theory,24, pp. 124–126 (January 1978).
Author information
Authors and Affiliations
Additional information
Communicated by Israel Cidon and Inder S. Gopal.
This work was partially supported by the National Science Foundation under Grant ECS-8504752, and by the US Army Research Office under Contract DAAL03-87-K-0062.
Rights and permissions
About this article
Cite this article
Verdú, S. Computational complexity of optimum multiuser detection. Algorithmica 4, 303–312 (1989). https://doi.org/10.1007/BF01553893
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01553893