System and method of decoding data with reduced power consumption

• US 8,301,987 B2
• Filed: 10/29/2009
• Issued: 10/30/2012
• Est. Priority Date: 10/29/2009
• Status: Active Grant

• Current Assignee: Western Digital Israel Limited (Western Digital Corporation)
• Original Assignee: SanDisk IL Ltd. (Western Digital Corporation)
• Inventors: Dror, Itai, Berger, Alexander
• Primary Examiner(s): Baderman, Scott
• Assistant Examiner(s): Kudirka, Joseph
• Application Number:
  US12/608,411
• Publication Number:
  US 20110107188A1
• Time in Patent Office: 1,097 Days
• Field of Search: 714/752, 714/773, 714/781, 714/782, 714/784, 714/785, 375/240.24, 713/300, 713/320
• US Class Current: 714/785
• CPC Class Codes: H03M 13/152 Bose-Chaudhuri-Hocquenghem [BCH] codes
• CPC Class Codes: H03M 13/1525 Determination and particular use of error location polynomials
• CPC Class Codes: H03M 13/153 using the Berlekamp-Massey algorithm
• CPC Class Codes: H03M 13/1545 Determination of error locations, e.g. Chien search or other methods or arrangements for the determination of the roots of the error locator polynomial
• CPC Class Codes: H03M 13/157 Polynomial evaluation, i.e. determination of a polynomial sum at a given value
• CPC Class Codes: H03M 13/159 Remainder calculation, e.g. for encoding and syndrome calculation
• CPC Class Codes: H03M 13/6502 Reduction of hardware complexity or efficient processing

Abstract

A decoder is disclosed that can reduce power consumption at different stages of a decoding process. At a first stage where the decoder calculates residual values, the decoder can reduce power consumption by calculating residual values using less than a full set of division circuits. A reduced number of division circuits may be sufficient to successfully calculate residuals associated with the codeword to complete the decoding process. Division circuits that are not used may be disabled to reduce power consumption. At another stage of the decoding process where the decoder generates coefficients that are used to identify locations of errors in the codeword, the decoding process can limit power consumption by reducing the number of iterations of a polynomial generator by incorporating termination decision circuitry.

Claims

1. A method of decoding data, the method comprising:

at a decoder configured to generate up to a first number of residual values to correct errors within data representing a corrupted codeword;

receiving the data representing the corrupted codeword;

before determining a syndrome associated with the received data., generating a first set of residual values, the first set of residual values having a second number of residual values corresponding to the received data, wherein the second number of residual values is less than the first number of residual values;

determining whether the received data representing the corrupted codeword is decodable using the first set of residual values; and

in response to determining that the received data is decodable using the first set of residual values, generating decoded data corresponding to the codeword.

2. The method of claim 1, further comprising:

in response to determining that the received data is not decodable using the first set of residual values, determining a second set of residual values corresponding to the received data, the second set of residual values comprising the first number of residual values.

3. The method of claim 1, wherein the decoder comprises residual calculation circuitry that includes a plurality of residual calculation circuits, and wherein at least one residual calculation circuit is selectively disabled during generation of the first set of residual values.

4. The method of claim 3, wherein the at least one residual calculation circuit is selectively disabled while another residual calculation circuit remains active.

5. The method of claim 4, further comprising selectively blocking a clock signal to the at least one residual calculation circuit.

6. The method of claim 1, further comprising:

determining a reduced number of errors to be correctable at the decoder, wherein the reduced number of errors is less than a first number of errors; and

determining the second number of residual values based on the reduced number of errors.

7. The method of claim 6, wherein the reduced number of errors is determined at least partially based on an estimated number of errors of the received data.

8. The method of claim 6, wherein the reduced number of errors is determined at least partially based on a failure threshold.

9. The method of claim 6, wherein the second number of residual values is determined based on an iterative convergence scheme that terminates in response to a degree of an error location polynomial equaling or exceeding the first number of errors.

10. The method of claim 6, wherein the second number of residual values is determined based on an iterative convergence scheme that terminates in response to a predetermined number of sequential discrepancy factors equaling zero during the iterative convergence scheme prior to a degree of an error location polynomial equaling the first number of errors.

11. The method of claim 10, wherein the received data is read from a flash memory array having a block error rate threshold, and wherein the predetermined number of sequential discrepancy factors is determined at least partially based on the block error rate threshold.

12. A data decoding device comprising:

an error correction code (ECC) engine configured to generate residual values to correct errors within a codeword that has been corrupted, wherein the ECC engine is adapted to generate a first number (p) of residual values to correct not more than a first number of errors (t) of the corrupted codeword when the corrupted codeword has a first codeword size (s), the ECC engine comprising;

