Title :
Polynomial complexity optimal detection of certain multiple-access systems
Author :
Schlegel, Christian ; Grant, Alex
Author_Institution :
Dept. of Electr. Eng., Utah Univ., Salt Lake City, UT, USA
fDate :
9/1/2000 12:00:00 AM
Abstract :
It is demonstrated that optimal multiple-user detection in a linear multiple-access system with identical crosscorrelations requires only 𝒪(KlogK) operations instead of the worst case O(2K). 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
Keywords :
computational complexity; correlation methods; multi-access systems; multiuser channels; optimisation; polynomials; signal detection; CDMA; code-division multiple access; crosscorrelations; exponential complexity; linear multiple-access system; optimal detection algorithm; optimal multiple-user detection; polynomial complexity optimal detection; Decoding; Detection algorithms; Entropy; Information theory; Polynomials; Statistics; Steganography; Testing; Watermarking;
Journal_Title :
Information Theory, IEEE Transactions on
