Error correction code (ECC) decoders sharing logic operations, memory controllers including the error correction code decoders, and methods of decoding error correction codes

• US 10,243,588 B2
• Filed: 07/19/2017
• Issued: 03/26/2019
• Est. Priority Date: 01/11/2017
• Status: Active Grant

• Current Assignee: MIMIRIP LLC (Ideahub, Inc.)
• Original Assignee: SK Hynix Inc.
• Inventors: Kim, Soojin
• Primary Examiner(s): Tabone, Jr., John J
• Application Number:
  US15/653,730
• Publication Number:
  US 20180198468A1
• Time in Patent Office: 615 Days
• Field of Search: 714758, 714763, 714768, 714773, 714782, 714784, 714785, 714799, 365200, 365201, 36518509
• CPC Class Codes: G06F 11/1016 Error in accessing a memory location, i.e. addressing error
• CPC Class Codes: G06F 11/106 Correcting systematically all correctable errors, i.e. scrubbing
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G11C 11/409 Read-write [R-W] circuits
• CPC Class Codes: G11C 2029/0411 Online error correction
• CPC Class Codes: G11C 29/42 using error correcting codes [ECC] or parity check
• CPC Class Codes: G11C 29/816 for an application-specific layout
• CPC Class Codes: H03M 13/11 using multiple parity bits
• CPC Class Codes: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/152 Bose-Chaudhuri-Hocquenghem [BCH] codes
• CPC Class Codes: H03M 13/153 using the Berlekamp-Massey algorithm
• CPC Class Codes: H03M 13/158 Finite field arithmetic processing

Abstract

An error correction code (ECC) decoder includes a finite state machine (FSM) controller and a shared logic circuit. The FSM controller generates a first control signal and a second control signal each corresponding to a certain state. The shared logic circuit includes a plurality of shared Galois field (GF) multipliers, a plurality of shared XOR arithmetic elements, and a plurality of shared multiplexers (MUXs), which are used for an operation selected between a syndrome operation, an error location polynomial operation, an error location operation and an error correction operation, in response to the first and second control signals.

Claims

1. An error correction code (ECC) decoder comprising:

a finite state machine (FSM) controller configured to generate a first control signal and a second control signal each corresponding to a certain state of a plurality of states; and

a shared logic circuit configured to include a plurality of shared Galois field (GF) multipliers, a plurality of shared XOR arithmetic elements, and a plurality of shared multiplexers (MUXs), which are used for an operation selected between a syndrome operation, an error location polynomial operation, an error location operation, and an error correction operation, in response to the first and second control signals.

2. The ECC decoder of claim 1, wherein the FSM controller circularly operates based on the plurality of states including a first state defined as an initialized state, a second state defined as a syndrome operation state, a third state defined as an error location polynomial operation state, a fourth state defined as an error location operation state, and a fifth state defined as an error correction operation state.

3. The ECC decoder of claim 2, wherein the FSM controller generates the first and second control signals maintaining a current state or transitioning to a next state in response to an input control signal.

4. The ECC decoder of claim 2, wherein the FSM controller:

generates the first and second control signals during the first state so that the shared logic circuit maintains a standby state;

generates the first and second control signals during the second state so that the shared logic circuit performs the syndrome operation;

generates the first and second control signals during the third state so that the shared logic circuit performs the error location polynomial operation;

generates the first and second control signals during the fourth state so that the shared logic circuit performs the error location operation; and

generates the first and second control signals during the fifth state so that the shared logic circuit performs the error correction operation.

5. The ECC decoder of claim 1, wherein the shared GF multipliers and the shared XOR arithmetic elements are used to perform any one of the syndrome operation, the error location polynomial operation, and the error location operation, according to the first control signal.

6. The ECC decoder of claim 1, wherein the shared MUXs are used to perform any one operation of the error location polynomial operation and the error correction operation according to the second control signal.

7. The ECC decoder of claim 1, wherein each of the plurality of shared GF multipliers includes:

a first MUX including an input terminal receiving the first control signal from the FSM controller, a first state input terminal receiving first syndrome operation data to be used for the syndrome operation, a second state input terminal receiving first error location polynomial operation data to be used for the error location polynomial operation, a third state input terminal receiving first error location operation data to be used for the error location operation, and an output terminal;

a second MUX including an input terminal receiving the first control signal from the FSM controller, a first state input terminal receiving second syndrome operation data to be used for the syndrome operation, a second state input terminal receiving second error location polynomial operation data to be used for the error location polynomial operation, a third state input terminal receiving second error location operation data to be used for the error location operation, and an output terminal; and

a GF multiplier configured to perform a GF multiplying operation on output signals output through the output terminals of the first and second MUXs to output the result of the GF multiplying operation.

8. The ECC decoder of claim 7, wherein:

the first syndrome operation data is one of data bits included in a codeword;

