Decoder for low-density parity-check codes
Methods and apparatus for decoding LDPC code provide that an LDPC code may be represented as a Tanner graph comprising bit nodes and check nodes and connections between them. A configurable LDPC decoder supporting many different LDPC codes having any sub-matrix size includes several independently addressable memories which are used to store soft decision data for each bit node. The decoder further includes a number P of check node processing systems which generate updated soft decision data. The updated values are then passed back to the memories via a shuffling system. If the number of check nodes processed in parallel by the check node processing systems is P CNB (where P≥P CNB ) and the soft decision data for a bit node is of word size q bits, the total width of the independently addressable memories is larger than P CNB *q bits.
1. A configurable LDPC decoder comprising:
one or more memories arranged collectively to store soft decision data for each bit node for use in decoding an LDPC code;
a plurality of check node processing systems arranged to operate in parallel and generate updates to the bit node soft decision data;
a first shuffling system arranged to pass data from the one or more memories to the plurality of check node processing systems; and
a second shuffling system arranged to pass updates to the bit node soft decision data from the plurality of check node processing systems to the one or more memories;
wherein each check node processing system generates updates to soft decision data for a bit node using check-to-bit node messages for each check node connected to the bit node.
2. The configurable LDPC decoder according to claim 1 , wherein each memory has a width, the width of a memory comprising an amount of data accessible from the memory in a single cycle.
3. The configurable LDPC decoder according to claim 1 , wherein each check-to-bit node message is calculated using a min-sum algorithm and a variable offset, wherein the variable offset is calculated based on differences between lowest-valued bit-to-check message magnitudes.
4. The configurable LDPC decoder according to claim 3 , wherein the variable offset is subtracted from an initial bit-to check node message calculated using the min-sum algorithm.
5. The configurable LDPC decoder according to claim 1 , wherein the decoder is arranged to support multiple different LDPC code structures having any sub-matrix size.
6. The configurable LDPC decoder according to claim 5 , wherein a parity check matrix for the LDPC code comprises a plurality of sub-matrices, a check node block comprises a group of check nodes processed in parallel by the check node processing systems and a sub-matrix comprises a plurality of check node blocks.
7. The configurable LDPC decoder according to claim 5 , wherein the one or more memories comprises a plurality of independently addressable memories.
8. A method of decoding an LDPC code comprising:
accessing soft decision data for a plurality of bit nodes from one or more memories;
providing the accessed soft decision data to a plurality of check node processing systems; and
generating updates to the soft decision data for the plurality of bit nodes in parallel in the check node processing systems; and
storing updated soft decision data for the plurality of bit nodes in the one or more memories;
wherein generating updates to the soft decision data for the plurality of bit nodes in parallel in the check node processing systems comprises, for each bit node:
calculating initial check-to-bit node messages for each check node connected to the bit node.
9. The method according to claim 8 , wherein the soft decision data is accessed in a single cycle.
10. The method according to claim 8 , wherein generating updates to the soft decision data for the plurality of bit nodes in parallel in the check node processing systems comprises, for each bit node:
calculating initial check-to-bit node messages for each check node connected to the bit node using a min-sum algorithm;
generating final check-to-bit node messages for each check node connected to the bit node using a variable offset, wherein the variable offset is calculated based on differences between lowest-valued bit-to-check node messages; and
calculating an update to the soft decision data based on the final check-to-bit node messages for each bit node connected to the check node.
11. The method according to claim 9 , wherein generating final check-to-bit node messages for each check node connected to the bit node using a variable offset comprises:
subtracting the variable offset from each initial check-to-bit node message to generate the final check-to-bit node messages for each check node connected to the bit node.
12. The method according to claim 8 , wherein the soft decision data for a plurality of bit nodes is accessed, in a single cycle, from a plurality of independently addressable memories.
13. A non-transitory computer readable storage medium having stored thereon computer readable program code that when processed in an integrated circuit manufacturing system causes the integrated circuit manufacturing system to generate a processor comprising an LDPC decoder, the LDPC decoder including:
one or more memories arranged collectively to store soft decision data for each bit node for use in decoding an LDPC code;
a plurality of check node processing systems arranged to operate in parallel and generate updates to the bit node soft decision data;
a first shuffling system arranged to pass data from the one or more memories to the plurality of check node processing systems; and
a second shuffling system arranged to pass updates to the bit node soft decision data from the plurality of check node processing systems to the one or more memories;
wherein each check node processing system generates updates to soft decision data for a bit node using check-to-bit node messages for each check node connected to the bit node.