Syndrome layered decoding for LDPC codes

• US 9,136,877 B1
• Filed: 08/20/2013
• Issued: 09/15/2015
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Enterprise IP LLC (Western Digital Corporation)
• Inventors: Chen, Xiaoheng, Zhu, Jiangli, Tai, Ying Yu
• Primary Examiner(s): NGUYEN, STEVE N
• Application Number:
  US13/971,774
• Time in Patent Office: 756 Days
• US Class Current: 1/1
• CPC Class Codes: H03M 13/1117 using approximations for check node processing, e.g. an outgoing message is depending on the signs and the minimum over the magnitudes of all incoming messages according to the min-sum rule
• CPC Class Codes: H03M 13/1134 Full parallel processing, i.e. all bit nodes or check nodes are processed in parallel
• CPC Class Codes: H03M 13/1137 Partly parallel processing, i.e. sub-blocks or sub-groups of nodes being processed in parallel
• CPC Class Codes: H03M 13/2909 Product codes
• CPC Class Codes: H04L 1/0045 Arrangements at the receiver end

Abstract

The various implementations described herein include systems, methods and/or devices for enhancing the performance of error control decoding. The method includes receiving at an LDPC decoder data from a storage medium corresponding to N variable nodes. The method further includes: updating a subset of the N variable nodes; updating all check nodes logically coupled to the updated subset of the N variable nodes; and generating check node output data for each updated check node including at least an updated syndrome check. Finally, the method includes: stopping decoding of the read data in accordance with a determination that the syndrome checks for all the M check nodes are valid syndrome checks or initiating performance of the set of operations with respect to a next subset of the N variable nodes in accordance with a determination that the syndrome checks for all the M check nodes include one invalid syndrome check.

Claims

1. An LDPC error control decoding system, comprising:

a set of parallel variable node processing units (VNUs) for updating N variable nodes, wherein N is an integer;

a port for receiving read data from a storage medium, the read data corresponding to the N variable nodes;

a set of parallel check node processing units (CNUs) for updating M check nodes, wherein M is an integer, each check node having a respective syndrome check;

wherein each of the N variable nodes is logically coupled with a corresponding subset of the M check nodes, and each of the M check nodes is logically coupled with a corresponding subset of the N variable nodes;

control logic coupled with the set of parallel VNUs and the set of parallel CNUs, configured to perform a set of operations, including;

enabling one or more VNUs of the set of parallel VNUs to update a subset of the N variable nodes, so as to generate for each updated variable node a respective new hard decision bit and an α

_nm message;

enabling one or more CNUs of the set of parallel CNUs to update all check nodes of the M check nodes logically coupled with the updated subset of the N variable nodes, in accordance with the new hard decision bits and α

_nm messages generated for the updated subset of the N variable nodes, so as to generate, for each of the updated check nodes, updated check node output data including at least an updated syndrome check, wherein generating the updated syndrome check for a respective check node of the M check nodes comprises identifying variable nodes for which the received new hard decision bit is different from a corresponding previously stored hard decision bit, counting the identified variable nodes, and inverting a previous syndrome check for the respective check node in accordance with a determination that the count is an odd number;

determining whether the syndrome checks for all the M check nodes are valid syndrome checks;

in accordance with a determination that the syndrome checks for all the M check nodes are valid syndromes, stopping decoding the read data; and

in accordance with a determination that the syndrome checks for all the M check nodes include at least one invalid syndrome check, initiating performance of the set of operations with respect to a next subset of the N variable nodes.

2. The LDPC error control decoding system of claim 1, wherein the updated check node output data comprises an updated syndrome check and an updated β

_mn message.

3. The LDPC error control decoding system of claim 1, wherein each CNU is configured to perform processing for a respective check node of the M check nodes, including:

receiving, for each variable node of the corresponding subset of the N variable nodes, the α

_nm message and the new hard decision bit;

generating the updated syndrome check; and

generating an updated β

_mn message based on the received α

_nm messages.

