Patent ID: 8429512

Claim:
A method of decoding a manifestation of a codeword in which K information bits are encoded as N>K codeword bits, the method comprising: (a) updating estimates of the codeword bits by steps including: in a graph that includes N bit nodes and N−K check nodes, exchanging messages between the bit nodes and the check nodes during at least one message exchange iteration; (b)defining a full message length greater than two bits with which individual messages, transmitted between the bit nodes and check nodes, are expressed during computation; and (c) in each iteration, storing representations of at least a portion of the messages that are exchanged between the bit nodes and the check nodes; wherein, for at least one of the bit nodes or check nodes, if representations of the messages that are sent from the bit nodes or check nodes during one of the at least one iteration are stored, then the representation of at least one of the messages is stored using at least two bits but using fewer bits than the full message length.