Polynomial complexity optimal detection for oversaturated M-ary complex-valued Multiple-Access systems

The optimal multiuser detection (OMD) for binary Multiple-Access (MA) system can be posed as a binary quadratic programming (BQP) which belongs to a nondeterministic polynomial-time hard (NP-hard) problem unless the systems have some special structures. While, the OMD for PAM real-valued MA system can be posed as an integer quadratic programming (IQP) which is a problem much more difficult than BQP. Furthermore, the most generalized MA system is the M-ary complex-valued system and the OMD for this system can be posed as a complex-valued integer quadratic programming (CIQP). To the best of our knowledge, the optimal detector with polynomial complexity has never been presented for any nonorthogonal Mary complex-valued MA system. In this paper, we focus our interests on a certain M-ary complex-valued nonorthogonal MA system with a hierarchical structure of the signature waveform set. The OMD for this system can be posed as a CIQP. By using two properties of the hierarchical signature waveform set, we propose a polynomial complexity detector which can solve this CIQP optimally.