---
abstract: |
    Sparse superposition codes (SPARCs) are a class of codes for efficient communication over the AWGN channel at rates approaching the channel capacity. In a standard SPARC, codewords are sparse linear combinations of columns of an i.i.d. Gaussian design matrix, while in a spatially coupled SPARC the design matrix has a block-wise structure, where the variance of the Gaussian entries can be varied across blocks. A well-designed spatial coupling structure can significantly enhance the error performance of iterative decoding algorithms such as Approximate Message Passing (AMP).

    In this paper, we obtain a non-asymptotic bound on the probability of error of spatially coupled SPARCs with AMP decoding. Applying this bound to a simple band-diagonal design matrix, we prove that spatially coupled SPARCs with AMP decoding achieve the capacity of the AWGN channel. The bound also highlights how the decay of error probability depends on each design parameter of the spatially coupled SPARC.

    The asymptotic mean squared error (MSE) of the AMP decoder can be predicted via a deterministic recursion called state evolution. Our result provides the first proof that the MSE concentrates on the state evolution prediction for spatially coupled designs. Combined with the state evolution prediction, this result implies that spatially coupled SPARCs with the proposed band-diagonal design are capacity-achieving. The proof technique used to establish the main result is also used to obtain a concentration inequality for the MSE of AMP applied to compressed sensing with spatially coupled design matrices. Finally, we provide numerical simulation results that demonstrate the finite length error performance of spatially coupled SPARCs. The performance is compared with coded modulation schemes that use LDPC codes from the DVB-S2 standard.
author:
- 'Cynthia Rush[^1]'
- 'Kuan Hsieh[^2]'
- 'Ramji Venkataramanan[^3]'
title: ' Capacity-achieving Spatially Coupled Sparse Superposition Codes with AMP Decoding '
---

[^1]: Department of Statistics, Columbia University, New York, NY 10027, USA. Email: [cynthia.rush@columbia.edu]{}

[^2]: Department of Engineering, University of Cambridge, Cambridge CB2 1PZ, UK. Email: [kh525@cam.ac.uk]{}

[^3]: Department of Engineering, University of Cambridge, Cambridge CB2 1PZ, UK. Email: [ramji.v@eng.cam.ac.uk]{} This work was supported in part by an EPSRC Doctoral Training Award and a Turing Fellowship from the Alan Turing Institute. This paper was presented in part at the 2018 IEEE International Symposium on Information Theory and at the 2018 IEEE Information Theory Workshop.
