Open AccessA Polynomial Complexity Optimal Multiuser Detection Algorithm Based on Monotonicity Properties
Author(s) -
Quan Qingyi
Publication year - 2010
Publication title -
etri journal
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.295
H-Index - 46
eISSN - 2233-7326
pISSN - 1225-6463
DOI - 10.4218/etrij.10.0209.0503
Subject(s) - monotonic function , algorithm , sequence (biology) , ranking (information retrieval) , mathematics , computational complexity theory , time complexity , monotone polygon , correlation , multiuser detection , class (philosophy) , polynomial , mathematical optimization , computer science , code division multiple access , artificial intelligence , mathematical analysis , telecommunications , genetics , geometry , biology
An optimal multiuser detection algorithm with a computational complexity of O(K log K) is proposed for the class of linear multiple‐access systems which have constant cross‐correlation values. Here the optimal multiuser detection is implemented by searching for a monotone sequence with maximum likelihood, under the ranking of sufficient statistics. The proposed algorithm is intuitive and concise. It is carried out in just two steps, and at each step only one kind of operation is performed. Also, the proposed algorithm can be extended to more complex systems having more than a single cross‐correlation value.