Divide & Concur and Difference-Map BP Decoders for LDPC Codes

Date Added: Jan 2011
Format: PDF

The "Divide and Concur" (DC) algorithm, recently introduced by Gravel and Elser, can be considered a competitor to the Belief Propagation (BP) algorithm, in that both algorithms can be applied to a wide variety of constraint satisfaction, optimization, and probabilistic inference problems. The authors show that DC can be interpreted as a message-passing algorithm on a constraint graph, which helps make the comparison with BP clearer. The "Difference-map" dynamics of the DC algorithm enables it to avoid "Traps" which may be related to the "Trapping sets" or "Pseudo-codewords" that plague BP decoders of Low-Density Parity Check (LDPC) codes in the error-floor regime.