the second syndrome operation data is one of GF primitive elements;

the first and second error location polynomial operation data are one of control signals and one of error location polynomial coefficients, respectively;

the first error location operation data is one of the error location polynomial coefficients; and

the second error location operation data is one of the GF primitive elements.

9. The ECC decoder of claim 1, wherein each of the plurality of shared XOR arithmetic elements includes:

a first MUX including an input terminal receiving the first control signal from the FSM controller, a first state input terminal receiving third syndrome operation data to be used for the syndrome operation, a second state input terminal receiving third error location polynomial operation data to be used for the error location polynomial operation, a third state input terminal receiving third error location operation data to be used for the error location operation, and an output terminal;

a second MUX including an input terminal receiving the first control signal from the FSM controller, a first state input terminal receiving fourth syndrome operation data to be used for the syndrome operation, a second state input terminal receiving fourth error location polynomial operation data to be used for the error location polynomial operation, a third state input terminal receiving fourth error location operation data to be used for the error location operation, and an output terminal; and

an XOR arithmetic element configured to perform an XOR operation on output signals output through the output terminals of the first and second MUXs to output the result of the XOR operation.

10. The ECC decoder of claim 9, wherein:

the third and fourth syndrome operation data are output signals of first and second shared GF multipliers, respectively, used in the syndrome operation, among the plurality of shared GF multipliers;

the third and fourth error location polynomial operation data are output signals of first and second shared GF multipliers, respectively, used in the error location polynomial operation, among the plurality of shared GF multipliers;

the third error location operation data is one of error location polynomial coefficients; and

the fourth error location operation data is one of output signals of the shared GF multipliers used in the error location operation, among the plurality of shared GF multipliers.

11. The ECC decoder of claim 1, wherein the shared logic circuit receives a codeword, and wherein if the number of bits included in the codeword is “

n” and

the maximum number of error correctable bits is “

t,”

the number of the shared GF multipliers is “

2t×

(n−

1),”

the number of the shared XOR arithmetic elements is “

2t×

(n−

1),” and

the number of the shared MUXs is “

n”

.

12. The ECC decoder of claim 11, wherein:

all of the “

2t×

(n−

1)”

shared GF multipliers and all of the “

2t×

(n−

1)”

shared XOR arithmetic elements are used in the syndrome operation;

“

2×

(3t+1)”

shared GF multipliers among the “

2t×

(n−

1)”

shared GF multipliers, “

3t+1”

shared XOR arithmetic elements among the “

2t×

(n−

1)”

shared XOR arithmetic elements, and three shared MUXs among the “

n”

shared MUXs are used in the error location polynomial operation;

“

t×

(n−

1)”

shared GF multipliers among the “

2t×

(n−

1)”

shared GF multipliers and “

t×

n”

shared XOR arithmetic elements among the “

2t×

(n−

1)”

shared XOR arithmetic elements are used in the error location operation; and

all of the “

n”

shared MUXs are used in the error correction operation.

13. A method of decoding error correction codes, the method comprising:

providing a shared logic circuit including a plurality of shared Galois field (GF) multipliers, a plurality of shared XOR arithmetic elements, and a plurality of shared multiplexers (MUXs);

providing a finite state machine (FSM) controller generating a first control signal and a second control signal each corresponding to a certain state of a plurality of states; and

driving the shared logic circuit including the plurality of shared GF multipliers, the plurality of shared XOR arithmetic elements and the plurality of shared MUXs to perform an operation selected between a syndrome operation, an error location polynomial operation, an error location operation, and an error correction operation, in response to the first and second control signals.

14. The method of claim 13, wherein the FSM controller circularly operates based on the plurality of states including a first state defined as an initialized state, a second state defined as a syndrome operation state, a third state defined as an error location polynomial operation state, a fourth state defined as an error location operation state, and a fifth state defined as an error correction operation state.

15. The method of claim 14, wherein the FSM controller generates the first and second control signals maintaining a current state or transitioning to a next state in response to an input control signal.

16. The method of claim 14, wherein the FSM controller:

generates the first and second control signals during the first state so that the shared logic circuit maintains a standby state;

generates the first and second control signals during the second state so that the shared logic circuit performs the syndrome operation;

generates the first and second control signals during the third state so that the shared logic circuit performs the error location polynomial operation;

generates the first and second control signals during the fourth state so that the shared logic circuit performs the error location operation; and

generates the first and second control signals during the fifth state so that the shared logic circuit performs the error correction operation.

17. The method of claim 13, wherein the shared GF multipliers and the shared XOR arithmetic elements are used to perform any one of the syndrome operation, the error location polynomial operation, and the error location operation, according to the first control signal.

18. The method of claim 13, wherein the shared MUXs are used to perform any one operation of the error location polynomial operation and the error correction operation according to the second control signal.