Bit-flipping decoder for G-LDPC codes with syndrome-decoding for component codes

• US 10,707,899 B2
• Filed: 03/09/2018
• Issued: 07/07/2020
• Est. Priority Date: 08/31/2017
• Status: Active Grant

• Current Assignee: SK Hynix Inc.
• Original Assignee: SK Hynix Inc.
• Inventors: Bhatia, Aman, Kumar, Naveen, Xiong, Chenrong, Zhang, Fan, Lu, Xuanxuan, Cai, Yu
• Primary Examiner(s): Kerveros, James C
• Application Number:
  US15/917,222
• Publication Number:
  US 20190068219A1
• Time in Patent Office: 851 Days
• Field of Search: 714785
• CPC Class Codes: G06F 11/1012 using codes or arrangements adapted for a specific type of error G06F11/1048 takes precedence
• CPC Class Codes: G11C 29/42 using error correcting codes [ECC] or parity check
• CPC Class Codes: H03M 13/1108 Hard decision decoding, e.g. bit flipping, modified or weighted bit flipping
• CPC Class Codes: H03M 13/1111 Soft-decision decoding, e.g. by means of message passing or belief propagation algorithms
• CPC Class Codes: H03M 13/1174 Parity-check or generator matrices built from sub-matrices representing known block codes such as, e.g. Hamming codes, e.g. generalized LDPC codes

Abstract

Techniques are described for performing a bit-flipping decoding scheme on a G-LDPC codeword. In an example, a decoding system uses two syndrome tables. The first syndrome table identifies a predefined syndrome for a component codeword that protects a bit of the G-LDPC codeword. This predefined syndrome is identified based on a location of the bit and is used to update a current syndrome of the component codeword. The second syndrome table identifies one or more bit error locations for the component codeword. The bit error locations are identified from the second syndrome table based on the current syndrome of the component codeword, as updated. In an example, the error locations are used to update a reliability of the bit if its location corresponds to one of the error locations. A bit flipping decision is made for the bit based on its reliability.

Claims

1. A generalized low density-parity check (G-LDPC) decoding method, comprising:

receiving, by a decoding system, a G-LDPC codeword that comprises a plurality of component codewords; and

decoding, by the decoding system, the G-LDPC codeword by at least;

identifying a component codeword that protects a bit of the G-LDPC codeword;

determining, from a first syndrome table, a predefined syndrome based on a location of the bit in at least one of the component codeword or the G-LDPC codeword, the first syndrome table associating the location with the predefined syndrome;

updating a current syndrome of the component codeword based on the predefined syndrome;

determining, from a second syndrome table, an error location based on the current syndrome, the second syndrome table associating one or more error locations with one or more syndromes; and

performing a bit-flipping operation on the bit in the component codeword based on a determination that the error location corresponds to the location of the bit.

2. The method of claim 1, further comprising:

initializing, by the decoding system, a decision bit of the G-LDPC codeword to the bit of the G-LDPC codeword;

initializing, by the decoding system, current syndromes of the plurality of component codewords to zero; and

updating, by the decoding system, the current syndromes by at least;

identifying a set of component codewords of the plurality of component codewords, wherein the set protects the bit of the G-LDPC codeword and comprises the component codeword and a second component codeword; and

for the second component codeword of the set;

identifying a second location of the bit of the G-LDPC codeword in the second component codeword, and

updating a current syndrome of the second component codeword based on a second predefined syndrome determined from the first syndrome table given the second location of the bit in the second component codeword.

3. The method of claim 2, wherein the current syndrome of the component codeword and the current syndrome of the second component codeword are updated based on the bit having a current value of “

1.”

4. The method of claim 1, further comprising:

updating, by the decoding system, a current reliability of the bit by at least adding a value to the current reliability based on the determination that the error location given the current syndrome of the component codeword corresponds to the location of the bit in the component codeword.

5. The method of claim 4, wherein updating the current reliability comprises:

identifying a second component codeword that protects the bit of the G-LDPC codeword;

determining a second error location from the second syndrome table based on a current syndrome of the second component codeword;

determining that the second error location corresponds to a location of the bit in the second component codeword; and

adding the value to the current reliability based on the determination that the second error location corresponds to the location of the bit in the second component codeword.

6. The method of claim 5, wherein updating the current reliability further comprises:

identifying a third component codeword that protects the bit of the G-LDPC codeword;

determining a third error location from the second syndrome table based on a current syndrome of the third component codeword;

determining that the third error location is different from a location of the bit in the third component codeword;

avoiding an addition of the value to the current reliability based on the determination that the third error location is different from the location of the bit in the third component codeword.

7. The method of claim 6, wherein the value added to the current reliability is one.

8. The method of claim 4, wherein the current reliability is updated at a decoding iteration, and further comprising:

comparing, by the decoding system, the current reliability at the decoding iteration to a threshold;

performing, by the decoding system, the bit-flipping operation based on the comparing.

