Error correction and decoding

Abstract

In an embodiment, an error detection and correction apparatus includes a positive edge triggered flip-flop that receives syndrome input based on a syndrome output a syndrome generator indicating whether or not input data includes an error, whereby the positive edge triggered flip-flop further provides a syndrome output to an error location decoder.

Claims

1. An error detection and correction apparatus, comprising: a syndrome generator configured to receive input data and to output a syndrome that indicates whether the input data includes an error; a positive edge triggered flip-flop that is configured to receive syndrome input based on the syndrome from the syndrome generator and to provide a syndrome output; and an error location decoder configured to receive the syndrome output from the positive edge triggered flip-flop.

2. The error detection and correction apparatus of claim 1, further comprising: a timing controller configured to receive a clock signal, and to delay the clock signal by a given amount of time by passing the clock signal through a delay line, wherein the positive edge triggered flip-flop is controlled by the delayed clock signal.

3. The error detection and correction apparatus of claim 2, wherein the given amount of time is configured to mimic a delay associated with a critical path of the syndrome generator.

4. The error detection and correction apparatus of claim 1, further comprising: an error detector configured to generate corrected output data, wherein the error location decoder is configured to provide, based on the syndrome output, both a single error location decoder output and a double error location decoder output to the error detector.

5. The error detection and correction apparatus of claim 4, wherein the syndrome input received at the positive edge triggered flip-flop corresponds to the syndrome that is output from the syndrome generator.

6. The error detection and correction apparatus of claim 1, wherein the error location decoder corresponds to a single error location decoder configured to provide, based on the syndrome output, a single error location decoder output.

7. The error detection and correction apparatus of claim 6, further comprising: a control unit configured to receive the syndrome that is output from the syndrome generator, and to provide a single error correction output, wherein the syndrome input received by the positive edge triggered flip-flop is the single error correction output from the control unit.

8. The error detection and correction apparatus of claim 6, further comprising: another positive edge triggered flip-flop that is configured to receive syndrome input based on the syndrome from the syndrome generator and to provide another syndrome output; and a double error location decoder configured to provide, based on the another syndrome output, a double error location decoder output.

9. The error detection and correction apparatus of claim 8, further comprising: a multiplexer configured to select one of the single error location decoder output and the double error location decoder output; and an error corrector configured to receive the selected output from the multiplexer.

10. The error detection and correction apparatus of claim 1, wherein the error location decoder corresponds to a double error location decoder configured to provide, based on the syndrome output, a double error location decoder output.

11. The error detection and correction apparatus of claim 10, further comprising: a control unit configured to receive the syndrome that is output from the syndrome generator, and to provide a double error correction output, wherein the syndrome input received by the positive edge triggered flip-flop is the double error correction output from the control unit.

12. An error detection and correction apparatus, comprising: means for outputting a syndrome that indicates whether input data includes an error; a positive edge triggered flip-flop that is configured to receive syndrome input based on the syndrome from the means for outputting and to provide a syndrome output; and means for generating an error location decoder output based on the syndrome output from the positive edge triggered flip-flop.

13. The error detection and correction apparatus of claim 12, further comprising: means for receiving a clock signal; means for delaying the clock signal by a given amount of time by passing the clock signal through a delay line, wherein the positive edge triggered flip-flop is controlled by the delayed clock signal.

14. The error detection and correction apparatus of claim 13, wherein the given amount of time is configured to mimic a delay associated with a critical path of the means for outputting.

15. The error detection and correction apparatus of claim 12, further comprising: means for generating corrected output data, wherein the means for generating the error location decoder output is configured to provide, based on the syndrome output, both a single error location decoder output and a double error location decoder output to the means for generating corrected output data.

16. The error detection and correction apparatus of claim 15, wherein the syndrome input received at the positive edge triggered flip-flop corresponds to the syndrome that is output from the means for outputting.

17. The error detection and correction apparatus of claim 12, wherein the means for generating is configured to provide, based on the syndrome output, a single error location decoder output.

18. The error detection and correction apparatus of claim 17, further comprising: means for providing a single error correction output based on the syndrome that is output from the means for outputting, wherein the syndrome input received by the positive edge triggered flip-flop is the single error correction output from the means for providing.

