Complexity of Verdu optimum multiuser detection algorithm applied to random-access multichannel CDMA systems

A statistical characterization of the complexity function of Verdu (1986) optimum multiuser detection (VOMD) algorithm is presented for a communication system employing finite number of randomly accessed orthogonal channels and finite number of simultaneous users. It is proved that the probability that the single channel complexity is greater than A^τ approaches zero exponentially fast as the average number τ of simultaneous users in each channel increases, where A is the modulation alphabet size. The moments of the detection complexity function of each channel is found. The ratio of the κ-th root of the κ-th order moment of the complexity function to the complexity of applying the VOMD directly to a single channel CDMA system with the same number of users approaches zero for all κ⩾1 as the number of channels increases. The probability distribution of the joint complexity function (JCF) of the aggregate system is also found. It is shown that with a probability close to 1.0 the JCF concentrates in a small region centered at the mean of the JCF, whose order of magnitude is much less than that of applying the VOMD directly to a single channel CDMA system with the same number of simultaneous users. Therefore, when CDMA systems are constrained primarily by multiuser detection complexity, a multichannel CDMA communication system can support a much larger population of simultaneous users than the traditional single channel CDMA system, while reducing the multiuser detection complexity to a more desirable level