<p>Recently, low-density parity-check (LDPC) codes have attracted much attention because of their excellent error correcting performance and highly parallelizable decoding scheme. However, the effective VLSI implementation of and LDPC decoder remains a big challenge and is a crucial issue in determining how well we can exploit the benefits of the LDPC codes in the real applications. In this master thesis report, following a error coding background, we describe Low-Density Parity-Check codes and their decoding algorithm, and also requirements and architectures of LPDC decoder implementations.</p>

Recently, low-density parity-check (LDPC) codes have attracted much attention because of their excellent error correcting performance and highly parallelizable decoding scheme. However, the effective VLSI implementation of and LDPC decoder remains a big challenge and is a crucial issue in determining how well we can exploit the benefits of the LDPC codes in the real applications. In this master thesis report, following a error coding background, we describe Low-Density Parity-Check codes and their decoding algorithm, and also requirements and architectures of LPDC decoder implementations.

Fountain codes have demonstrated great results for the binary erasure channel and have already been incorporated into several international standards to recover lost packets at the application layer. These include multimedia broadcast/multicast sessions and digital video broadcasting on global internet-protocol. The rateless property of Fountain codes holds great promise for noisy channels. These are more sophisticated mathematical models representing errors on communications links rather than only erasures. The practical implementation of Fountain codes for these channels, however, is hampered by high decoding cost and delay. In this work we study trapping sets in Fountain codes over noisy channels and their effect on the decoding process. While trapping sets have received much attention for low-density parity-check (LDPC) codes, to our knowledge they have never been fully explored for Fountain codes. Our study takes into account the different code structure and the dynamic nature of Fountain codes. We show that 'error-free' trapping sets exist for Fountain codes. When the decoder is caught in an error-free trapping set it actually has the correct message estimate, but is unable to detect this is the case. Thus, the decoding process continues, increasing the decoding cost and delay for naught. The decoding process for rateless codes consists of one or more decoding attempts. We show that trapping sets may reappear as part of other trapping sets on subsequent decoding attempts or be defeated by the reception of more symbols. Based on our observations we propose early termination methods that use trapping set detection to obtain improvements in realized rate, latency, and decoding cost for Fountain codes. / Thesis (Master, Electrical & Computer Engineering) -- Queen's University, 2009-10-29 14:33:06.548

Large-dimensional communication systems are likely to play an important role in modern wireless communications, where dimensions can be in space, time, frequency and their combinations. Large dimensions can bring several advantages with respect to the performance of communication systems. Harnessing such large-dimension benefits in practice, however, is challenging. In particular, optimum signal detection gets prohibitively complex for large dimensions. Consequently, low-complexity detection techniques that scale well for large dimensions while achieving near-optimal performance are of interest. Belief Propagation (BP) is a technique that solves inference problems using graphical models. BP has been successfully employed in a variety of applications including computational biology, statistical signal/image processing, machine learning and artificial intelligence. BP is well suited in several communication problems as well; e.g., decoding of turbo codes and low-density parity check codes (LDPC), and multiuser detection. We propose a BP based algorithm for detection in large-dimension linear vector channels employing binary phase shift keying (BPSK) modulation, by adopting a Markov random field (MRF)graphical model of the system. The proposed approach is shown to achieve i)detection at low complexities that scale well for large dimensions, and ii)improved bit error performance for increased number of dimensions (a behavior we refer to as the ’large-system behavior’). As one application of the BP based approach, we demonstrate the effectiveness of the proposed BP algorithm for decoding non-orthogonal space-time block codes (STBC) from cyclic division algebras (CDA)having large dimensions. We further improve the performance of the proposed algorithm through damped belief propagation, where messages that are passed from one iteration to the next are formed as a weighted combination of messages from the current iteration and the previous iteration. Next, we extend the proposed BP approach to higher order modulation. through a novel scheme of interference cancellation. This proposed scheme exhibits large system behavior in terms of bit error performance, while being scalable to large dimensions in terms of complexity. Finally, as another application of the BP based approach, we illustrate the adoption and performance of the proposed BP algorithm for low-complexity near-optimal equalization in severely delay-spread UWBMIMO-ISI channels that are characterized by large number (tens to hundreds)of multipath components.