Using List Decoding to Improve the Finite-Length Performance of Sparse Regression Codes
Authors:
- Haiwen CaoHCHaiwen Cao
- Pascal O. VontobelPVPascal O. Vontobel
Preprint
Abstract
We consider sparse superposition codes (SPARCs) over complex AWGN channels. Such codes can be efficiently decoded by an approximate message passing (AMP) decoder, whose performance can be predicted via so-called state evolution in the large-system limit. In this paper, we mainly focus on how to use concatenation of SPARCs and cyclic redundancy check (CRC) codes on the encoding side and use list decoding on the decoding side to improve the finite-length performance of the AMP decoder for SPARCs over complex AWGN channels. Simulation results show that such a concatenated coding scheme works much better than SPARCs with the original AMP decoder and results in a steep waterfall-like behavior in the bit-error rate performance curves. Besides that, we also introduce a novel class of design matrices, i.e., matrices that describe the encoding process, based on circulant matrices derived from Frank or from Milewski sequences. This class of design matrices has comparable encoding and decoding computational complexity as well as very close performance with the commonly-used class of design matrices based on discrete Fourier transform (DFT) matrices, but gives us more degrees of freedom when designing SPARCs for various applications.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- The Error Probability of Sparse Superposition Codes With Approximate Message Passing DecodingIEEE Transactions on Information Theory, 2018
- Techniques for Improving the Finite Length Performance of Sparse Superposition CodesIEEE Transactions on Communications, 2017
- Capacity-Achieving Sparse Superposition Codes via Approximate Message Passing DecodingIEEE Transactions on Information Theory, 2017
- Lossy Compression via Sparse Linear Regression: Computationally Efficient Encoding and DecodingIEEE Transactions on Information Theory, 2014
- Lossy Compression via Sparse Linear Regression: Performance Under Minimum-Distance EncodingIEEE Transactions on Information Theory, 2014
- Fast Sparse Superposition Codes Have Near Exponential Error Probability for $R<{\cal C}$IEEE Transactions on Information Theory, 2013
- Least Squares Superposition Codes of Moderate Dictionary Size Are Reliable at Rates up to CapacityIEEE Transactions on Information Theory, 2012
- The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed SensingIEEE Transactions on Information Theory, 2011
- Periodic Sequences with Optimal Properties for Channel Estimation and Fast Start-Up EqualizationIBM Journal of Research and Development, 1983
- Phase shift pulse codes with good periodic correlation properties (Corresp.)IEEE Transactions on Information Theory, 1962