Optimum Multiuser Detection Is Tractable for Synchronous CDMA Systems Using M-Sequences

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 Gamma(ij) = -1/G for all i, j, where G is the processing gain.