Polynomial complexity optimal detection of certain multiple-access systems
Christian B. Schlegel, Alex J. Grant · IEEE Transactions on Information Theory · 2000
It is demonstrated that optimal multiple-user detection in a linear multiple-access system with identical crosscorrelations requires only /spl Oscr/(KlogK) operations instead of the worst case O(2/sup K/). A simple optimal detection algorithm is given, which when generalized has a complexity that is exponential not in the number of users but in the number of unique crosscorrelation values.