Paper detail

Effects of Single-Cycle Structure on Iterative Decoding for Low-Density Parity-Check Codes

We consider communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) codes and belief propagation (BP) decoding. For fixed numbers of BP iterations, the bit error probability approaches a limit as blocklength tends to infinity, and the limit is obtained via density evolution. On the other hand, the difference between the bit error probability of codes with blocklength $n$ and that in the large blocklength limit is asymptotically $α(ε,t)/n + Θ(n^{-2})$ where $α(ε,t)$ denotes a specific constant determined by the code ensemble considered, the number $t$ of iterations, and the erasure probability $ε$ of the BEC. In this paper, we derive a set of recursive formulas which allows evaluation of the constant $α(ε,t)$ for standard irregular ensembles. The dominant difference $α(ε,t)/n$ can be considered as effects of cycle-free and single-cycle structures of local graphs. Furthermore, it is confirmed via numerical simulations that estimation of the bit error probability using $α(ε,t)$ is accurate even for small blocklengths.