Multiple Access Demodulation in the Lifted Signal Graph With Spatial Coupling

Demodulation in a random multiple access channel is considered where the signals are chosen uniformly randomly with unit energy. It is shown that by lifting (replicating) the graph of this system and randomizing the graph connections, a simple iterative cancellation demodulator achieves the same performance as an optimal symbol-by-symbol detector of the original system. The iterative detector has a complexity that is linear in the number of users, while the direct optimal approach is known to be NP-hard. However, the maximal system load of this lifted graph is limited to α <; 2.07, even for large signal-to-noise ratios (SNRs)-the system is interference limited. Spatial coupling between subsequent lifted graphs is introduced, and anchoring the initial graphs, the achievable system load α can go to infinity as the SNR goes to infinity. Our results apply to several well-documented system proposals, such as interleave-division multiple access, partitioned spreading, and certain forms of multiple-input multiple-output communications.