We analyze the convergence behavior of iteratively decoded coupled LDPC codes from a complexity point of view. It can be observed that the thresholds of coupled regular LDPC codes approach capacity as the node degrees and the number L of coupled blocks tend to infinity. The absence of degree two variable nodes in these capacity achieving ensembles implies for any fixed L a doubly exponential decrease of the error probability with the number of decoding iterations I, which guarantees a vanishing block error probability as the overall length n of the coupled codes tends to infinity at a complexity of O(n log n). On the other hand, an initial number of iterations Ibris required until this doubly exponential decrease can be guaranteed, which for the standard flooding schedule increases linearly with L. This dependence of the decoding complexity on L can be avoided by means of efficient message passing schedules that account for the special structure of the coupled ensembles.
We analyze the convergence behavior of iteratively decoded coupled LDPC codes from a complexity point of view. It can be observed that the thresholds of coupled regular LDPC codes approach capacity as the node degrees and the number L of coupled blocks tend to infinity. The absence of degree two variable nodes in these capacity achieving ensembles implies for any fixed L a doubly exponential decrease of the error probability with the number of decoding iterations I, which guarantees a vanishing block error probability as the overall length n of the coupled codes tends to infinity at a complexity of O(n log n). On the other hand, an initial number of iterations Ibris required until this doubly exponential decrease can be guaranteed, which for the standard flooding schedule increases linearly with L. This dependence of the decoding complexity on L can be avoided by means of efficient message passing schedules that account for the special structure of the coupled ensembles.
Serial decoding schedules for low-density parity-check (LDPC) codes are described and analyzed. Conventionally, in each iteration all the variable nodes and subsequently all the check nodes send messages to their neighbors (“flooding schedule”). In contrast, in the considered methods, the updating of the nodes is implemented according to a serial schedule. The evolution of the decoding algorithm’s computation tree under serial scheduling is analyzed. The analysis shows that it grows twice as fast in comparison to the flooding schedule’s computation tree, indicating that the serial schedule propagates information twice as fast in the code’s underlying graph. Furthermore, asymptotic analysis of the serial schedule’s convergence rate is done using the Density Evolution (DE) algorithm. Applied to various ensembles of LDPC codes, it shows that when working near the ensemble’s threshold, for long enough codes the serial schedule is expected to converge in half the number of iterations compared to the standard flooding schedule. This observation is generally proved for the Binary Erasure Channel (BEC) under some likely assumptions. Finally, an accompanying concentration theorem is proved, justifying the asymptotic DE analysis assumptions. 1
Conventionally, in each low-density parity-check (LDPC) decoding iteration all the variable nodes and subsequently all the check nodes send messages to their neighbors (flooding schedule). An alternative, more efficient, approach is to update the nodes' messages serially (serial schedule). A theoretical analysis of serial message passing decoding schedules is presented. In particular, the evolution of the computation tree under serial scheduling is analyzed. It shows that the tree grows twice as fast in comparison to the flooding schedule's one, indicating that the serial schedule propagates information twice as fast in the code's underlying graph. Furthermore, an asymptotic analysis of the serial schedule's convergence rate is done using the density evolution (DE) algorithm. Applied to various ensembles of LDPC codes, it shows that for long codes the serial schedule is expected to converge in half the number of iterations compared to the standard flooding schedule, when working near the ensemble's threshold. This observation is generally proved for the binary erasure channel (BEC) under some natural assumptions. Finally, an accompanying concentration theorem is proved.
This paper investigates about the usefulness of a recently published low complexity upper bound on beliefpropagation decoding thresholds for a class of irregular lowdensity parity-check (LDPC) codes. In particular, the class considered is characterized by variable node degree distributions λ(x) of minimum degree i1 >2: being, in this case, λ′(0)=λ2=0, this is useful to design LDPC codes presenting a linear minimum distance growth with the block length with probability 1, as shown in Di et al.’s 2006 paper. These codes unfortunately cannot reach capacity under iterative decoding, since the achievement of capacity requires λ2=0. However, in this latter case, the block error probability might converge to a constant, as shown in the aforementioned paper.
Performance analysis for iterative decoders: In Chapter 7, we discuss the behavior of LDPC codes under iterative erasure decoding. When the blocklength goes to infinity, for many LDPC codes, the symbol error probability exhibits a so-called threshold phenomenon that is, there exists a certain channel erasure probability below which error-free communication is possible, while this is not guaranteed above it. We discuss how to compute this threshold for ensembles of LDPC codes on memoryless erasure channels. In the finite-length setting, one may observe a flattening of the symbol error rate curve owing to stopping sets – specific structures in the code’s bipartite graph. Knowing their number and size allows predicting this so-called error floor. Based on our findings, we discuss how to design good LDPC for memoryless erasure channels with extension to channels with memory.
This thesis addresses the topic of Low-Density Parity-Check (LDPC) code analysis, both asymptotically and for finite block lengths. Since in general it is a difficult problem to analyze individual code instances, ensemble averages are studied by following Gallager's original idea and results of Luby et al. Often, one can relate the insights gained by studying ensemble averages to statements regarding individual codes by proving that most elements in the ensemble behave "close" to the average. One important such average is the average weight distribution, another is the average pseudo-codeword distribution, where pseudo-codewords play the same role under iterative decoding as codewords do for maximum likelihood decoding. One of the main contributions of this thesis is the calculation of such averages for fully irregular LDPC code ensembles. Much of classical coding theory is aimed at the construction of codes with large minimum distance. This is so since away from capacity accurate bounds on the performance of a code can be given in terms of its minimum distance (or more generally, in terms of its weight distribution). Therefore, it is of interest to investigate what role the minimum distance plays for iteratively decoded LDPC code ensembles. In particular, sequences of capacity-achieving LDPC code ensembles of increasing length when transmission takes place over the Binary Erasure Channel (BEC) are investigated. It is shown that, under certain technical conditions, the minimum distance of such ensembles grows sub-linearly in the block length, a result which is somewhat surprising from a classical point of view. Specific attention is also given to the design of LDPC code ensembles, where an inherent trade-off is observed between achieving large minimum distance (which is relevant for the so called error-floor regime) and achieving a large threshold (which in the limit of long block lengths determines the worst channel on which transmission can be accomplished reliably). Most results on iterative coding systems to date address their asymptotic performance, i.e., their performance when the block length tends to infinity. For small and moderate block lengths the behavior of a code can deviate significantly from its asymptotic limit. It is therefore of high practical value to be able to analyze the finite-length performance of LDPC code ensembles. In this thesis, an exact such analysis is presented for iteratively decoded LDPC code ensembles over the BEC. In particular, expressions for the exact average bit and block erasure probabilities are computed by solving a set of recursions. Such an analysis is the starting point for a finite-length optimization, a topic which is slated for future work. The methods used in this thesis include a combinatorial approach (familiar to the coding society) as well as the powerful techniques developed in the statistical physics community, for example, the replica method or the mean-field approximation. Although the statistical physics techniques are ideally suited for the analysis of iterative coding systems, they are to date only accessible to a relatively small community. Therefore, an overview of these techniques is first presented using a language familiar to the coding theory community. Next, in order to highlight the differences and common points between the combinatorial and the statistical physics approaches, both techniques are applied to the weight distribution problem. It turns out that for regular ensembles, both methods yield the same result, while for irregular ensembles, they do differ in general.
This paper investigates the performance of a class of irregular low-density parity-check (LDPC) codes through a recently published low complexity upper bound on their beliefpropagation decoding thresholds. Moreover, their performance analysis is carried out through a recently published algorithmic method, presented in Babich et al. 2017 paper. In particular, the class considered is characterized by variable node degree distributions λ(x) of minimum degree i1>2: being, in this case, λ′(0)=λ2=0, this is useful to design LDPC codes presenting a linear minimum distance growth with the block length with probability 1, as shown in Di et al.’s 2006 paper. These codes unfortunately cannot reach capacity under iterative decoding, since the achievement of capacity requires λ2=0. However, in this latter case, the block error probability might converge to a constant, as shown in the aforementioned paper.