Sparse superposition codes were recently introduced by Barron and Joseph for reliable communication over the additive white Gaussian noise (AWGN) channel at rates approaching the channel capacity. The codebook is defined in terms of a Gaussian design matrix, and codewords are sparse linear combinations of columns of the matrix. In this paper, we propose an approximate message passing decoder for sparse superposition codes, whose decoding complexity 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 with an appropriate power allocation. Simulation results are provided to demonstrate the performance of the decoder at finite blocklengths. We introduce a power allocation scheme to improve the empirical performance, and demonstrate how the decoding complexity can be significantly reduced by using Hadamard design matrices.
An approximate message passing decoder for sparse superposition codes was recently proposed by Barbier and Krzakala in @cite_14 . This decoder has different update rules from the AMP proposed here. A replica-based analysis of the decoder in @cite_14 suggested it could not achieve rates beyond a threshold which was strictly smaller than @math . Subsequently, @cite_23 reported empirical results which show that the performance of the decoder in @cite_14 can be improved by using spatially coupled Hadamard matrices to define the code.
@cite_14 @cite_23
2088934832 1909826856
Superposition codes are efficient for the Additive White Gaussian Noise channel. We provide here a replica analysis of the performances of these codes for large signals. We also consider a Bayesian Approximate Message Passing decoder based on a belief-propagation approach, and discuss its performance using the density evolution technic. Our main findings are 1) for the sizes we can access, the message-passing decoder outperforms other decoders studied in the literature 2) its performance is limited by a sharp phase transition and 3) while these codes reach capacity as @math (a crucial parameter in the code) increases, the performance of the message passing decoder worsen as the phase transition goes to lower rates. We study the approximate message-passing decoder for sparse superposition coding on the additive white Gaussian noise channel and extend our preliminary work. We use heuristic statistical-physics-based tools, such as the cavity and the replica methods, for the statistical analysis of the scheme. While superposition codes asymptotically reach the Shannon capacity, we show that our iterative decoder is limited by a phase transition similar to the one that happens in low density parity check codes. We consider two solutions to this problem, that both allow to reach the Shannon capacity: 1) a power allocation strategy and 2) the use of spatial coupling, a novelty for these codes that appears to be promising. We present, in particular, simulations, suggesting that spatial coupling is more robust and allows for better reconstruction at finite code lengths. Finally, we show empirically that the use of a fast Hadamard-based operator allows for an efficient reconstruction, both in terms of computational time and memory, and the ability to deal with very large messages.