The Stability of Low-Density Parity-Check Codes and Some of its Consequences
Wei Liu, Rudiger L. Urbanke · IEEE Transactions on Information Theory · 2021
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.