Reliable uncoded communication in the underdetermined SIMO MAC with low-complexity decoding

We consider a single input multiple output (SIMO) multiple access channel with a large number of transmitters sending symbols from a constellation to the receiver of a multi-antenna base station. We investigate the fundamental limits of joint decoding of the signals from all the users using a low complexity convex relaxation of the maximum likelihood decoder (constellation search). We show that in a rich scattering environment, and in the asymptotic limit of a large number of transmitters, reliable communication is possible even without employing coding at the transmitters. This holds even when the number of receiver antennas per transmitter is arbitrarily small, with scaling behaviour arbitrarily close to what is achievable with coding. Thus, the diversity of a large system not only makes coded performance similar to that of uncoded performance, but also allows efficient decoders to realize near-optimal performance. With the proposed low-complexity decoder however, we do lose the exponential or near-exponential rates of decay of error probability of the ML decoder.