Low complexity optimal multiple access joint detection for linearly dependent user sets

The general problem of joint detection of linearly dependent users in an uncoded multiple access (MA) system is N-P hard. We look to exploit the existing structure in our problem so that low complexity algorithms may be devised to yield the optimal solution. Advantage is taken over the design of user signatures in a typical MA communication system. By imposing a hierarchical cross-correlation structure on the user signature waveforms, the receiver design problem is reduced so that it is no longer N-P complete. A tree joint detection algorithm which takes advantage of such a cross-correlation structure is presented. The tree detector gives the optimal estimate with an extremely low computational complexity that is typically low-order-polynomial in the number of users. This is an enormous savings in computations over the O(2^K) computations needed if the signatures did not exhibit any structure