Reduced complexity LDPC decoder

A memory controller comprising:

• (a) an encoder for encoding K information bits as a codeword of N>K codeword bits;
• and (b) a decoder including:
• (i) at least one decoder memory;
• and (ii) at least one processor for decoding a manifestation of the codeword by executing an algorithm for updating estimates of the codeword bits by steps including:
• (A) 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, individual messages, transmitted between the bit nodes and check nodes, being expressed during computation with a full message length greater than two bits, and (B) storing, in the at least one decoder memory, 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 nodes, if representations of the messages that are sent from the bit node or check node 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.

A receiver comprising:

• (a) a demodulator for demodulating a message received from a communication channel, thereby providing a manifestation of a codeword in which K information bits are encoded as N>K codeword bits;
• and (b) a decoder including:
• (i) at least one memory;
• and (ii) at least one processor for decoding the manifestation of the codeword by executing an algorithm for updating estimates of the codeword bits by steps including:
• (A) 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, individual messages, transmitted between the bit nodes and check nodes, being expressed during computation with a full message length greater than two bits, and (B) storing, in the at least one memory, 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 that node 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.

A communication system for transmitting and receiving a message, comprising:

• (a) a transmitter including:
• (i) an encoder for encoding K information bits of the message as a codeword of N>K codeword bits, and (ii) a modulator for transmitting the codeword via a communication channel as a modulated signal;
• and (b) a receiver including:
• (i) a demodulator for receiving the modulated signal from the communication channel and for demodulating the modulated signal, thereby providing a manifestation of the codeword, and (ii) a decoder including:
• (A) at least one memory;
• and (B) at least one processor for decoding the manifestation of the codeword by executing an algorithm for updating estimates of the codeword bits by steps including:
• (I) 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, individual messages, transmitted between the bit nodes and check nodes, being expressed during computation with a full message length greater than two bits, and (II) storing, in the at least one memory, 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 nodes, if representations of the messages that are sent from the bit node or check node 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.

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) providing a parity check matrix having N−K rows and N columns;
• (b) updating estimates of the codeword bits by steps including exchanging messages between the rows and the columns of the matrix during at least one message exchange iteration;
• (c) 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 (d) storing representations of at least a portion of the messages that are exchanged between the rows and the columns;
• wherein, for at least one of the rows or columns, if representations of the messages that are sent from that row or column 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.

A decoder for decoding a manifestation of a codeword in which K information bits are encoded as N>K codeword bits, comprising:

• (a) at least one memory;
• and (b) at least one processor for decoding the manifestation of the codeword by executing an algorithm for updating estimates of the codeword bits by steps including:
• (i) providing a parity check matrix having N−K rows and N columns;
• (ii) exchanging messages between the rows and the columns of the matirix during at least one message exchange iteration, individual messages, transmitted between the bit nodes and check nodes, being expressed with a full message length greater than two bits, and (iii) storing, in the at least one memory, representations of at least a portion of the messages that are exchanged between the rows and the columns, wherein, for at least one of the rows or columns, if representations of the messages that are sent from that row or column 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.

A memory controller comprising:

• (a) an encoder for encoding K information bits as a codeword of N>K codeword bits;
• and (b) a decoder including:
• (i) at least one memory;
• and (ii) at least one processor for decoding a manifestation of the codeword by executing an algorithm for updating estimates of the codeword bits by steps including:
• (A) providing a parity check matrix having N−K rows and N columns;
• exchanging messages between the rows and the columns of the matrix during at least one message exchange iteration, individual messages, transmitted between the bit nodes and check nodes, being expressed during computation with a full message length greater than two bits, and (C) storing, in the at least one memory, representations of at least a portion of the messages that are exchanged between the rows and the columns, wherein, for at least one of the rows or columns, if representations of the messages that are sent from that row or column 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.

A receiver comprising:

• (a) a demodulator for demodulating a message received from a communication channel, thereby providing a manifestation of a codeword in which K information bits are encoded as N>K codeword bits;
• and (b) a decoder including:
• (i) at least one memory;
• and (ii) at least one processor for decoding the manifestation of the codeword by executing an algorithm for updating estimates of the codeword bits by steps including:
• (A) providing a parity check matrix having N−K rows and N columns;
• (B) exchanging messages between the rows and the columns of the matrix during at least one message exchange iteration, individual messages, transmitted between the bit nodes and check nodes, being expressed during computation with a full message length greater than two bits, and (C) storing, in the at least one memory, representations of at least a portion of the messages that are exchanged between the rows and the columns, wherein, for at least one of the rows or columns, if representations of the messages that are sent from that row or column 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.

A communication system for transmitting and receiving a message, comprising:

• (a) a transmitter including:
• (i) an encoder for encoding K information bits of the message as a codeword of N>K codeword bits, and (ii) a modulator for transmitting the codeword via a communication channel as a modulated signal;
• and (b) a receiver including:
• (i) a demodulator for receiving the modulated signal from the communication channel and for demodulating the modulated signal, thereby providing a manifestation of the codeword, and (ii) a decoder including:
• (A) at least one memory;
• and B) at least one processor for decoding the manifestation of the codeword by executing an algorithm for updating estimates of the codeword bits by steps including:
• (I) providing a parity check matrix having N−K rows and N columns;
• (II) exchanging messages between the rows and the columns of the matrix during at least one message exchange iteration, individual messages, transmitted between the bit nodes and check nodes, being expressed during computation with a full message length greater than two bits, and (II) storing, in the at least one memory, representations of at least a portion of the messages that are exchanged between the rows and the columns, wherein, for at least one of the rows or columns, if representations of the messages that are sent from that row or column 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.