The Stability of Low-Density Parity-Check Codes and Some of its Consequences

We study the stability of low-density parity-check codes under blockwise or bitwise maximum a posteriori decoding, 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 Luby et 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 maximum a posteriori decoding as well. We demonstrate how the stability threshold can determine an upper bound on the corresponding blockwise or bitwise maximum a posteriori threshold, revealing the operational significance of the stability threshold.

On the Universality of Low-Density Parity-Check Block Codes

Wei Liu, Rüdiger Urbanke

An important class of modern channel codes is the capacity-achieving sequences of low-density parity-check block codes. Such sequences are usually designed for the binary erasure channel and are decoded by iterative message-passing algorithms. In this paper we investigate the universality of such sequences. We show that many existing capacity-achieving sequences designed for the binary erasure channel do not achieve the same capacity of many other binary-input memoryless output-symmetric channels under belief propagation decoding.

IEEE2020

Finite-length analysis of various low-density parity-check ensembles for the binary erasure channel

Mohammad Amin Shokrollahi, Rüdiger Urbanke

We investigate the average erasure probability of the belief propagation algorithm over the binary erasure channel (BEC) for various finite-length low- density parity-check (LDPC) ensembles. In particular, we give tight upper bounds on the "error floor", i.e., on the contribution to the erasure probability stemming from relatively small deficiencies in the graph. We also define and analyse "expurgated" ensembles and give upper bounds on the error floor of "typical" codes. Finally, we show that typical codes of properly chosen ensembles have an erasure correcting radius which grows linearly in the block length. The presented method provides valuable insight into how finite- length codes should be designed. Although the standard ensemble can achieve capacity on the BEC, the construction of good finite-length codes requires careful control of the structure of the degree two variable nodes. In this paper, we investigate the standard ensemble, the Poisson ensemble, an ensemble in which degree two nodes are added in a cycle, and an ensemble in which different degree two variable nodes have distinct neighboring check nodes.

2002

Threshold Saturation via Spatial Coupling: Why Convolutional LDPC Ensembles Perform So Well over the BEC

Shrinivas Kudekar, Rüdiger Urbanke

Convolutional low-density parity-check (LDPC) ensembles, introduced by Felstrom and Zigangirov, have excellent thresholds and these thresholds are rapidly increasing functions of the average degree. Several variations on the basic theme have been proposed to date, all of which share the good performance characteristics of convolutional LDPC ensembles. We describe the fundamental mechanism that explains why "convolutional-like" or "spatially coupled" codes perform so well. In essence, the spatial coupling of individual codes increases the belief-propagation (BP) threshold of the new ensemble to its maximum possible value, namely the maximum a posteriori (MAP) threshold of the underlying ensemble. For this reason, we call this phenomenon "threshold saturation." This gives an entirely new way of approaching capacity. One significant advantage of this construction is that one can create capacity-approaching ensembles with an error correcting radius that is increasing in the blocklength. Although we prove the "threshold saturation" only for a specific ensemble and for the binary erasure channel (BEC), empirically the phenomenon occurs for a wide class of ensembles and channels. More generally, we conjecture that for a large range of graphical systems a similar saturation of the "dynamical" threshold occurs once individual components are coupled sufficiently strongly. This might give rise to improved algorithms and new techniques for analysis.

2011