On-the-fly evaluation of the number of errors corrected in iterative ECC decoding

Patent metadata

Field	Value
Publication number	US-9853661-B2
Application number	US-201514961913-A
Country	US
Kind code	B2
Filing date	Dec 8, 2015
Priority date	Dec 8, 2015
Publication date	Dec 26, 2017
Grant date	Dec 26, 2017

Abstract

A decoder includes an interface and circuitry. The interface is configured to receive a code word that was encoded using a Quasi-Cyclic Low Density Parity Check (QC-LDPC) Error Correcting Code (ECC) represented by multiple check equations that are defined over multiple variables. The circuitry is configured to decode the code word by iteratively processing multiple layers that each includes a respective subset of the variables of the code word, and producing per each layer one or more count updates, and to generate a total number of errors corrected over the entire code word by accumulating the count updates.

First claim

The invention claimed is:

1. A storage system, comprising:
a memory, configured to store a code word that was encoded using a Quasi-Cyclic (QC) Low Density Parity Check (QC-LDPC) Error Correcting Code (ECC) represented by multiple check equations that are defined over multiple variables; and
a hardware-implemented decoder, configured to:
receive the code word that was read from the memory, wherein the code word contains one or more errors caused by impairments in the memory;
decode the code word by iteratively processing multiple layers that each comprises a respective subset of the variables of the code word, and producing, per each layer, one or more count updates;
generate a total number of errors corrected over the entire code word by accumulating the count updates; and
output at least one of the decoded code word and the total number of errors corrected.

2. The storage system according to claim 1 , wherein the decoder is configured to process each of the layers by processing the variables of the layer with respect to one or more equation groups that each comprises one or more of the check equations defining the QC-LDPC ECC, and to produce the count updates for the respective equation groups.

3. The storage system according to claim 1 , wherein the decoder is configured to:
produce a first count comprising a number of differences between values of the variables in the subset and respective values in the received code word;
produce a second count comprising the number of differences between values of the variables in the subset, derived in a previous processing instance of the layer, and the respective values in the received code word; and
derive the count updates by subtracting the second count from the first count.

4. The storage system according to claim 3 , wherein the decoder is configured to:
store the first count; and
produce the second count in a subsequent processing instance of the layer by extracting the stored first count.

5. The storage system according to claim 4 , wherein the decoder is configured to store the first count in a register that stores values up to a maximal number that is smaller than a number of the variables in the subset.

6. The storage system according to claim 3 , wherein the decoder is configured to produce the second count by storing the values of the variables of the subset in the previous processing instance of the layer, and counting the number of differences between the stored values and the respective values of the variables of the code word.

7. The storage system according to claim 1 , wherein the decoder is configured to accumulate the count updates by accumulating a given count update that was produced in processing the respective layer.

8. A method for data storage, comprising:
in a storage system comprising a memory and a hardware-implemented decoder coupled to the memory, reading from the memory a code word that was encoded using a Quasi-Cyclic Low Density Parity Check (QC-LDPC) Error Correcting Code (ECC) represented by multiple check equations that are defined over multiple variables, wherein the code word contains one or more errors caused by impairments in the memory;
decoding the code word, by the decoder, by iteratively processing multiple layers that each comprises a respective subset of the variables of the code word, and producing, per each layer, one or more count updates;
generating a total number of errors corrected over the entire code word by accumulating the count updates; and
outputting, by the decoder, at least one of the decoded code word and the total number of errors corrected.

9. The method according to claim 8 , wherein processing the multiple layers comprises processing the variables of each of the layers with respect to one or more equation groups that each comprises one or more of the check equations defining the QC-LDPC ECC, and wherein producing the count updates comprises producing the count updates for the respective equation groups.

10. The method according to claim 8 , wherein producing the count updates comprises producing a first count comprising a number of differences between values of the variables in the subset and respective values in the received code word, further producing a second count comprising the number of differences between values of the variables in the subset, derived in a previous processing instance of the layer, and the respective values in the received code word, and deriving the count updates by subtracting the second count from the first count.

11. The method according to claim 10 , wherein producing the count updates comprises storing the first count, and producing the second count in a subsequent processing instance of the layer by extracting the stored first count.

12. The method according to claim 11 , wherein storing the first count comprises storing the first count in a register that stores values up to a maximal number that is smaller than a number of the variables in the subset.

13. The method according to claim 10 , wherein producing the count updates comprises producing the second count by storing the values of the variables of the subset in the previous processing instance of the layer, and counting the number of differences between the stored values and the respective values of the variables of the code word.

14. The method according to claim 8 , wherein accumulating the count updates comprises accumulating a given count update that was produced in processing the respective layer.

15. A receiver in a communication system, the receiver comprising:
an interface, configured to receive a code word that was encoded, in a transmitter of the communication system, using a Quasi-Cyclic (QC) Low Density Parity Check (QC-LDPC) Error Correcting Code (ECC) represented by multiple check equations that are defined over multiple variables, wherein the code word contains one or more errors caused by a communication channel between the transmitter and the receiver; and
a hardware-implemented decoder, configured to:
decode the received code word by iteratively processing multiple layers that each comprises a respective subset of the variables of the code word, and producing, per each layer, one or more count updates;
generate a total number of errors corrected over the entire code word by accumulating the count updates; and
output at least one of the decoded code word and the total number of errors corrected.

16. A method for communication, comprising:
in a receiver of a communication system, receiving a code word that was encoded in a transmitter of the communication system, using a Quasi-Cyclic (QC) Low Density Parity Check (QC-LDPC) Error Correcting Code (ECC) represented by multiple check equations that are defined over multiple variables, wherein the code word contains one or more errors caused by a communication channel between the transmitter and the receiver;
decoding the received code word, by a hardware-implemented decoder of the receiver, by
iteratively processing multiple layers that each comprises a respective subset of the variables of the code word, and producing, per each layer, one or more count updates;
generating a total number of errors corrected over the entire code word by accumulating the count updates; and
outputting at least one of the decoded code word and the total number of errors corrected.

Assignees

• Apple Inc

Inventors

• Tate Yonathan
• Landau Asaf
• Anholt Micha

Classifications

• H03M13/116 Primary

  Quasi-cyclic LDPC [QC-LDPC] codes, i.e. the parity-check matrix being composed of permutation or circulant sub-matrices · CPC title

• H03M13/1131 Primary

  Scheduling of bit node or check node processing · CPC title

• G06F11/0727

  in a storage system, e.g. in a DASD or network based storage system (drivers for digital recording or reproducing units G06F3/06; circuits for error detection or correction within digital recording or reproducing units G11B20/18; for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS], H04L67/1097) · CPC title

• G06F11/076

  by exceeding a count or rate limit, e.g. word- or bit count limit · CPC title

• H03M13/1128

  Judging correct decoding and iterative stopping criteria other than syndrome check and upper limit for decoding iterations · CPC title