Extended optimum decoding for LDPC codes based on exhaustive tree search algorithm

A maximum-likelihood decoding algorithm inspired by information set decoding is realised for LDPC codes or linear block codes with sparse parity-check matrices of moderate codeword lengths over the AWGN channel. The extension involves an exhaustive branch and bound tree-search based algorithm for finding all small Euclidean distance error vectors. It provides an approach of searching on the bounded n-bit positions, which involves 2^k combinatorial dual codes based on the corresponding parity-check matrix, to achieve the near-optimum decoding output with attainable computational complexity. Soft decision decoding results are presented for some well-known LDPC codes demonstrating near-optimum maximum-likelihood performance.