Capacity-achieving Sparse Regression Codes via approximate message passing decoding

Change log
Rush, Cynthia 
Greig, Adam 
Venkataramanan, Ramji  ORCID logo

Sparse superposition codes were recently introduced by Barron and Joseph for reliable communication over the AWGN channel at rates approaching the channel capacity. In this code, the codewords are sparse linear combinations of columns of a design matrix. In this paper, we propose an approximate message passing decoder for sparse superposition codes. The complexity of the decoder scales linearly with the size of the design matrix. The performance of the decoder is rigorously analyzed and it is shown to asymptotically achieve the AWGN capacity. We also provide simulation results to demonstrate the performance of the decoder at finite block lengths, and introduce a power allocation that significantly improves the empirical performance.

4613 Theory Of Computation, 46 Information and Computing Sciences, 4006 Communications Engineering, 40 Engineering
Journal Title
2015 IEEE International Symposium on Information Theory (ISIT)
Conference Name
2015 IEEE International Symposium on Information Theory (ISIT)
Journal ISSN
Volume Title
European Commission (631489)
RV would like to acknowledge support from a Marie Curie Career Integration Grant (GA Number 631489). AG is supported by an EPSRC Doctoral Training Award.