19. The error detection and correction apparatus of claim 17, further comprising: another positive edge triggered flip-flop that is configured to receive syndrome input based on the syndrome from the means for outputting and to provide another syndrome output; and means for generating a double error location decoder output based on the another syndrome output.

20. The error detection and correction apparatus of claim 19, further comprising: means for selecting one of the single error location decoder output and the double error location decoder output; and means for error correcting the selected output from the means for selecting.

21. The error detection and correction apparatus of claim 12, wherein the means for generating is configured to provide, based on the syndrome output, a double error location decoder output.

22. The error detection and correction apparatus of claim 21, further comprising: means for providing a double error correction output based on the syndrome that is output from the means for outputting, wherein the syndrome input received by the positive edge triggered flip-flop is the double error correction output from the means for providing.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The accompanying drawings are presented to aid in the description of embodiments of the disclosure and are provided solely for illustration of the embodiments and not limitation thereof.

(2) FIG. 1 is a block diagram illustrating an embodiment of an error detection and correction apparatus.

(3) FIG. 2 is a block diagram illustrating another embodiment of an error detection and correction apparatus having a flip-flop and a timing controller.

(4) FIG. 3 is a block diagram illustrating an embodiment of a delay line as a timing controller in the embodiment of the error correcting and decoding apparatus of FIG. 2.

(5) FIG. 4 is a block diagram illustrating yet another embodiment of an error detection and correction apparatus having flip-flops, a timing controller, separate single error correction (SEC) and double error correction (DEC) error location decoders, a multiplexer, and a flag generator.

(6) FIG. 5 is a block diagram illustrating an embodiment of an error detection and correction apparatus with logic configured to perform error detection and correction functions.

(7) FIG. 6 is a block diagram illustrating an embodiment of a memory device in which error detection and correction apparatus may be implemented.

DETAILED DESCRIPTION

(8) Aspects of the disclosure are described in the following description and related drawings directed to specific embodiments. Alternate embodiments may be devised without departing from the scope of the disclosure. Additionally, well-known elements will not be described in detail or will be omitted so as not to obscure the relevant details of the disclosure.

(9) The word exemplary is used herein to mean serving as an example, instance, or illustration. Any embodiment described herein as exemplary is not necessarily to be construed as preferred or advantageous over other embodiments. Likewise, the term embodiments does not require that all embodiments include the discussed feature, advantage or mode of operation.

(10) The terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of the embodiments. As used herein, the singular forms a, an and the are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will be further understood that the terms comprises, comprising, includes or including, when used herein, specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, or groups thereof. Moreover, it is understood that the word or has the same meaning as the Boolean operator OR, that is, it encompasses the possibilities of either and both and is not limited to exclusive or (XOR), unless expressly stated otherwise. It is also understood that the symbol / between two adjacent words has the same meaning as or unless expressly stated otherwise. Moreover, phrases such as connected to, coupled to or in communication with are not limited to direct connections unless expressly stated otherwise.

(11) Further, many embodiments are described in terms of sequences of actions to be performed by, for example, elements of a computing device. It will be recognized that various actions described herein can be performed by specific circuits, for example, central processing units (CPUs), graphic processing units (GPUs), digital signal processors (DSPs), application specific integrated circuits (ASICs), field programmable gate arrays (FPGAs), or various other types of general purpose or special purpose processors or circuits, by program instructions being executed by one or more processors, or by a combination of both. Additionally, these sequence of actions described herein can be considered to be embodied entirely within any form of computer readable storage medium having stored therein a corresponding set of computer instructions that upon execution would cause an associated processor to perform the functionality described herein. Thus, the various aspects of the disclosure may be embodied in a number of different forms, all of which have been contemplated to be within the scope of the claimed subject matter. In addition, for each of the embodiments described herein, the corresponding form of any such embodiments may be described herein as, for example, logic configured to perform the described action.

