MCMC Decoding of LDPC Codes with BP Preprocessing

Monte Carlo Markov chain (MCMC) decoding is a randomized algorithm which has been proven to be near-optimal in terms of decoding error probability. However, the exponentially slow mixing rate of Markov chains seems to preclude MCMC decoding from applications concerning even short blocklength codes. In contrast, belief propagation (BP) is a deterministic algorithm that is empirically fast but sub-optimal in error rate when it is used to decode low-density parity-check (LDPC) codes. In this paper, a code-independent BP–MCMC hybrid decoder is devised for short-blocklength LDPC codes. Theoretical error analysis of the hybrid algorithm is provided. Preliminary experiments show that the preprocessing of BP successfully reduces the time complexity of MCMC decoding and hence significantly improves the applicability of MCMC decoders to short LDPC codes.