Optimum multiuser detection is tractable for synchronons CDMA systems usine M-sequences

Sennur Ulukus, Roy Yates

Research output: Contribution to journalArticle

44 Citations (Scopus)

Abstract

The optimum multiuser detection problem was shown to be NP-hard, i.e., its computational complexity increases exponentially with the number of users [1], [2]. In this letter, we show that the optimum multiuser detection problem for a synchronous code-division multiple access (CDMA) system is equivalent to the minimum capacity cut problem in a related network and propose an optimum multiuser detection algorithm with polynomial computational complexity for a certain class of signature sequences. The minimum cut problem is solvable in polynomial time if the capacities of the links not incident to source and sink are nonnegative. This condition in the optimum detection problem is equivalent to all cross correlations between the signature sequences of the users being negative. One example of such set of signature sequences is obtained when shifted versions of the maximal length sequences (or m-sequences) are used. In this case the cross correlation between users i and j is given as Γij = -1/G for all i, j, where G is the processing gain.

Original languageEnglish (US)
Pages (from-to)89-91
Number of pages3
JournalIEEE Communications Letters
Volume2
Issue number4
DOIs
StatePublished - Dec 1 1998

Fingerprint

Multiuser Detection
M-sequence
Multiuser detection
Code Division multiple Access
Code division multiple access
Computational complexity
Polynomials
Signature
Cross-correlation
Computational Complexity
Minimum Cut
Polynomial Complexity
Processing
Polynomial time
NP-complete problem
Non-negative

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering
  • Computer Science Applications
  • Modeling and Simulation

Keywords

  • CDMA
  • Optimum multiuser detection

Cite this

@article{e8e4c5e3ff754acbbb168987ec3724c0,
title = "Optimum multiuser detection is tractable for synchronons CDMA systems usine M-sequences",
abstract = "The optimum multiuser detection problem was shown to be NP-hard, i.e., its computational complexity increases exponentially with the number of users [1], [2]. In this letter, we show that the optimum multiuser detection problem for a synchronous code-division multiple access (CDMA) system is equivalent to the minimum capacity cut problem in a related network and propose an optimum multiuser detection algorithm with polynomial computational complexity for a certain class of signature sequences. The minimum cut problem is solvable in polynomial time if the capacities of the links not incident to source and sink are nonnegative. This condition in the optimum detection problem is equivalent to all cross correlations between the signature sequences of the users being negative. One example of such set of signature sequences is obtained when shifted versions of the maximal length sequences (or m-sequences) are used. In this case the cross correlation between users i and j is given as Γij = -1/G for all i, j, where G is the processing gain.",
keywords = "CDMA, Optimum multiuser detection",
author = "Sennur Ulukus and Roy Yates",
year = "1998",
month = "12",
day = "1",
doi = "https://doi.org/10.1109/4234.664214",
language = "English (US)",
volume = "2",
pages = "89--91",
journal = "IEEE Communications Letters",
issn = "1089-7798",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "4",

}

Optimum multiuser detection is tractable for synchronons CDMA systems usine M-sequences. / Ulukus, Sennur; Yates, Roy.

In: IEEE Communications Letters, Vol. 2, No. 4, 01.12.1998, p. 89-91.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Optimum multiuser detection is tractable for synchronons CDMA systems usine M-sequences

AU - Ulukus, Sennur

AU - Yates, Roy

PY - 1998/12/1

Y1 - 1998/12/1

N2 - The optimum multiuser detection problem was shown to be NP-hard, i.e., its computational complexity increases exponentially with the number of users [1], [2]. In this letter, we show that the optimum multiuser detection problem for a synchronous code-division multiple access (CDMA) system is equivalent to the minimum capacity cut problem in a related network and propose an optimum multiuser detection algorithm with polynomial computational complexity for a certain class of signature sequences. The minimum cut problem is solvable in polynomial time if the capacities of the links not incident to source and sink are nonnegative. This condition in the optimum detection problem is equivalent to all cross correlations between the signature sequences of the users being negative. One example of such set of signature sequences is obtained when shifted versions of the maximal length sequences (or m-sequences) are used. In this case the cross correlation between users i and j is given as Γij = -1/G for all i, j, where G is the processing gain.

AB - The optimum multiuser detection problem was shown to be NP-hard, i.e., its computational complexity increases exponentially with the number of users [1], [2]. In this letter, we show that the optimum multiuser detection problem for a synchronous code-division multiple access (CDMA) system is equivalent to the minimum capacity cut problem in a related network and propose an optimum multiuser detection algorithm with polynomial computational complexity for a certain class of signature sequences. The minimum cut problem is solvable in polynomial time if the capacities of the links not incident to source and sink are nonnegative. This condition in the optimum detection problem is equivalent to all cross correlations between the signature sequences of the users being negative. One example of such set of signature sequences is obtained when shifted versions of the maximal length sequences (or m-sequences) are used. In this case the cross correlation between users i and j is given as Γij = -1/G for all i, j, where G is the processing gain.

KW - CDMA

KW - Optimum multiuser detection

UR - http://www.scopus.com/inward/record.url?scp=3342886083&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=3342886083&partnerID=8YFLogxK

U2 - https://doi.org/10.1109/4234.664214

DO - https://doi.org/10.1109/4234.664214

M3 - Article

VL - 2

SP - 89

EP - 91

JO - IEEE Communications Letters

JF - IEEE Communications Letters

SN - 1089-7798

IS - 4

ER -