Performance-Complexity Analysis for MAC ML-Based Decoding with User Selection

Hsiao-Feng Lu, Petros Elia, Arun Kumar Singh

Research output: Contribution to journalArticlepeer-review


The rate-reliability-complexity limits of a quasi-static K-user multiple access channel (MAC), with or without feedback, are explored in this paper. Using high-SNR asymptotics, bounds on the computational resources required to achieve near-optimal (ML-based) decoding performance are first derived. They, in turn, yield bounds on the (reduced) complexity needed to achieve any (including suboptimal) diversity-multiplexing tradeoff (DMT) performance. Similar complexity-bounds in the presence of feedback-aided user selection are also given. This latter effort reveals the ability of a few bits of feedback not only to improve performance, but also to reduce complexity. In this context, our analysis reveals the interesting finding that a proper calibration of user selection can allow for near-optimal ML-based decoding, with complexity that need not scale exponentially in the total number of codeword bits. The derived bounds constitute the best known performance-versus-complexity behavior to date for ML-based MAC decoding, as well as a first exploration of the complexity-feedback-performance interdependencies in multiuser settings.

Original languageEnglish
Article number7358145
Pages (from-to)1867-1880
Number of pages14
JournalIEEE Transactions on Signal Processing
Issue number7
StatePublished - 1 Apr 2016


  • Complexity exponent
  • User selection
  • diversity-multiplexing tradeoff
  • multiple access channel
  • performance-complexity tradeoff


Dive into the research topics of 'Performance-Complexity Analysis for MAC ML-Based Decoding with User Selection'. Together they form a unique fingerprint.

Cite this