An iterative probabilistic decoding algorithm for binary linear block codes beyond the half minimum distance

Abstract

An algorithm for decoding of linear binary block codes based on the iterative probabilistic error-correction is considered theoretically and experimentally. Assuming the sparse code parity-check matrix it is demonstrated that, with probability close to one, the algorithm works far beyond the half minimum distance with complexity linearly proportional to the codeword length and the average number of per bit employed parity-checks.