Coupled LDPC codes: Complexity aspects of threshold saturation
Michael Lentmaier, Gerhard Paul Fettweis · 2011
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.