### 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 language | English (US) |
---|---|

Pages (from-to) | 89-91 |

Number of pages | 3 |

Journal | IEEE Communications Letters |

Volume | 2 |

Issue number | 4 |

DOIs | |

State | Published - Dec 1 1998 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

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

### Keywords

- CDMA
- Optimum multiuser detection

### Cite this

}

*IEEE Communications Letters*, vol. 2, no. 4, pp. 89-91. https://doi.org/10.1109/4234.664214

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

Research output: Contribution to journal › Article

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 -