Oswald and Shokrollahi carried out a systematic study of capacity-achieving sequences of low-density parity-check (LDPC) codes for the binary erasure channel. Two quantities mu and Delta were suggested to measure the convergence speed of these sequences. They gave an upper bound of mu for a certain type of capacity-achieving sequences. In this correspondence, a lower bound of mu for this type of sequences is provided. It follows that, under a certain condition, the exact value of mu can be determined, which answers an open question posed by Oswald and Shokrollahi in their paper. If the condition is not satisfied the upper bound may not be tight. A counterexample is given.
Oswald and Shokrollahi carried out a systematic study of capacity-achieving sequences of low-density parity-check (LDPC) codes for the binary erasure channel. Two quantities mu and Delta were suggested to measure the convergence speed of these sequences. They gave an upper bound of mu for a certain type of capacity-achieving sequences. In this correspondence, a lower bound of mu for this type of sequences is provided. It follows that, under a certain condition, the exact value of mu can be determined, which answers an open question posed by Oswald and Shokrollahi in their paper. If the condition is not satisfied the upper bound may not be tight. A counterexample is given.
In this paper, we introduce new sequences (lambdan, rhon) of capacity achieving low-density parity-check (LDPC) code ensembles over the binary erasure channel (BEC). These sequences include the existing sequences by Shokrollahi as a special case. For a fixed code rate R, in the set of proposed sequences, Shokrollahipsilas sequences are superior to the rest of the set in that for any given value of n, their threshold is closer to the capacity upper bound 1 - R. For any given delta, 00, such that for any n > n0, the sequence (lambdan, rhon) requires a smaller maximum variable node degree as well as a smaller number of constituent variable node degrees to achieve a threshold within delta-neighborhood of the capacity upper bound 1 - R. Moreover, we prove that the check-regular subset of the proposed sequences are asymptotically quasi-optimal, i.e., their decoding complexity per iteration increases only logarithmically with the relative increase of the threshold. A stronger result on asymptotic optimality of some of the proposed sequences is also established.
In this paper, new sequences(λn,ρn)of capacity achieving low-density parity-check (LDPC) code ensembles over the binary erasure channel (BEC) is introduced. These sequences include the existing sequences by Shokrollahias a special case. For a fixed code rateR, in the set of proposed sequences, Shokrollahi's sequences are superior to the rest of the set in that for any given value ofn, their threshold is closer to the capacity upper bound1−R. For any given$\delta $,0<δ<1−R, however, there are infinitely many sequences in the set that are superior to Shokrollahi's sequences in that for each of them, there exists an integer numbern0, such that for anyn>n0, the sequence(λn,ρn)requires a smaller maximum variable node degree as well as a smaller number of constituent variable node degrees to achieve a threshold within$\delta $-neighborhood of the capacity upper bound1−R. Moreover, it is proven that the check-regular subset of the proposed sequences are asymptotically quasi-optimal, i.e., their decoding complexity increases only logarithmically with the relative increase of the threshold. A stronger result on asymptotic optimality of some of the proposed sequences is also established.
In the past decade, there has been tremendous amount of research on the analysis and design of the Low-Density Parity-Check (LDPC) codes with belief propagation decoding over different types of Binary-Input Output-Symmetric Memoryless (BIOSM) channels. However, with the exception of the Binary Erasure Channel (BEC), analytical results on LDPC codes over such channels are limited and most results are based on numerical methods and optimization. In particular, systematic design of provably capacity achieving sequences of LDPC code ensembles over general class of BIOSM channels has remained a fundamental open problem. Such sequences have been designed only for the binary erasure channel (BEC). In this paper, we first prove some novel analytical properties of the LDPC code ensembles over BIOSM channels. In particular, we prove a result that generalizes the previously known stability condition over symmetric channels. This suggests that a modified version of the flatness condition, a property which has been shown to be critical for capacity achieving sequences over the BEC, can be used to devise capacity achieving sequences for general class of BIOSM channels. Based on this assumption, we propose a method which could result in the systematic design of such sequences over BIOSM channels. Numerical evidence is promising and provides a consistent convergence behavior to capacity over the considered BIOSM channels as the average check node degree increases.
We study the stability of low-density parity-check codes under blockwise or bitwise maximuma posterioridecoding, where transmission takes place over a binary-input memoryless output-symmetric channel. Our study stems from the consideration of constructing universal capacity-achieving codes under low-complexity decoding algorithms, where universality refers to the fact that we are considering a family of channels with equal capacity. Consider, e.g., the right-regular sequence by Shokrollahi and the heavy-tail Poisson sequence by Lubyet al. Both sequences are provably capacity-achieving under belief propagation decoding when transmission takes place over the binary erasure channel. In this paper we show that many existing capacity-achieving sequences of low-density parity-check codes are not universal under belief propagation decoding. We reveal that the key to showing this non-universality result is determined by the stability of the underlying codes. More concretely, for an ordered and complete channel family and a sequence of low-density parity-check code ensembles, we determine a stability threshold associated with them, which gives rise to a sufficient condition under which the sequence is not universal under belief propagation decoding. Moreover, we show that the same stability threshold applies to blockwise or bitwise maximuma posterioridecoding as well. We demonstrate how the stability threshold can determine an upper bound on the corresponding blockwise or bitwise maximuma posteriorithreshold, revealing the operational significance of the stability threshold.
Assuming iterative decoding for binary erasure channels (BECs), a novel tree-based technique for upper bounding the bit error rates (BERs) of arbitrary, finite low-density parity-check (LDPC) codes is provided and the resulting bound can be evaluated for all operating erasure probabilities, including both the waterfall and the error floor regions. This upper bound can also be viewed as a narrowing search of stopping sets, which is an approach different from the stopping set enumeration used for lower bounding the error floor. When combined with optimal leaf-finding modules, this upper bound is guaranteed to be tight in terms of the asymptotic order. The Boolean framework proposed herein further admits a composite search for even tighter results. For comparison, a refinement of the algorithm is capable of exhausting all stopping sets of size les 13 for irregular LDPC codes of length n ap 500, which requires (13500) ap 1.67 times 1025trials if a brute force approach is taken. These experiments indicate that this upper bound can be used both as an analytical tool and as a deterministic worst-performance (error floor) guarantee, the latter of which is crucial to optimizing LDPC codes for extremely low BER applications, e.g., optical/satellite communications
We derive lower bounds on the density of parity-check matrices of binary linear codes which are used over memoryless binary-input output-symmetric (MBIOS) channels. The bounds are expressed in terms of the gap between the rate of these codes for which reliable communications is achievable and the channel capacity; they are valid for every sequence of binary linear block codes if there exists a decoding algorithm under which the average bit-error probability vanishes. For every MBIOS channel, we construct a sequence of ensembles of regular low-density parity-check (LDPC) codes, so that an upper bound on the asymptotic density of their parity-check matrices scales similarly to the lower bound. The tightness of the lower bound is demonstrated for the binary erasure channel by analyzing a sequence of ensembles of right-regular LDPC codes which was introduced by Shokrollahi, and which is known to achieve the capacity of this channel. Under iterative message-passing decoding, we show that this sequence of ensembles is asymptotically optimal (in a sense to be defined in this paper), strengthening a result of Shokrollahi. Finally, we derive lower bounds on the bit-error probability and on the gap to capacity for binary linear block codes which are represented by bipartite graphs, and study their performance limitations over MBIOS channels. The latter bounds provide a quantitative measure for the number of cycles of bipartite graphs which represent good error-correction codes.