2026-09-22T14:55:17Zhttps://api.repository.cam.ac.uk/server/oai/request

oai:www.repository.cam.ac.uk:1810/2749172019-01-30T12:14:48Zcom_1810_213729com_1810_256065col_1810_219485

Design Techniques for Efficient Sparse Regression Codes 10.17863/CAM.22068 Greig, Adam 0000000272904063 Venkataramanan, Ramji Sparse regression codes (SPARCs) are a recently introduced coding scheme for the additive white Gaussian noise channel, for which polynomial time decoding algorithms have been proposed which provably achieve the Shannon channel capacity. One such algorithm is the approximate message passing (AMP) decoder. However, directly implementing these decoders does not yield good empirical performance at practical block lengths. This thesis develops techniques for improving both the error rate performance, and the time and memory complexity, of the AMP decoder. It focuses on practical and efficient implementations for both single- and multi-user scenarios. A key design parameter for SPARCs is the power allocation, which is a vector of coefficients which determines how codewords are constructed. In this thesis, novel power allocation schemes are proposed which result in several orders of magnitude improvement to error rate compared to previous designs. Further improvements to error rate come from investigating the role of other SPARC construction parameters, and from performing an online estimation of a key AMP parameter instead of using a pre-computed value. Another significant improvement to error rates comes from a novel three-stage decoder which combines SPARCs with an outer code based on low-density parity-check codes. This construction protects only vulnerable sections of the SPARC codeword with the outer code, minimising the impact to the code rate. The combination provides a sharp waterfall in bit error rates and very low overall codeword error rates. Two changes to the basic SPARC structure are proposed to reduce computational and memory complexity. First, the design matrix is replaced with an efficient in-place transform based on Hadamard matrices, which dramatically reduces the overall decoder time and memory complexity with no impact on error rate. Second, an alternative SPARC design is developed, called Modulated SPARCs. These are shown to also achieve the Shannon channel capacity, while obtaining similar empirical error rates to the original SPARC, and permitting a further reduction in time and memory complexity. Finally, SPARCs are implemented for the broadcast and multiple access channels, and for the multiple description and Wyner-Ziv source coding models. Designs for appropriate power allocations and decoding strategies are proposed and are found to give good empirical results, demonstrating that SPARCs are also well suited to these multi-user settings. University of Cambridge 2018-05-19 Thesis Doctoral Doctor of Philosophy (PhD) en Funded by a Doctoral Training Award from the Engineering and Physical Sciences Research Council. https://www.repository.cam.ac.uk/handle/1810/274917 https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/3e4a09a3-4dea-4ac4-ad59-e7a31e6b3e75/download 87eda9de84448d1f82354d60eee3eb5f https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/9561a3aa-fd1c-446c-be8e-081e81877502/download f04ac7f937a2b137ba843622938c0df4 https://creativecommons.org/licenses/by-nc-sa/4.0/ sparse regression codes information theory communication compressed sensing capacity-achieving codes multiuser information theory approximate message passing