Accelerating LDPC decoding using multiple-cycle eigenmessages

The eigenmessage decoder O. Chauhan et al. (2003) expresses a degree of nonlocality in a message passing decoder by representing an entire cycle in a single linear equation. The eigenvector for the linear message passing matrix represents a fixed point of the message passing algorithm around a cycle and has been shown to significantly decrease the number of iterations required for low-density parity-check (LDPC) decoding using message passing. In this paper, we extend the eigenmessage idea to simultaneously solving for a fixed point of multiple cycles. The representation is thus nonlocal over a broader section of the graph. This multiple-cycle eigenmessage algorithm shows improvement over traditional belief propagation (BP) methods. We present and compare results for the new algorithm and consider possible variations.