(12) FIG. 1 is a block diagram illustrating an embodiment of an error detection and correction apparatus 100 having a data input (databit_in) 102, an error check input (checkbit_in) 104, and a corrected data output (databit_out) 106. Such an error correcting code decoder may be implemented in various digital apparatus or devices for correcting data errors, for example, in memory devices such as spin-transfer torque magnetic random access memories (STT-MRAMs). It will be appreciated that the error correcting code decoder according to embodiments of the disclosure may also be used in various other apparatus or devices by persons skilled in the art. Referring to FIG. 1, the error detection and correction apparatus 100 includes a syndrome generator 108 which is configured to receive the data input (databit_in) 102 and the error check input (checkbit_in) 104. In an embodiment, the syndrome generator 108 is capable of generating a first vector signal output (S.sub.0), a second vector signal output (S.sub.1) and a third vector signal output (S.sub.3) in response to the data input (databit_in) 102 and the error check input (checkbit_in) 104.

(13) In an embodiment, the syndrome generator 108 comprises a parity-check matrix decoder, and the error check input (checkbit_in) 104 comprises a parity-check bit input. Such a syndrome generator 108 may be constructed by using one of many known error correcting codes (ECCs). In an embodiment, the parity-check matrix decoder may comprise an XOR-tree based parity-check matrix decoder. For example, the syndrome generator 108 may be constructed by implementing an ECC such as a double error correcting-triple error detecting (DEC-TED) Bose-Chaudhuri-Hocquenghem (BCH) code where is a primitive element in the Galois field GF(2.sup.n):

(14) $H=\left[\begin{array}{ccccc}1& 1& 1& \mathrm{.Math.}& 1\\ 1& & {}^2& \mathrm{.Math.}& {}^{n-1}\\ 1& {}^3& {}^6& \mathrm{.Math.}& {}^{3\left(n-1\right)}\end{array}\right]=\left[\begin{array}{c}1\\ H_1\\ H_3\end{array}\right]$

(15) The syndrome generated by the above parity check matrix may be divided into three parts,
S=v.Math.H.sup.T=[v.Math.1,v.Math.H.sub.1.sup.T,v.Math.H.sub.3.sup.T]=[S.sub.0, S.sub.1, S.sub.3]

(16) In alternate embodiments, other types of syndrome generators may also be implemented for error detection and correction.

(17) In the embodiment illustrated in FIG. 1, the error detection and correction apparatus 100 also includes a controller 110 which is configured to receive the first vector signal output (S.sub.0), the second vector signal output (S.sub.1) and the third vector signal output (S.sub.3) from the syndrome generator 108, and to generate a single error correction output (SEC_output) and a double error correction output (DEC_output) based on at least two of the three vector signals S.sub.0, S.sub.1 and S.sub.3 from the syndrome generator 108.

(18) In an embodiment, the controller 110 is implemented to generate the single error correction output (SEC_output) and the double error correction output (DEC_output), which are transmitted to the inputs of a single error correction (SEC) error location decoder 118 and a double error correction (DEC) error location decoder 120, respectively. The SEC error location decoder 118 and the DEC error location decoder 120 will be described in further detail below. In an embodiment, it is desirable to reduce the delay and dynamic power consumption of the error detection and correction apparatus 100 by not having both the SEC error location decoder 118 and the DEC error location decoder 120 actively operating at the same time. For example, if the error in the data input is a single error, then the DEC error location decoder 120 should not be active. Likewise, if the error is a double error, then the SEC error location decoder 118 should not be active.

(19) In an embodiment, the single error correction output (SEC_output) and the double error correction output (DEC_output) of the controller 110 are set to satisfy the above conditions. For example, if the first vector signal output (S.sub.0) from the syndrome generator 108 is one, which means that the data input is assumed to have a single error, then the double error correction output (DEC_output) of the controller 110 is a zero vector. In contrast, if the first vector signal output (S.sub.0) from the syndrome generator 108 is zero, which means that the data input is assumed to have a double error, then the single error correction output (SEC_output) of the controller is a zero vector.

(20) In an embodiment, the outputs SEC_output and DEC_output of the controller 110 may be generated by the following equations based on the first vector signal output (S.sub.0), the second vector signal output (S.sub.1) and the third vector signal output (S.sub.3) from the syndrome generator 108:
SEC_output=S.sub.0*[S.sub.1,S.sub.3]
DEC_output=(S.sub.0)*[S.sub.1,S.sub.3]

