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.

This dissertation considers several coding techniques based on Reed-Solomon (RS) and low-density parity-check (LDPC) codes. These two prominent families of error-correcting codes have attracted a great amount of interest from both theorists and practitioners and have been applied in many communication scenarios. In particular, data storage systems have greatly benefited from these codes in improving the reliability of the storage media. The first part of this dissertation presents a unified framework based on rate-distortion (RD) theory to analyze and optimize multiple decoding trials of RS codes. Finding the best set of candidate decoding patterns is shown to be equivalent to a covering problem which can be solved asymptotically by RD theory. The proposed approach helps understand the asymptotic performance-versus-complexity trade-off of these multiple-attempt decoding algorithms and can be applied to a wide range of decoders and error models. In the second part, we consider spatially-coupled (SC) codes, or terminated LDPC convolutional codes, over intersymbol-interference (ISI) channels under joint iterative decoding. We empirically observe the phenomenon of threshold saturation whereby the belief-propagation (BP) threshold of the SC ensemble is improved to the maximum a posteriori (MAP) threshold of the underlying ensemble. More specifically, we derive a generalized extrinsic information transfer (GEXIT) curve for the joint decoder that naturally obeys the area theorem and estimate the MAP and BP thresholds. We also conjecture that SC codes due to threshold saturation can universally approach the symmetric information rate of ISI channels. In the third part, a similar analysis is used to analyze the MAP thresholds of LDPC codes for several multiuser systems, namely a noisy Slepian-Wolf problem and a multiple access channel with erasures. We provide rigorous analysis and derive upper bounds on the MAP thresholds which are shown to be tight in some cases. This analysis is a first step towards proving threshold saturation for these systems which would imply SC codes with joint BP decoding can universally approach the entire capacity region of the corresponding systems.

[pt] Os códigos IRA (Irregular Repeat-Accumulate) são uma classe de códigos criada com o objetivo de permitir codificação em tempo linear garantindo comunicação robusta a taxas próximas à capacidade do canal. Eles foram introduzidas por Jin, Khandekar and McEliece em 2000. O artigo no qual foram apresentados provou que os códigos IRA alcançavam a capacidade do canal de apagamento e mostravam desempenho cmparável ao dos códigos Turbo no canal AWGN (Additive White Gaussian Noise). Os desenvolvimentos teóricos por trás dos códigos IRA vieram da busca pelos primeiros códigos LDPC (Low Density Parity Check), ou códigos em grafos, que atingiriam a capacidade do canal AWGN. Os códigos LDPC - propostos originalmente por Robert Gallager em 1963 - se tornaram objeto de grande interesse nas últimas décadas após um longo período de ostracismo desde sua concepção, desenvolvendo seu potencial para codificação de canal em aplicações tão diversas quanto comunicações por satélite, redes sem fio e streaming via IP, bem como codificação distribuída de fonte. O objetivo desta dissertação é a avaliação dos códigos IRA e os efeitos de diferentes métodos de construção de grafos em seu desempenho. O uso das muitas variações do algoritmo PEG (Progressive Edge-Growth) foi testado em simulações no canal AWGN. / [en] Irregular Repeat-Accumulate codes are motivated by the challenge of providing a class of codes that use linear-time encoding and decoding while communicating reliably at rates close to channel capacity. They were introduced by Hui Jin, Khandekar and McEliece in 2000, their article proves that IRA codes achieve channel capacity for the binary erasure channel and exhibit remarkably good performance on the AWGN channel. The theoretical developments supporting IRA codes stem from the efforts ar the development of capacity achieving Low-Density Parity-Check codes. LDPC codes were first proposed by Robert Gallager in 1963 and became the subject of intense research during the past decade after being dormant for a long period since its conception. Efforts by many researchers have developed its potential for channel coding in applications as diverse as satellite communications, wireless networks and streaming over IP, as well as studies on its usage in Distributed Source Coding. The goal of this dissertation is the evaluation of IRA codes and the effects of different graph construction methods in its performance. The use of the many variations of the Progressive Edge-Growth algorithm with IRA codes was tested in simulations on the AWGN channel.