Back to results
US 8,359,522 B2Granted
Low density parity check decoder for regular LDPC codes
AssigneeThe Texas A&M University System
InventorsKiran K. Gunnam, Gwan S. Choi
Life of this patent
Estimating the term…
Abstract
A method and system for decoding low density parity check (“LDPC”) codes. An LDPC decoder includes an R select unit, a Q message first-in first-out (“FIFO”) memory, and a cyclic shifter. The R select unit provides an R message by selecting from a plurality of possible R message values. The Q message memory stores a Q message until an R message is generated by a CNU, the Q message and the R message are combined to provide a P message. The cyclic shifter shifts the P message.
Claims98
A low density parity check code decoder, comprising:
- a check node unit (“CNU”);
- the CNU comprising:
- a set of comparators for comparing stored minimum values to a received variable message Q, wherein:
- a total number of comparators in the set is less than the check node degree;
- a first comparator of the set determines a first minimum value, M1, by comparing a first stored minimum value, M1PS, and the received variable message Q;
- and
- a second comparator of the set determines a second minimum value, M2, by comparing a second stored minimum value, M2PS, and the received variable message Q;
- and
- final state storage that stores:
- a modified version of M1PS,
- a modified version of a two's complement of M1PS, and
- one of a modified version of M2PS and a modified version of a two's complement of M2PS;
- a selector that selects, from the final state storage, a message to a variable node unit to be one of:
- the modified version of M1PS,
- the modified version of the two's complement of M1PS, and
- the one of the modified version of M2PS and the modified version of the two's complement of M2PS;
- wherein the modified version of either of M1PS and M2PS is one of an offset corrected version and a scaled version.
14 more elements
A method for decoding a low density parity check code, comprising:
- comparing a received variable message to a first stored minimum value to determine a new first minimum value;
- comparing the received variable message to a second stored minimum value to determine new second minimum value;
- determining indicia of the location of the new first minimum value;
- storing the new first minimum value, the new second minimum value and the indicia of the new first minimum value location in a partial state storage array;
- storing final minimum values in a final state storage array of a check node unit, the final minimum values comprising modified versions of:
- the first minimum value read from the partial state storage array,
- a two's complement of the first minimum value read from the partial state storage array, and
- one of the second minimum value read from the partial state storage array and a two's complement of the second minimum value read from the partial state storage array;
- and
- selecting, by the check node unit, one of the final minimum values stored in the final state storage array to be a check node message;
- providing the check node message to a variable node;
- wherein the modified versions of the first minimum value and the second minimum value are one of offset corrected versions and scaled versions.
9 more elements
A low density parity check (“LDPC”) code decoder, comprising:
- a plurality of check node unit (“CNU”) arrays, each array comprising a plurality of CNUs and each array processing a block row of an LDPC parity check matrix;
- wherein the CNUs of each array are interconnected to perform a cyclic shift characteristic of the block row processed by the array;
- wherein routing of messages between CNUs and between CNUs and variable node units (VNUs) is accomplished by passive wired interconnection, rather than by active routers.
A method for low density parity check (“LDPC”) code decoding, comprising:
- applying a log-likelihood ratio (“LLR”) as an initial variable message to a check node unit (“CNU”) array;
- processing a layer of an LDPC parity check matrix in an array of CNUs, the CNUs of the array interconnected, without active routers, to provide incremental shifts in accordance with the number of incremental shifts characteristic of the blocks of the layer.
A low density parity check (“LDPC”) code decoder, comprising:
- an R select unit that provides an R message by selecting from a plurality of possible R message values;
- a Q message first-in first-out (“FIFO”) memory that stores a Q message until an R message is generated by a check node unit (“CNU”), the Q message and the R message are combined to provide a P message;
- and
- a cyclic shifter that shifts the P message;
- wherein the cyclic shifter shifts the P message by the difference of the shifts of a block currently being processed and the shifts of a block previously processed;
- wherein the block currently being processed and the block previously processed are in a same block column.
3 more elements
A method for decoding a low density parity check code, comprising:
- selecting an R old message from a plurality of possible R old messages based on a message index value and a sign bit;
- delaying a Q message in a FIFO memory until a check node unit (“CNU”) provides an R new message;
- summing the R new message and the delayed Q message to produce a P message;
- and
- cyclically shifting the P message by the difference of the shifts of a block currently being processed and the shifts of a block previously processed;
- wherein the block currently being processed and the block previously processed are in a same block column.
3 more elements
A low density parity check (“LDPC”) code decoder, comprising:
- a first R select unit that provides an R message by selecting from a plurality of possible R message values,
- a Q message generator that combines the R message with a P message to produce a Q message;
- and
- a first cyclic shifter that shifts the P message;
- wherein the decoder is configured to update the P message based on determination of a final state for each block row.
2 more elements
A method for decoding a low density parity check code, comprising:
- selecting a first R message from a plurality of previously generated possible R messages based on at least a message index value and a sign bit;
- generating a Q message by combining the first R message with a P message;
- cyclically shifting the P message;
- and
- updating the P message responsive to determination of a final state for each block row.
2 more elements
A low density parity check code decoder, comprising:
- a check node unit (“CNU”);
- the CNU comprising:
- a set of comparators for comparing stored minimum values to a received variable message Q, wherein:
- a total number of comparators in the set is less than the check node degree;
- a first comparator of the set determines a first minimum value, M1, by comparing a first stored minimum value, M1PS, and the received variable message Q;
- and
- a second comparator of the set determines a second minimum value, M2, by comparing a second stored minimum value, M2PS, and the received variable message Q;
- and
- final state storage that stores:
- a modified version of M1PS, and
- a modified version of M2PS;
- a selector that selects, from the final state storage, magnitude of a message
- to a variable node unit to be one of:
- the modified version of M1PS, and
- the modified version of M2PS;
- wherein the modified version of either of M1PS and M2PS is one of an offset corrected version and a scaled version.
13 more elements
Dependencies are inferred from the claim text.