LOW-COMPLEXITY OPTIMAL JOINT DETECTION FOR OVERSATURATED MULTIPLE-ACCESS COMMUNICATIONS

Optimal joint detection for interfering (nonorthogonal) users in a mul tiple access communication system has, in general, a computational com plexity that is exponential in the number of users, For this reason, o ptimal joint detection has been thought to be impractical for large nu mbers of users, A number of suboptimal low-complexity joint detectors have been proposed for direct sequence spread spectrum user waveforms that have properties suitable for mobile cellular and other systems, T here are, however, other systems, such as satellite systems, for which other waveforms may be considered, This paper shows that there are us er signature set selections that enable optimal joint detection that i s extremely low in complexity, When a hierarchical cross-correlation s tructure is imposed on the user waveforms, optimal detection can be ac hieved with a tree-structured receiver having complexity that is, in t ypical cases, a low-order-polynomial in the number of users, This is a huge savings over the exponential complexity needed for the optimal d etection of general signals, Work in recent literature has shown that a hierarchically structured signal set can achieve oversaturation (mor e users than dimensions) with no growth in required signal-to-noise ra tio, The proposed tree detector achieves low-complexity optimal joint detection even in this oversaturated case.