Compensation methods for cycles in message passing decoders

It is well established that cycles in the Tanner graphs associated with error correction codes introduces biases into message passing decoding and result in poor performance as the number of cycles in the graph increases. The decoder in this paper addresses the problem of cycles by two methods: (1) Computing exact probabilities by marginalizing the exact probability obtained using clique potential functions and Clifford-Hammersley theorem, followed by pushing these probabilities as messages on adjacent to the graph; and (2) finding a set of random embedded subgraphs as minimal spanning trees, then passing messages along these. Modest probability of error improvements are obtained on very short codes.