Fast decoding of regular LDPC codes using greedy approximation algorithms

Greedy algorithms are proposed for fast decoding of linear block codes over a binary symmetric channel. They are motivated by matching pursuit schemes developed in compressive sensing. Theoretical guarantees are provided for regular LDPC codes. The algorithms are highly efficient, as they only require vector-matrix multiplications and mostly use binary arithmetic. Their complexity is completely determined and depends on the code´s block length and a sparsity parameter. The experimental results validate the performance of the proposed algorithms.