(21) where denotes the logical complement or NOT. For the triple error case, S.sub.0 is one, which is the same as the single error case.

(22) In the embodiment illustrated in FIG. 1, the error detection and correction apparatus 100 further includes a double error detector 112 which has inputs coupled to receive the first vector signal output (S.sub.0), the second vector signal output (S.sub.1) and the third vector signal output (S.sub.3) from the syndrome generator 108, and an output that generates a double error detection output (AL_DED) 114 based on the three vector signals S.sub.0, S.sub.1 and S.sub.3 received from the syndrome generator 108.

(23) In an embodiment, the double error detection output (AL_DED) 114 from the double error detector 112 may be generated by the following equation based on the second vector signal output (S.sub.1) and the third vector signal output (S.sub.3) from the syndrome generator 108:
AL_DED=S.sub.1.sup.3+S.sub.3

(24) In a further embodiment, a flag generator 116 is provided in the error detection and correction apparatus 100 as illustrated in FIG. 1. In an embodiment, the flag generator 116 is provided to determine the number of errors from zero error to triple error. In an embodiment, the flag generator 116 generates a two-bit variable called an error flag (error_flag) 122, which is output from the error detection and correction apparatus 100 as a two-bit indicator of zero error, single error, double error or triple error.

(25) In an embodiment, the error flag (error_flag) 122 may be determined based on the double error detection output (AL_DED) 114 from the double error detector 112 and the first vector signal output (S.sub.0) from the syndrome generator 108:

(26) TABLE-US-00001 TABLE 1 Relationship Number of between S.sub.0, Errors S.sub.0 S.sub.1 and S.sub.3 AL_DED error_flag No Error 0 S.sub.1 = S.sub.3 = 0 0 00 Single Error 1 S.sub.1.sup.3= S.sub.3 0 01 Double Error 0 S.sub.1.sup.3 S.sub.3 1 10 Triple Error 1 S.sub.1.sup.3 S.sub.3 1 11

(27) According to the table above, the relationship between the error_flag and S.sub.0 can be expressed as follows:
Most significant bit (MSB) of error_flag=AL_DED
Least significant bit (LSB) of error_flag=S.sub.0

(28) As described above, the SEC error location decoder 118 is provided to locate single errors and the DEC error location decoder 120 is provided to locate double errors. In an embodiment, the SEC error location decoder 118 is coupled to receive the single error correction output (SEC_output) from the controller 110 and outputs a single error location decoder output (e_sec) 124 based on the SEC_output from the controller 110. In an embodiment, the DEC error location decoder 120 is coupled to receive the double error correction output (DEC_output) from the controller 110 and outputs a double error location decoder output (e_dec) 126 based on the DEC_output from the controller 110.

(29) In an embodiment, a multiplexer 128 is provided in the error detection and correction apparatus 100 to generate a multiplexer output 130. In the embodiment illustrated in FIG. 1, the multiplexer 128 comprises a 2:1 multiplexer having a first input coupled to the single error location decoder output (e_sec) 124, a second input coupled to the double error location decoder output (e_dec) 126, and a multiplexer output 130 to output either the single error location decoder output (e_sec) or the double error location decoder output (e_dec) based on a control input 132.

(30) In the embodiment illustrated in FIG. 1, the control input 132 for the multiplexer 128 is an input that receives the logical complement of the double error detection output (AL_DED) from the double error detector 112. In an embodiment, the control signal, which is (AL_DED), at the control input 132 of the multiplexer 128 determines the output 130 of the multiplexer 128 according to the following relationships:

(31) TABLE-US-00002 TABLE 2 Control Signal (~AL_DED) Output of Multiplexer 0 Output of DEC Error Location Decoder e_dec 1 Output of SEC Error Location Decoder e_sec

(32) In this embodiment, bit errors up to double errors in the data input may be corrected. Although triple errors may not be correctable in this embodiment, an error flag 122 generated by the flag generator 116 may indicate the presence of a triple error. For example, in the embodiment described with respect to Table 1 above, a two-bit error flag of 11 indicates the presence of a triple error.