a plurality of residual calculation circuits to generate a first set of residual values before a syndrome associated with the corrupted codeword is generated, the first set of residual values having a second number (r′

) of residual values, the second number (r′

) less than the first number (p);

a syndrome generator circuit coupled to receive the first set of residual values via an output of the plurality of residual calculation circuits; and

a control logic circuit configured to initiate generation of the first set of residual values, wherein an operation of at least one residual calculation circuit is disabled during generation of the first set of residual values.

13. The data decoding device of claim 12, wherein the control logic circuit is further configured to:

receive an indication of whether the corrupted codeword is decodable using the first set of residual values; and

in response to the indication indicating that the corrupted codeword is not decodable using the first set of residual values, initiate generation of a second set of residual values corresponding to received data representative of the corrupted codeword, the second set of residual values comprising the first number (p) of residual values.

14. The data decoding device of claim 13, wherein the ECC engine further comprises:

an error location polynomial generator coupled to receive an output of the syndrome generator circuit; and

an error location and correction circuit coupled to receive an output of the error location polynomial generator.

15. The data decoding device of claim 14, wherein the error location polynomial generator generates the indication of whether the received data is decodable using the first set of residual values.

16. The data decoding device of claim 14, wherein the error location polynomial generator is configured to generate data corresponding to an error location polynomial using an iterative convergence scheme that terminates in response to a predetermined number of sequential discrepancy factors equaling zero.

17. The data decoding device of claim 12, further comprising a circuit responsive to the control logic circuit to send a clock disable signal to the at least one residual calculation circuit.

18. A method comprising:

at a decoder including a plurality of residual calculation circuits, the plurality of residual calculation circuits comprising a first number (p) of residual calculation circuits, wherein a first number (t) of errors of a corrupted codeword is correctable using the first number (p) of residual calculation circuits;

selectively disabling an operation of at least one residual calculation circuit during generation of a first set of residual values corresponding to the corrupted codeword, the first set of residual values having a second number (r′

) of residual values that is less than the first number (p) of residual calculation circuits, the second number (r′

) of residual values determined to correct a second number (r) of errors within the corrupted codeword, wherein the second number (r) of errors is less than the first number (t) of errors; and

initiating generation of the first set of residual values corresponding to received data before a syndrome associated with the received data is calculated; and

generating the syndrome using the first set of residual values.

19. A method of decoding data, the method comprising:

at a decoder configured to correct a first number of errors within a codeword that has been corrupted;

receiving data representing the corrupted codeword;

before determining a syndrome associated with the received data, generating a first set of residual values, the first set of residual values having a second number of residual values corresponding to the received data, wherein the second number of residual values is less than a first number of residual values;

initiating an iterative convergence scheme to generate an error location polynomial, wherein each particular iteration of the iterative convergence scheme includes updating the error location polynomial and determining a discrepancy factor corresponding to the particular iteration; and

generating a count of sequential iterations of the iterative convergence scheme that correspond to a zero discrepancy factor and terminating the iterative convergence scheme in response to the count equaling a threshold, wherein the iterative convergence scheme is terminated prior to a degree of the error location polynomial equaling the first number of errors.

20. The method of claim 19, wherein the received data is read from a flash memory array.

21. The method of claim 20, wherein a block error rate threshold corresponds to the flash memory array, and wherein the threshold is determined at least partially based on the block error rate threshold.

22. The method of claim 21, wherein a probability that the iterative convergence scheme terminates prior to determining an actual convergence value of the error location polynomial is less than the block error rate threshold.

23. The method of claim 19, further comprising, during each iteration:

determining the discrepancy factor for the iteration;

incrementing a zeros counter in response to the discrepancy factor being zero;

resetting the zeros counter in response to the discrepancy factor being non-zero; and

comparing a value of the zeros counter to the threshold.

24. A data storage device comprising:

a flash memory;

a flash controller coupled to the flash memory; and

an error correction code (ECC) engine responsive to the flash controller and configured to generate residual values to correct errors within a codeword that has been corrupted, wherein the ECC engine is adapted to generate a first number (p) of residual values to correct not more than a first number of errors (t) of the corrupted codeword when the corrupted codeword has a first codeword size (s), the ECC engine comprising;

a plurality of residual calculation circuits to generate a first set of residual values before a syndrome associated with the corrupted codeword is generated, the first set of residual values having a second number (r′

) of residual values, the second number (r′

) less than the first number (p);

a syndrome generator circuit coupled to receive the first set of residual values via an output of the plurality of residual calculation circuits; and

a control logic circuit configured to initiate generation of the first set of residual values, wherein an operation of at least one residual calculation circuit is disabled during generation of the first set of residual values.