Message-passing decoding beyond the girth with local-optimality guarantees

We present a new message-passing iterative decoding algorithm, called normalized weighted min-sum (NWMS). NWMS-decoding is a BP-type algorithm that applies to any irregular Tanner code with single parity-check local codes (e.g., LDPC codes and HDPC codes). The decoding guarantee of NWMS applies whenever there exists a locally optimal codeword. We prove that if a locally-optimal codeword with respect to height parameter h exists, then NWMS-decoding finds it in h iterations. This decoding guarantee holds for every finite value of h and is not limited by the girth. Because local optimality of a codeword implies that it is the unique ML-codeword, the decoding guarantee also has an ML-certificate.