Patent ID: 8261170

Claim:
A multi-stage decoder for decoding a block of symbols, received via a noisy channel, to a codeword of an error-correcting code, comprising: a plurality of sub-decoders connected sequentially, and wherein a next sub-decoder has a slower processing time and a betterword error rate than a previous sub-decoder, and wherein the next sub-decoder is only executed if the previous decoder fails to decode the block sequence of symbols, and a last sub-decoder is executed until a termination condition is reached, wherein any sub-decoders that use an iterative decoding method use an active set iterative decoding method, and wherein the channel is a binary symmetric channel, and wherein the active set decoder further comprises: an iterative belief propagation decoder, comprising: a set of check nodes; a set of variables nodes; and means for passing messages between the set of check nodes and the set of variable nodes, and wherein a set of outgoing messages from the check nodes is only updated if a set of incoming messages to the check node change, and the set of outgoing messages from a variables node is only updated if the incoming messages to the variable node change.