The Error Probability of Sparse Superposition Codes with Approximate Message Passing Decoding
View / Open Files
Publication Date
2019-05Journal Title
IEEE Transactions on Information Theory
ISSN
0018-9448
Publisher
IEEE
Type
Article
This Version
AM
Metadata
Show full item recordCitation
Rush, C., & Venkataramanan, R. (2019). The Error Probability of Sparse Superposition Codes with Approximate Message Passing Decoding. IEEE Transactions on Information Theory https://doi.org/10.1109/TIT.2018.2882177
Abstract
Sparse superposition codes, or sparse regression codes (SPARCs), are a recent class of codes for reliable communication over the AWGN channel at rates approaching the channel capacity. Approximate
message passing (AMP) decoding, a computationally efficient technique for decoding SPARCs, has been proven to be asymptotically capacity-achieving for the AWGN channel. In this paper, we refine the asymptotic result by deriving a large deviations bound on the probability of AMP decoding error. This bound gives insight into the error performance of the AMP decoder for large but finite problem sizes, giving an error exponent as well as guidance on how the code parameters should be chosen at finite block lengths. For an appropriate choice of code parameters, we show that for any fixed rate less than the channel capacity, the decoding error probability decays exponentially in $n/(\log n)^{2T}$, where $T$, the number of AMP iterations required for successful decoding, is bounded in terms of the gap from capacity.
Sponsorship
European Commission (631489)
Engineering and Physical Sciences Research Council (EP/N013999/1)
Isaac Newton Trust (1540 (R))
Identifiers
External DOI: https://doi.org/10.1109/TIT.2018.2882177
This record's URL: https://www.repository.cam.ac.uk/handle/1810/286767
Rights
Licence:
http://www.rioxx.net/licenses/all-rights-reserved
Statistics
Total file downloads (since January 2020). For more information on metrics see the
IRUS guide.