4. The LDPC error control decoding system of claim 3, wherein each CNU is configured to forgo generating the updated β

_mn message when the syndrome checks for all the M check nodes are valid syndrome checks.

5. The LDPC error control decoding system of claim 1, wherein the updated β

_mn message is generated using a min-sum algorithm.

6. The LDPC error control decoding system of claim 1, wherein N is defined by the number of columns in a parity-check matrix H, and M is defined by the number of rows in the parity-check matrix H.

7. The LDPC error control decoding system of claim 6, wherein one or more VNUs of the set of parallel VNUs are enabled to update a subset of the N variables nodes corresponding to a group of columns in the parity-check matrix H in accordance with a column-based decoding schedule.

8. The LDPC error control decoding system of claim 1, further comprising:

a first converter to convert at least one 2'"'"'s complement value generated by a respective VNU to a signed-magnitude value for use by a respective CNU; and

a second converter to convert at least one signed-magnitude value generated by a respective CNU to a 2'"'"'s complement value for use by a respective VNU.

9. An LDPC error control decoding system, comprising:

a set of parallel variable node processing units (VNUs) for updating N variable nodes, wherein N is an integer;

a port for receiving read data from a storage medium, the read data corresponding to the N variable nodes;

a set of parallel check node processing units (CNUs) for updating M check nodes, wherein M is an integer, each check node having a respective syndrome check;

wherein each of the N variable nodes is logically coupled with a corresponding subset of the M check nodes, and each of the M check nodes is logically coupled with a corresponding subset of the N variable nodes;

control logic coupled with the set of parallel VNUs and the set of parallel CNUs, configured to perform a set of operations, including;

enabling one or more VNUs of the set of parallel VNUs to update a subset of the N variable nodes, so as to generate for each updated variable node a respective new hard decision bit and an α

_nm message;

enabling one or more CNUs of the set of parallel CNUs to update all check nodes of the M check nodes logically coupled with the updated subset of the N variable nodes, in accordance with the new hard decision bits and α

_nm messages generated for the updated subset of the N variable nodes, so as to generate, for each of the updated check nodes, updated check node output data including at least an updated syndrome check wherein generating the updated check node output data including at least an updated syndrome check, wherein generating the updated syndrome check for a respective check node of the M check nodes comprises identifying each respective variable node for which the received new hard decision bit is different from a corresponding previously stored hard decision bit, and performing an XOR of a previously stored syndrome, with only the new hard decision bit for the each identified respective variable node of the corresponding subset of the N variable nodes, and a corresponding previously stored hard decision bit for each identified respective variable node of the corresponding subset of the N variable nodes;

determining whether the syndrome checks for all the M check nodes are valid syndrome checks;

in accordance with a determination that the syndrome checks for all the M check nodes are valid syndromes, stopping decoding the read data; and

in accordance with a determination that the syndrome checks for all the M check nodes include at least one invalid syndrome check, initiating performance of the set of operations with respect to a next subset of the N variable nodes.

10. A method of LDPC error control decoding, the method comprising:

at an LDPC decoder with a set of parallel variable node processing units (VNUs) for updating N variable nodes, wherein N is an integer, a port coupled to a storage medium, a set of parallel check node processing units (CNUs) for updating M check nodes, wherein M is an integer, each check node having a respective syndrome check, and control logic coupled with the set of parallel VNUs and the set of parallel CNUs;

receiving read data from the storage medium at the port, the read data corresponding to the N variable nodes, wherein each of the N variable nodes is logically coupled with a corresponding subset of the M check nodes, and each of the M check nodes is logically coupled with a corresponding subset of the N variable nodes;

updating via one or more VNUs of the set of parallel VNUs a subset of the N variable nodes, so as to generate for each updated variable node a respective new hard decision bit and a α

_nm message;

in accordance with the new hard decision bits and α

