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

Patent metadata

Field	Value
Publication number	US-10243588-B2
Application number	US-201715653730-A
Country	US
Kind code	B2
Filing date	Jul 19, 2017
Priority date	Jan 11, 2017
Publication date	Mar 26, 2019
Grant date	Mar 26, 2019

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.

First claim

What is claimed is:

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

Assignees

• Sk Hynix Inc

Inventors

• Kim Soojin

Classifications

• H03M13/152

  Bose-Chaudhuri-Hocquenghem [BCH] codes · CPC title

• H03M13/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 title

• G11C29/816

  for an application-specific layout · CPC title

• G06F11/1016

  Error in accessing a memory location, i.e. addressing error · CPC title

• G06F11/1076

  Parity data used in redundant arrays of independent storages, e.g. in RAID systems · CPC title