Speed and accuracy comparison of techniques for multiuser detection in synchronous CDMA

In this letter, we compare the complexity and efficiency of several methods used for multiuser detection in a synchronous code-division multiple-access system. Various methods are discussed, including decision-feedback (DF) detection, group decision-feedback (GDF) detection, coordinate descent, quadratic programming with constraints, space-alternating generalized EM (SAGE) detection, Tabu search, a Boltzmann machine detector, semidefinite relaxation, probabilistic data association (PDA), branch and bound (BBD), and the sphere decoding (SD) method. The efficiencies of the algorithms, defined as the probability of group detection error divided by the number of floating point computations, are compared under various situations. Of particular interest is the appearance of an "efficient frontier" of algorithms, primarily composed of DF detector, GDF detector, PDA detector, the BBD optimal algorithm, and the SD method. The efficient frontier is the convex hull of algorithms as plotted on probability of error versus computational demands axes: algorithms not on this efficient frontier can be considered dominated by those that are.