_nm messages generated for the updated subset of the N variable nodes, updating via one or more CNUs of the set of parallel CNUs all check nodes of the M check nodes logically coupled with the updated subset of the N variable nodes, so as to generate, for each of the updated check nodes, updated check node output data including at least an updated syndrome check, wherein generating the updated syndrome check for a respective check node of the M check nodes comprises identifying variable nodes for which the received new hard decision bit is different from a corresponding previously stored hard decision bit, counting the identified variable nodes, and inverting previous syndrome check for the respective check node in accordance with a determination that the count is an odd number;

determining whether the syndrome checks for all the M check nodes are valid syndrome checks;

in accordance with a determination that the syndrome checks for all the M check nodes are valid syndrome checks, stopping decoding the read data; and

in accordance with a determination that the syndrome checks for all the M check nodes include at least one invalid syndrome check, initiating performance of the set of operations with respect to a next subset of the N variable nodes.

11. The method of claim 10, wherein the updated check node output data comprises an updated syndrome check and an updated β

_mn message.

12. The method of claim 10, wherein each CNU is configured to perform processing for a respective check node of the M check nodes, including:

receiving, for each variable node of the corresponding subset of the N variable nodes, the α

_nm message and the new hard decision bit;

generating the updated syndrome check; and

generating an updated β

_mn message based on the received α

_nm messages.

13. The method of claim 12, wherein each CNU is configured to forgo generating the updated β

_mn message when the syndrome checks for all the M check nodes are valid syndrome checks.

14. The method of claim 10, wherein the updated β

_mn message is generated using a min-sum algorithm.

15. The method of claim 10, wherein N is defined by the number of columns in a parity-check matrix H, and M is defined by the number of rows in the parity-check matrix H.

16. The method of claim 15, wherein updating via one or more VNUs of the set of parallel VNUs a subset of the N variables nodes includes updating via one or more VNUs of the set of parallel VNUs a subset of the N variables nodes corresponding to a group of columns in the parity-check matrix H in accordance with a column-based decoding schedule.

17. The method of claim 10, further comprising:

converting via a first converter at least one 2'"'"'s complement value generated by a respective VNU to a signed-magnitude value for use by a respective CNU; and

converting via a second converter at least one signed-magnitude value generated by a respective CNU to a 2'"'"'s complement value for use by a respective VNU.

18. A method of LDPC error control decoding, the method comprising:

at an LDPC decoder with a set of parallel variable node processing units (VNUs) for updating N variable nodes, wherein N is an integer, a port coupled to a storage medium, a set of parallel check node processing units (CNUs) for updating M check nodes, wherein M is an integer, each check node having a respective syndrome check, and control logic coupled with the set of parallel VNUs and the set of parallel CNUs;

receiving read data from the storage medium at the port, the read data corresponding to the N variable nodes, wherein each of the N variable nodes is logically coupled with a corresponding subset of the M check nodes, and each of the M check nodes is logically coupled with a corresponding subset of the N variable nodes;

updating via one or more VNUs of the set of parallel VNUs a subset of the N variable nodes, so as to generate for each updated variable node a respective new hard decision bit and a α

_nm message;

in accordance with the new hard decision bits and α

_nm messages generated for the updated subset of the N variable nodes, updating via one or more CNUs of the set of parallel CNUs all check nodes of the M check nodes logically coupled with the updated subset of the N variable nodes, so as to generate, for each of the updated check nodes, updated check node output data including at least an updated syndrome check, wherein generating the updated syndrome check for a respective check node of the M check nodes comprises identifying each respective variable node for which the received new hard decision bit is different from a corresponding previously stored hard decision bit, and performing an XOR of a previously stored syndrome, with only the new hard decision bit for each identified respective variable node of the corresponding subset of the N variable nodes, and a corresponding previously stored hard decision bit for each identified respective variable node of the corresponding subset of the N variable nodes;

determining whether the syndrome checks for all the M check nodes are valid syndrome checks;

in accordance with a determination that the syndrome checks for all the M check nodes are valid syndrome checks, stopping decoding the read data; and

in accordance with a determination that the syndrome checks for all the M check nodes include at least one invalid syndrome check, initiating performance of the set of operations with respect to a next subset of the N variable nodes.