(33) In the embodiment described above, the relationships between the number of errors, the first vector signal output (S.sub.0) from the syndrome generator 108, the output (e_sec) 124 from the SEC error location decoder 118, the output (e_dec) 126 from the DEC error location decoder 120, the logical complement of AL_DED (AL_DED), and the output (e) 130 of the multiplexer 128 are summarized in the following table:

(34) TABLE-US-00003 TABLE 3 Number Multiplexer of Errors S.sub.0 e_sec e_dec ~AL_DED Output No Error 0 zero vector zero 1 e_sec = zero vector vector Single 1 correct error zero 1 e_sec = correct Error vector for vector error vector for single error single error Double 0 zero vector correct 0 e_dec = correct Error error error vector for vector for double error double error Triple 1 incorrect error zero 0 e_dec = zero Error vector for vector vector triple error

(35) In a further embodiment, an error corrector 134 is provided which has a data input coupled to receive the input data (databit_in), an error vector input coupled to the error vector output (e) 130 of the multiplexer 128, and an output 106 which outputs corrected data (databit_out).

(36) FIG. 2 is a block diagram illustrating another embodiment of an error detection and correction apparatus 200 which includes a flip-flop and a timing controller but not separate SEC and DEC error location decoders with a multiplexer. In FIG. 2, the error detection and correction apparatus 200 has a data input (databit_in) 202, an error check input (checkbit_in) 204, a control input 206, a corrected data output (databit_out) 208, a single error detection output (AL_SED) 210 and a triple error detection output (AL_TED) 212. In the embodiment illustrated in FIG. 2, the error detection and correction apparatus 200 includes a syndrome generator 214. In an embodiment, the syndrome generator 214 in FIG. 2 may be similar to the syndrome generator 108 as shown in FIG. 1 and described above. For example, the syndrome generator 214 in FIG. 2 may comprise a parity-check matrix decoder, such as an XOR-tree based parity-check matrix decoder using a BCH code, as described above with respect to the embodiment shown in FIG. 1.

(37) In the embodiment illustrated in FIG. 2, a timing controller 216 is provided. In an embodiment, the timing controller 216 includes a delay line, an embodiment of which will be described in further detail below with reference to FIG. 3. Referring to FIG. 2, the timing controller 216 is coupled to the control input 206 and delays the incoming signal from the control input 206 by a given amount of time before the incoming signal exits the timing controller 216 at a control output 218. In an embodiment, the error detection and correction apparatus 200 includes a flip-flop 220 having a data input 222 coupled to the output of the syndrome generator 214, a toggle input 224 coupled to the control output 218 of the timing controller 216, and an output which outputs a delivered syndrome output 226 based on the syndrome received from the syndrome generator 214 and the control output 218 of the timing controller 216.

(38) In an embodiment, an error location decoder 228 is provided in the error detection and correction apparatus 200. In an embodiment, the error location decoder 228 has an input coupled to receive the delivered syndrome output 226 from the flip-flop 220, an error location decoder output 230, a single error decoder output (SED) 232 and a double error decoder output (DED) 234. In the embodiment shown in FIG. 2, an error corrector 236 is provided in the error detection and correction apparatus 200. In an embodiment, the error corrector 236 has a first input coupled to the data input (databit_in) 202, a second input coupled to the error location decoder output 230, and an output which generates the corrected data output (databit_out) 208 of the error detection and correction apparatus 200.

(39) In an embodiment, the error detection and correction apparatus 200 also includes an error detector 238 which generates a single error detection output (AL_SED) 210 and a triple error detection output (AL_TED) 212. In an embodiment, the error detector 238 has a first input coupled to receive the delivered syndrome output 226 from the flip-flop 220, a second input coupled to receive the single error decoder output (SED) 232, and a third input coupled to receive the double error decoder output (DED) 234 from the error location decoder 228.

(40) In an embodiment, the error detector 238 includes an OR gate 240 having an input coupled to receive the delivered syndrome output 226 and an output configured to output the single error detection output (AL_SED) 210. In a further embodiment, the error detector 238 also includes an AND gate 242 having a first input coupled to the output of the OR gate 240, a second input coupled to the complement of the single error decoder output (SED) 232, and a third output coupled to the complement of the double error decoder output (DED) 234. In the embodiment shown in FIG. 2, the output of the AND gate 242 is the triple error detection output (AL_TED) 212.

