Design, Analysis and Applications of Capacity-Approaching Codes on Graphsfor Erasure Channels

Abstract

<p>For the last several years, three topics dominated the field of coding theory: lowdensity<br />parity-check (LDPC) codes, fountain codes and network coding. Although<br />the first two representmodern developments in the error-correction coding,whereas<br />the third topic, as originally studied, is not concernedwith the error-correction problems,<br />these topics are intimately related. Theirmutual goal is to achieve the capacity<br />limits, either for the single-user or for the multi-user (network) scenario. In this thesis,<br />we study the selected problems from each of these topics.<br />As the first problem,we study the design of optimal finite-length irregular LDPC<br />codes. Our goal is to identify a subset of the selected irregular LDPC code ensemble<br />containing the codes of excellent error-correcting performance, aswell as to develop<br />code design algorithms that output the LDPC codes from this subset. Following the<br />work of Tian et al (Tian et al. 2004), we introduce the ACE spectrum of LDPC codes<br />as an efficient tool for evaluation of finite-length irregular LDPC codes. Classifying<br />LDPC codes with respect to their ACE spectra, we identify the set of LDPC codes<br />with extremal ACE spectrum properties as the subset of our interest. We propose<br />the generalized ACE constrained design algorithm to design LDPC codes from this<br />subset. In parallel, motivated by the work of Hu et al (Hu et al. 2005), we search<br />for an efficient way to design LDPC codes with excellent ACE spectrum properties<br />through the progressive edge-growth (PEG) code design. By introducing a generalized<br />framework in PEG code design, we propose a PEG algorithm version that<br />outputs LDPC codes with excellent ACE spectrum properties and error-correcting<br />performance.<br />In the field of fountain coding, we are mainly concerned with the important<br />question of design of unequal error protection (UEP) fountain codes. We propose<br />the expanding window fountain (EWF) codes as a simple and effective solution to<br />the UEP fountain code design problem. We provide an asymptotic analysis of EWF<br />codes, presenting their excellent UEP performance both analytically and by simulation<br />results. The design flexibility of EWF codes is demonstrated,where the erasurecorrecting performance of different data importance classes can be &ldquo;finely tuned&rdquo;<br />using numerous EWF code design parameters. EWF codes are shown to be ideally<br />suited as a forward error correction (FEC) solution for the delay-constrained scalable<br />source data multicasting over lossy packet networks to heterogeneous receiver<br />classes. We demonstrate their applicability, providing their performance analysis,<br />in the scenario of scalable image and video multicasting.<br />Finally, we are interested in low-complexity network coding schemes for the data<br />collection in wireless sensor networks. We are primarily concerned with the binary<br />sparse network coding schemes, a problem related to the data distribution using<br />fountain codes. Network coding principles are particularly useful in the limitedcomplexity<br />sensor networks enviroment, where the data collection can be implemented<br />as a low-complexity distributed operation of sensor nodes, avoiding the<br />problems related to data routing. Our work in this field is at its early stage; this part<br />of the thesis is mostly pointed towards the discussion of our ongoing and future<br />work and interests.</p>