Show simple item record

dc.contributor.authorGreig, Adam
dc.date.accessioned2018-04-17T09:24:17Z
dc.date.available2018-04-17T09:24:17Z
dc.date.issued2018-05-19
dc.date.submitted2017-09-18
dc.identifier.urihttps://www.repository.cam.ac.uk/handle/1810/274917
dc.description.abstractSparse 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.
dc.description.sponsorshipFunded by a Doctoral Training Award from the Engineering and Physical Sciences Research Council.
dc.language.isoen
dc.rightsAttribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)
dc.rights.urihttps://creativecommons.org/licenses/by-nc-sa/4.0/
dc.subjectsparse regression codes
dc.subjectinformation theory
dc.subjectcommunication
dc.subjectcompressed sensing
dc.subjectcapacity-achieving codes
dc.subjectmultiuser information theory
dc.subjectapproximate message passing
dc.titleDesign Techniques for Efficient Sparse Regression Codes
dc.typeThesis
dc.type.qualificationlevelDoctoral
dc.type.qualificationnameDoctor of Philosophy (PhD)
dc.publisher.institutionUniversity of Cambridge
dc.publisher.departmentDepartment of Engineering
dc.date.updated2018-04-10T18:54:39Z
dc.identifier.doi10.17863/CAM.22068
dc.contributor.orcidGreig, Adam [0000-0002-7290-4063]
dc.publisher.collegeSelwyn College
dc.type.qualificationtitleDoctor of Philosophy
cam.supervisorVenkataramanan, Ramji
cam.thesis.fundingtrue
rioxxterms.freetoread.startdate2018-04-10


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)
Except where otherwise noted, this item's licence is described as Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)