(41) FIG. 3 is a block diagram illustrating an embodiment of the timing controller 216 which comprises a delay line 300 to generate a control signal for the flip-flop 220 in the embodiment of the error detection and correction apparatus of FIG. 2. In an embodiment, the control input 206 receives a clock signal 302 having a positive leading edge, and the positive leading edge of the clock signal 302 is delayed by a given amount of time when the clock signal 302 exits the output 218 of the delay line 300.

(42) In an embodiment, a plurality of logic gates or buffers may be provided in the delay line 300 to delay the propagation of the clock signal 302. In the embodiment shown in FIG. 3, the delay line 300 includes one or more AND gates, such as AND gates 304a, 304b, 304c and 304d, one or more NAND gates, such as NAND gate 306, and one or more buffers, such as buffers 308a, 308b and 308c, to delay the propagation of the clock signal 302 from the input 206 to the output 218 of the delay line 300. Other types of logic gates, buffers or delay lines may also be implemented within the scope of the disclosure. Moreover, although FIG. 3 illustrates a positive edge triggered flip-flop 220, such as a D flip-flop, other types of flip-flops may be implemented in other embodiments. For example, instead of positive edge triggering, other types of triggering such as negative edge triggering may be implemented.

(43) In an embodiment, the delay line 300 and the flip-flop 220 in FIG. 3 are implemented to reduce the probability of invalid transitions in the error location decoder 228 as shown in FIG. 2. With a set amount of time delay provided by the delay line 300, the clock signal 302 reaches the flip-flop 220 after the syndrome is settled, and the syndrome is delivered by the flip-flop 220 to the error location decoder 228 as a delivered syndrome only after the syndrome is settled to avoid invalid transitions. In an embodiment, the delay line 300 is provided to mimic the worst delay of the syndrome generated by the syndrome generator 214. In an embodiment, the delay line 300 is created by mimicking the critical path of the circuit from the data and error check (databit_in) and (checkbit_in) inputs 202 and 204 to the output of the syndrome generator 214. The worst-case time delay of this critical path is the maximum time (T.sub.I-S) needed for settling the syndromes.

(44) In an embodiment, to ensure proper flip-flop operation, the delay line 300 may be designed such that the total time delay produced by the delay line 300 is slighter greater than the maximum time (T.sub.I-S) needed for settling the syndromes even though the overall delay of the error detection and correction apparatus 200 is slightly increased. For example, in the embodiment shown in FIG. 3, the number of logic gates such as AND gates 304a, 304b, 304c and 304d and the NAND gate 306 may be implemented to mimic the maximum time (T.sub.I-S) needed to settle the syndromes on the critical path from the syndrome inputs to the syndrome output, and the buffers such as buffers 308a, 308b and 308c may be added to produce additional time delay.

(45) FIG. 4 is a block diagram illustrating yet another embodiment of an error detection and correction apparatus having flip-flops, a timing controller, separate single error correction (SEC) and double error correction (DEC) error location decoders, a multiplexer, and a flag generator. In the embodiment illustrated in FIG. 4, the error detection and correction apparatus 400 has a data input (databit_in) 402, an error check input (checkbit_in) 404, and a corrected data output (databit_out) 406. In this embodiment, the error detection and correction apparatus 400 includes a syndrome generator 408 which is configured to receive the data input (databit_in) 402 and the error check input (checkbit_in) 404.

(46) In an embodiment, the syndrome generator 408 is capable of generating a first vector signal output (S.sub.0), a second vector signal output (S.sub.1) and a third vector signal output (S.sub.3) in response to the data input (databit_in) 402 and the error check input (checkbit_in) 404 in a similar manner to the syndrome generator 108 in the embodiment shown in FIG. 1 and described above. In an embodiment, the syndrome generator 408 comprises a parity-check matrix decoder, and the error check input (checkbit_in) 404 comprises a parity-check bit input. In an embodiment, the parity-check matrix decoder may comprise an XOR-tree based parity-check matrix decoder. For example, the syndrome generator 408 may be constructed by implementing any known ECC such as the BCH code.

