Asymptotic gaps between BP decoding and local-MAP decoding for low-density parity-check codes

In this paper, we consider communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) codes. We consider MAP decoding not using a whole Tanner graph but only a neighborhood graph of fixed depth referred to as local-MAP decoding for deriving lower bounds of the error probability under message-passing decoding and bit-flipping decoding. The main result of this paper is to derive an asymptotic performance for regular ensembles under local-MAP decoding and to derive an asymptotic gap of the bit error probability between belief propagation (BP) and local-MAP decoding for irregular ensembles. Finally, we show the limit of the scaling parameter of these decodings when number of iterations tends to infinity.