Patent ID: 8407550

Claim:
A method for decoding a code using message-passing, wherein the code is represented by a factor graph, wherein the factor graph includes variable nodes indexed by i and constraint nodes indexed by a, wherein the variable nodes and the constraint nodes are connected by edges for transferring messages m i→a outgoing from the variable nodes to the consraint nodes and messages m a→i incoming from the constraint nodes to the variable nodes, and wherein the messages m i→a are initialized using beliefs b i of the set of variables nodes based on a received set of symbols y, and a processor for iteratively performing steps of the method, comprising the steps of: generating the messages m a→i by overshooting the messages m i→a at the constraint nodes; updating the beliefs b i at the variable nodes using the messages m a→i ; determining if codeword has been found; outputting the codeword if true; and otherwise updating the messages m i→a using correction for the overshooting if false, wherein the decoding is performed in a divide and concur belief propagation (DCBP) decoder.