9. The method of claim 8, further comprising:

updating, by the decoding system based on the bit being flipped and being protected by the component codeword, the current syndrome of the component codeword by performing an XOR operation on the current syndrome and the predefined syndrome determined for the component codeword from the first syndrome table;

identifying, by the decoding system, a second component codeword that protects the bit of the G-LDPC codeword;

determining, by the decoding system, a location of the bit in the second component codeword;

determining, by the decoding system for the second component codeword, a second predefined syndrome from the first syndrome table based on the location of the bit in the second component codeword; and

updating, by the decoding system based on the bit being flipped and being protected by the second component codeword, a second current syndrome of the second component codeword by performing the XOR operation on the second current syndrome and the second predefined syndrome determined for the second component codeword from the first syndrome table.

10. The method of claim 8, wherein the threshold changes based on a counter of the decoding iteration.

11. The method of claim 10, wherein the threshold decreases with an increase to the counter of the decoding iteration.

12. The method of claim 11, wherein the threshold is defined as a function of an error correction capability of the component codeword.

13. The method of claim 1, wherein the first syndrome table and the second syndrome table are stored as a single table in storage space of the decoding system.

14. A generalized low density-parity check (G-LDPC) decoding system comprising:

one or more processors; and

one or more memories communicatively coupled with the one or more processors and storing instructions that, upon execution by the one or more processors, configure the G-LDPC decoding system to at least;

receive a G-LDPC codeword that comprises a plurality of component codewords; and

decode the G-LDPC codeword by at least;

identifying a component codeword that protects a bit of the G-LDPC codeword;

determining, from a first syndrome table, a predefined syndrome based on a location of the bit in at least one of the component codeword or the G-LDPC codeword, the first syndrome table associating the location with the predefined syndrome;

updating a current syndrome of the component codeword based on the predefined syndrome;

determining, from a second syndrome table, an error location based on the current syndrome, the second syndrome table associating one or more error locations with one or more syndromes; and

performing a bit-flipping operation on the bit in the component codeword based on a determination that the error location corresponds to the location of the bit.

15. The G-LDPC decoding system of claim 14, wherein the first syndrome table is defined based on:

initializing a simulation component codeword to “

0;

” and

iteratively performing operations comprising;

setting a single bit of the simulation component codeword to “

1,”

wherein the single bit is at a location in the simulation component codeword;

computing a syndrome of the simulation component codeword with the single bit set to “

1;

” and

adding the syndrome to an entry of the first syndrome table, wherein the entry is associated with the location of the single bit in the simulation component codeword.

16. The G-LDPC decoding system of claim 14, wherein the second syndrome table is defined based on:

generating, for a simulation component codeword, possible combinations for values of bits of the simulation component codeword; and

for each possible combination, performing operations comprising;

inputting the possible combination to a bit-flipping decoder;

receiving, from the bit-flipping decoder, a set of error locations and a syndrome for the possible combination;

adding the one or more error locations to a first entry of the second syndrome table; and

adding the syndrome received for the possible combination to a second entry of the second syndrome table, wherein the first entry and the second entry are associated together.

17. One or more non-transitory computer storage media comprising instructions that, upon execution on a generalized low density-parity check (G-LDPC) decoding system, configure the G-LDPC decoding system to perform operations comprising:

receiving a G-LDPC codeword that comprises a plurality of component codewords; and

decoding the G-LDPC codeword by at least;

identifying a component codeword that protects a bit of the G-LDPC codeword;

determining, from a first syndrome table, a predefined syndrome based on a location of the bit in at least one of the component codeword or the G-LDPC codeword, the first syndrome table associating the location with the predefined syndrome;

updating a current syndrome of the component codeword based on the predefined syndrome;

determining, from a second syndrome table, an error location based on the current syndrome, the second syndrome table associating one or more error locations with one or more syndromes; and

performing a bit-flipping operation on the bit in the component codeword based on a determination that the error location corresponds to the location of the bit.

18. The one or more non-transitory computer storage media of claim 17, wherein the first syndrome table and the second syndrome table are generated by the G-LDPC decoding system after receiving the G-LDPC codeword.

19. The one or more non-transitory computer storage media of claim 17, wherein the first syndrome table and the second syndrome table are stored in a storage space of the G-LDPC decoding system prior to receiving the G-LDPC codeword, and wherein the first syndrome table and the second syndrome table are accessed by the G-LDPC decoding system from the storage space after receiving the G-LDPC codeword.

20. The one or more non-transitory computer storage media of claim 17, wherein the G-LDPC codeword comprises different types of component codewords, wherein the component codeword is of a first type of the different types, wherein the first syndrome table and the second syndrome table are defined for the first type, wherein a third syndrome table and a fourth syndrome table are defined for a second type of the different types, wherein the third syndrome table associates a syndrome with a bit location, and wherein the fourth syndrome table associates the syndrome with a corresponding error location.