Effects of Single-Cycle Structure on Iterative Decoding of 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 the blocklength tends to infinity, and the limit is obtained via density evolution. The finite-blocklength correction behaves like $alpha(epsilon,t)+Theta(n^{-2})$ as the blocklength $n$ tends to infinity where $alpha(epsilon,t)$ denotes a specific constant determined by the code ensemble considered, the number $t$ of iterations, and the erasure probability $epsilon$ of the BEC. In this paper, we derive a set of recursive formulas which allows the evaluation of the constant $alpha(epsilon,t)$ for standard irregular ensembles. The dominant difference $alpha(epsilon,t)$ 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 $alpha(epsilon,t)$ is accurate even for small blocklengths.