(47) In the embodiment illustrated in FIG. 4, the error detection and correction apparatus 400 also includes a controller 410 which is configured to receive the first vector signal output (S.sub.0), the second vector signal output (S.sub.1) and the third vector signal output (S.sub.3) from the syndrome generator 408, and to generate a single error correction output (SEC_output) and a double error correction output (DEC_output) based on the three vector signals S.sub.0, S.sub.1 and S.sub.3 from the syndrome generator 108. In an embodiment, the SEC_output and DEC_output may be generated in the same manner as described above with respect to FIG. 1.

(48) In the embodiment illustrated in FIG. 4, the error detection and correction apparatus 400 further includes a double error detector 412 which has inputs coupled to receive the first vector signal output (S.sub.0), the second vector signal output (S.sub.1) and the third vector signal output (S.sub.3) from the syndrome generator 108, and an output that generates a double error detection output (AL_DED) 414 based on at least two of the three vector signals S.sub.0, S.sub.1 and S.sub.3 from the syndrome generator 408.

(49) In an embodiment, the double error detection output (AL_DED) 414 from the double error detector 412 may be generated by the same equation described above with respect to FIG. 1 based on the second vector signal output (S.sub.1) and the third vector signal output (S.sub.3) received from the syndrome generator 108:
AL_DED=S.sub.1.sup.3+S.sub.3

(50) In an embodiment, a flag generator 416 is provided in the error detection and correction apparatus 400 as illustrated in FIG. 4 in a similar manner to the embodiment described above with respect to FIG. 1. Referring to FIG. 4, the flag generator 416 generates a two-bit error flag (error_flag) 422, which is output from the error detection and correction apparatus 400 as a two-bit indicator of zero error, single error, double error or triple error. In an embodiment, the two-bit error flag (error_flag) 422 may be generated to indicate the presence of zero, single, double or triple errors according to Table 1 described above with respect to FIG. 1.

(51) Referring to FIG. 4, a timing controller 424 having a control input 426 which receives a clock signal and an output 428 which produces a time-delayed clock output is provided. In an embodiment, the timing controller 424 may comprise a delay line such as the delay line 300 as illustrated in FIG. 3 and described above. For example, such a delay line may comprise one or more logic gates, such as AND or NAND gates, or one or more buffers, or a combination of logic gates and buffers, as shown in FIG. 3. Referring to FIG. 4, the time-delayed clock output from the output 428 of the timing controller 424 is provided as toggle inputs for two flip-flops 430 and 432.

(52) In the embodiment shown in FIG. 4, the first flip-flop 430 is provided which includes a data input 434 to receive the single error correction output (SEC_output) from the controller 410 and a toggle input 436 to receive the time-delayed clock output from the timing controller 424. In an embodiment, the first flip-flop 430 comprises a D flip-flop with positive edge triggering. Likewise, the second flip-flop 432 is provided which includes a data input 438 to receive the double error correction output (DEC_output) from the controller 410 and a toggle input 440 to receive the time-delayed clock output from the timing controller 424. In a further embodiment, the second flip-flop 432 may also comprise a D flip-flop with positive edge triggering. In alternate embodiments, other types of flip-flops may be implemented, and triggering of the flip-flops need not be positive edge triggering by clock signals.

(53) In the embodiment shown in FIG. 4, the first flip-flop 430 outputs a delivered SEC_output 442 to a single error correction (SEC) error location decoder 444, while the second flip-flop 432 outputs a delivered DEC_output 446 to a double error correction (DEC) error location decoder 448. The SEC_output and the DEC_output may be generated by the controller 410 in the same manner as described above with respect to FIG. 1. The first and second flip-flops 430 and 432 are provided in the embodiment as shown in FIG. 4 to ensure that the SEC_output and DEC_output are delivered to the SEC error location decoder 444 and the DEC error location decoder 448, respectively, only after the syndrome is settled to avoid invalid transitions.

