Combined linear programming/belief propagation decoder

For decoding of LDPC codes two types of algorithms are frequently discussed in the literature. One type is based on belief propagation (BP) the other is based on linear programming (LP). Especially for short LDPC codes it has been observed that BP decoding often performs better at low SNR ranges, whereas LP decoding performs better at high SNR levels. A combined linear programming and belief propagation decoder is presented, which significantly outperforms both a pure LP and a pure BP decoder throughout the whole SNR range.