(54) In an embodiment, the SEC error location decoder 444 and the DEC error location decoder 448 in FIG. 4 generate a single error location decoder output (e_sec) 450 and a double error location decoder output (e_dec) 452, respectively, in the same manner as described above with respect to FIG. 1. Referring to FIG. 4, a multiplexer 454 having a first input coupled to receive the single error location decoder output (e_sec) 450, a second input coupled to receive the double error location decoder output (e_dec) 452, and a control input 456. In an embodiment, the control input 456 is coupled to receive the logical complement of AL_DED in the same manner as described above with respect to FIG. 1. In an embodiment, the output (e) 458 of the multiplexer 454 is selected in the same manner as described above with respect to FIG. 1, according to the relationships described in Tables 2 and 3, for example.

(55) In a further embodiment, an error corrector 460 is provided in the error detection and correction apparatus 400 of FIG. 4. In an embodiment, the error corrector has a data input coupled to receive the input data (databit_in), an error vector input coupled to the error vector output (e) 458 of the multiplexer 454, and an output 406 which outputs corrected data (databit_out).

(56) FIG. 5 is a simplified block diagram illustrating an embodiment of an error detection and correction apparatus with logic configured to perform error detection and correction functions. In the embodiment illustrated in FIG. 5, the error detection and correction apparatus 500 includes logic configured to locate single errors in block 505, logic configured to locate double errors 510, and logic configured to generate corrected output data 515. Each of the logic configured to locate single errors, logic configured to locate double errors, and logic configured to generate corrected output data as illustrated in blocks 505, 510 and 515 may include one or more elements in various embodiments of the error detection and correction apparatus described above with respect to FIGS. 1-4.

(57) FIG. 6 is a block diagram illustrating an embodiment of a memory device in which error detection and correction apparatus may be implemented. In the embodiment illustrated in FIG. 6, a memory 600 includes memory cells 605 and an error detection and correction apparatus 610. The error detection and correction apparatus 610 may be integrated on the same chip as memory cells 605, or be provided on a separate chip. As shown in FIG. 6, raw data from the memory cells may be transmitted along arrow 615 to the error detection and correction apparatus 610 for error detection and correction, and corrected data from the error detection and correction apparatus 610 may be transmitted along arrow 620 back to the memory cells 605. The error detection and correction apparatus 610 may include any of the various embodiments described above with respect to FIGS. 1-4.

(58) Those of skill in the art will appreciate that information and signals may be represented using any of a variety of different technologies and techniques. For example, data, instructions, commands, information, signals, bits, symbols, and chips that may be referenced throughout the above description may be represented by voltages, currents, electromagnetic waves, magnetic fields or particles, optical fields or particles, or any combination thereof.

(59) Further, those of skill in the art will appreciate that the various illustrative logical blocks, modules, circuits, and algorithm steps described in connection with the embodiments disclosed herein may be implemented as electronic hardware, computer software, or combinations of both. To clearly illustrate this interchangeability of hardware and software, various illustrative components, blocks, modules, circuits, and steps have been described above generally in terms of their functionality. Whether such functionality is implemented as hardware or software depends upon the particular application and design constraints imposed on the overall apparatus. Skilled artisans may implement the described functionality in varying ways for each particular application, but such implementation decisions should not be interpreted as causing a departure from the scope of the disclosure.

(60) The methods, sequences or algorithms described in connection with the embodiments disclosed herein may be embodied directly in hardware, in a software module executed by a processor, or in a combination of the two. A software module may reside in RAM memory, flash memory, ROM memory, EPROM memory, EEPROM memory, registers, hard disk, a removable disk, a CD-ROM, or any other form of storage medium known in the art. An exemplary storage medium is coupled to the processor such that the processor can read information from, and write information to, the storage medium. In the alternative, the storage medium may be integral to the processor.

(61) Accordingly, an embodiment of the disclosure can include a computer readable media embodying a method for error detection and correction. Accordingly, the disclosure is not limited to illustrated examples and any means for performing the functionality described herein are included in embodiments of the disclosure.

(62) While the foregoing disclosure shows illustrative embodiments, it should be noted that various changes and modifications could be made herein without departing from the scope of the appended claims. The functions, steps or actions of the method claims in accordance with embodiments described herein need not be performed in any particular order unless expressly stated otherwise. Furthermore, although elements may be described or claimed in the singular, the plural is contemplated unless limitation to the singular is explicitly stated.