Source: http://www.google.com/patents/US7962838?dq=ascentive
Timestamp: 2014-08-02 00:31:52
Document Index: 474627050

Matched Legal Cases: ['Application No. 2008', 'art 20', 'art 60', 'art 20', 'art 30', 'art 100', 'art 90']

Patent US7962838 - Memory device with an ECC system - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign in<nobr>Advanced Patent Search</nobr>PatentsA memory device has an error detection and correction system constructed on a Galois finite field. The error detection and correction system includes calculation circuits for calculating the finite field elements based on syndromes obtained from read data and searching error locations, the calculation...http://www.google.com/patents/US7962838?utm_source=gb-gplus-sharePatent US7962838 - Memory device with an ECC systemAdvanced Patent SearchPublication numberUS7962838 B2Publication typeGrantApplication numberUS 12/555,507Publication dateJun 14, 2011Filing dateSep 8, 2009Priority dateOct 31, 2008Also published asUS20100115383Publication number12555507, 555507, US 7962838 B2, US 7962838B2, US-B2-7962838, US7962838 B2, US7962838B2InventorsHaruki TodaOriginal AssigneeKabushiki Kaisha ToshibaExport CitationBiBTeX, EndNote, RefManPatent Citations (52), Non-Patent Citations (1), Referenced by (2), Classifications (12), Legal Events (1) External Links: USPTO, USPTO Assignment, EspacenetMemory device with an ECC systemUS 7962838 B2Abstract A memory device has an error detection and correction system constructed on a Galois finite field. The error detection and correction system includes calculation circuits for calculating the finite field elements based on syndromes obtained from read data and searching error locations, the calculation circuits having common circuits, which are used in a time-sharing mode under the control of internal clocks.
the syndrome element calculation part and the error searching part using expression indexes to perform multiplication and addition between finite field elements, the expression indexes, in which differing prime factors of the domain of a finite field are �p� and �q�, representing indexes of the finite field elements by combinations of numbers in mod p and numbers in mod q.
CROSS-REFERENCE TO RELATED APPLICATION This application is based on and claims the benefit of priority from the prior Japanese Patent Application No. 2008-281316, filed on Oct. 31, 2008, the entire contents of which are incorporated herein by reference.
SUMMARY OF THE INVENTION According to an aspect of the present invention, there is provided a memory device having an error detection and correction system constructed on a Galois finite field, wherein
BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 shows a 3EC-BCH-ECC system in accordance with an embodiment of the present invention.
(C) In an ECC system for correcting errors with a finite field, adder circuits and parity checker circuits, each of which calculates a product and a sum of finite elements represented by �expression indexes�, respectively, are used for calculating quantities derived from the syndrome and searching solutions of an equation used for searching elements designating error locations. These circuits are physically shared as widely as possible, and used in a time-sharing mode under the control of internal clocks.
(D) In the explanation described above, �expression index� is defined as follows: when designating elements of finite field GF(2n) by indexes �k� of roots αk of the basic irreducible polynomial, the indexes may be represented as a combination of the remainders with different factors of 2n−1 as modulo, and the remainders are referred to as �expression indexes�. For example, supposing that the domain 2n−1 is factorized into at least two prime factors �p� and �q�, a combination of the expression indexes k(mod p) and k(mod q) is utilized.
(F) In the ECC system, in which the elements of finite field are represented by �expression index� components with the different factors as modulo, decoder circuits for searching the expression index components of the element of finite field are formed to include decoder groups, which are used in common to two components of the expression indexes, and the expression index components are obtained by taking a logic between the outputs of the decoder group.
Since the number of elements constituting the ECC code is �h� excepting zero factor, (h−1)-degree polynomial f(x) shown in the following Expression 1 becomes an information polynomial, the coefficients of which designate data.
Information bits in data bits are assigned to coefficients a2n�ah−1. As shown in the following Expression 2, with respect to polynomial f(x) with the above-described coefficients, polynomial f(x)x2n beginning from 2n-degree is divided by g(x), and the remaining is referred to as r(x).
f(x)x 2n =q(x)g(x)+r(x) r(x)=b 2n−1 x 2n−1 +b 2n−2 x 2n−2 + . . . +b 1 x+b 0 [Exp. 2]
The coefficients, b2n−1�b0, of the remaining polynomial r(x) are used as check bits, which constitute data bits to be stored in the memory together with information bits ah−1�a2n.
v ⁡ ( x ) = ⁢ f ⁡ ( x ) ⁢ x 2 ⁢ n + r ⁡ ( x ) + e ⁡ ( x ) = ⁢ q ⁡ ( x ) ⁢ g ⁡ ( x ) + e ⁡ ( x ) [ Exp . ⁢ 3 ] The error polynomial e(x) is solved, and error correction may be achieved.
ν(x)≡S1(x)mod m1(x)→e(x)≡S 1(x)mod m 1(x)ν(x)≡S3(x)mod m3(x)→e(x)≡S 3(x)mod m 3(x) [Exp. 4]
If errors are present at degree numbers �i� and �j�, e(x) is expressed as follows; e(x)=xi+xj. Therefore, search the degree numbers �i� and �j�, and error locations may be detected, i.e., which data is erroneous will be determined.
So, calculation is performed in GF(2n) with respect to the indexes of roots α of m1(x)=0 to search �i� and �j�. Assume that the remaining polynomial obtained by dividing xn by m1(x) is referred to pn(x), αn=pn(α). Therefore, unknown numbers X1, X2 and syndromes S1, S3 are defined as follows.
Note here that indexes of X1 and X2 are �i� and �j�, respectively, and indexes of S1 and S3 are σ1(=σ) and σ3, respectively.
(x)=(x−X 1)(x−X 2)=x 2 +Sx+D=0 S=S 1 =X 1 +X 2 D=X1X2 [Exp. 7]There is a relationship between these coefficients and symmetric equations (i.e., syndromes) S1(=S) and S3, and the following Expression 8 will be obtained.
(2) Second, in case of two errors, error searching is to search index �n� of the root X=αn of (x)=x2+Sx+ζ/S=0. In this case, since S≠0 and D≠0, i.e., ζ=SD≠0, by use of variable transformation of: x=Sy, the quadratic equation to be solved is transformed to that shown in the following Expression 9.
y 2 +y=ζ/S 3 [Exp. 9]That is, the error location searching equation is subjected to variable transformation, and variable part and syndrome part thereof are separated from each other.
As described above, as a result of that (x) is transformed to have the variable part and syndrome part separated from each other, it becomes possible to search �n� the only based on the relationship between indexes. Explaining in other words, compare y2+y (where, finite field element is substituted for �y�) with ζ/S3 with a decoder, and search two roots, and two error locations will be obtained. The solution method with a decoder will be explained in detail later.
(3) The case where there are three or more errors includes the following equivalent two cases: one is contradictory case defined by S=0 and ζ≠0; and the other is that solution �n� is not searched. That is, in case necessary decoding is impossible, it is judged that there are three or more errors.
Root calculation in case of two errors will be performed as follows. Assume that the index of the result, α2i+α1, that is obtained by substituting α1 for the variable �y� in the variable part y2+y is �y1�. If this is congruent with index σ(ζ/S3) of ζ/S3 in mod h, �i� thereof becomes the index of error position �y�. In other words, �i� satisfying the congruence σ(ζ/S3)≡y1 mod h is searched as the index of �y�.
If there are not two �i�s satisfying �y1� corresponding the right side index determined from the syndromes, it designates that no solution is searched, i.e., there are three or more bit errors.
A practical error position will be searched as a bit position �n� based on the equation of: x=Sy=ασ1+i=αn. That is, to return index �i� of �y� corresponding to index �yi� to the real index of variable axe, multiply �y� by S=ασ1 to search index �n� of the solution �X�, and n≡σ1+i mod h is the index of the solution �X� corresponding to the error position. With this �X�, (x)=0 is satisfied.
Since finite field elements constituting the code of system are �h� excepting zero factor, coefficients of (h−1)-degree polynomial express data. Coefficient parts up to (3n−1)-degree are used as check bits of data. Information polynomial corresponding to Expression 1 will be expressed in the following Expression 10.
Information bits in data bits are assigned to coefficients a3n�ah−1. As shown in the following Expression 11, with respect to polynomial f(x) with the above-described coefficients, polynomial f(x) x3n beginning from 3n-degree is divided by g(x), and the remaining is referred to as r(x).
f(x)x 3n =q(x)g(x)+r(x) r(x)=b 3n−1 x 3n−1 +b 3n−2 x 3n−2 + . . . +b 1 x+b 0 [Exp. 11]
The coefficients b3n−1�b0 of the remaining polynomial r(x) are used as check bits, which constitute data bits to be stored in the memory together with information bits ah−1�a3n.
v ⁡ ( x ) = ⁢ f ⁡ ( x ) ⁢ x 3 ⁢ n + r ⁡ ( x ) + e ⁡ ( x ) = ⁢ q ⁡ ( x ) ⁢ g ⁡ ( x ) + e ⁡ ( x ) [ Exp . ⁢ 12 ] Search error polynomial e(x) in the Expression 12, and error correction may be achieved.
ν(x)≡S1(x)mod m1(x)→e(x)≡S 1(x)mod m 1(x)ν(x)≡S3(x)mod m3(x)→e(x)≡S 3(x)mod m 3(x)ν(x)≡S5(x)mod m5(x)→e(x)≡S 5(x)mod m 5(x) [Exp. 13]
If errors are present at degree numbers �i�, �j� and �k�, e(x) is represented as follows: e(x)=x1+x1+xk. Therefore, search degree numbers �i�, �j� and �k�, and error locations may be decided, i.e., which data is erroneous will be determined.
So, calculation is performed in GF(2n) with respect to the indexes of roots α of m1(x)=0 to search �i�, �j� and �k�. Assume that the remaining polynomial obtained by dividing xn by m1(x) is referred to pn(x), αn=pn(α). Therefore, unknown numbers X1, X2 and X3, and syndromes S1, S3 and S5 are defined as follows.
Note here that indexes of X1, X2 and X3 are �i�, �j� and �k�, respectively, and indexes of S1, S3 and S5 are σ1(=σ), σ3 and σ5, respectively.
(x)=(x−X 1)(x−X 2)(x−X 3)=x 3 +Sx 2 +Dx+T=0 S=S 1 =X 1 +X 2 +X 3 D=X 1 X 2 +X 2 X 3 +X 3 X 1 T=X1X2X3 [Exp. 16]There are two solution methods for the above-described polynomial. First decoding solution method 1 will be firstly explained below.
ζD=ζS 2+ηζT=ζS 3 +ηS+ζ 2 [Exp. 17](where, SD+T=S3+S3=ζ and S3D+S2T�S5+S5=ζ)
(3) Equivalent to cases (1) and (2) where solution �n� is not searched in the solution search process in 2EC-EW branch and 3EC-EW branch, it is judged that there are four or more errors.
In case there are three errors, in place of the method of sequentially substituting finite field elements for �x� to search a solution, it will be used such a method as to prepare solution candidates as table in advance, and then search index �n� of root x=αn of (x)=0 by use of the table. The calculation method will be explained below.
First, the polynomial of the error search equation, (x), is transformed, the variable part and syndrome part are separated from each other. By use of this, solution �n� may be searched based on the relationships between indexes of the solution candidates and the syndrome indexes.
x=az+b a=(η/ζ)1/2 b=S [Exp. 19]As a result of this variable transformation, the following Expression 20 will be obtained because of η≠0 in the case of three errors,
Index Zj of α3j+αj=αzj are preliminary searched by substituting αj for the variable part �z� in the equation, and summarized in a table.
On the other hand, the index of the syndrome part ζ5/2/ζ3/2 is (5/2) σζ=(3/2)ση. Therefore, �j� satisfying (5/2)σζ−(3/2)σn≡Zj mod h is that transformed from the error index. The practical error position may be searched from the following process: search σx of σa+j≡σx mod h from az=ασa+j=ασx; and search the bit position �n� of X=az+S=ασX+ασ1=αn.
Note here that if there is not searched �j� corresponding to zj, there are four or more errors.
Input to encode part 20 is information polynomial f(x) with coefficients α3n≠ah−1, to which h−1−3n data bits are assigned. Only coefficients of suitable degrees necessary for data bits are selected as information bits, and other coefficients, which are not used, are dealt with fixed data (�0� or �1�). With these fix data, which are not stored in the memory, the system may be constructed to be adaptable to the memory capacitance.
Next, parity checks between S3 and S3 and between S5 and S5 are performed with parity checkers 41 and 42, ζ and η are searched, respectively. With respect to these indexes in the calculation, expression indexes are used, which are distinguished from each other with mod p, mod q and mode r, where prime factors �p�, �q� and �r� of h (=pqr).
If all of S, ζ and η are zero, gate 71 detects it to output a signal �no error�. If S is not zero, gate 72 detects it to output a signal �1 error)�. In receipt of this output, Sy adder 54 output �n� as the index of S.
If ζ is zero and η is not zero, gate 73 outputs a signal designating that there is no solution in 1EC, i.e., �no solution 1EC� that designates there are two or more errors.
Next, indexes of �a� and �Sa2�, each being product or quotient between powers of syndromes S, S3 and S5, and ζ and η, are calculated in adder circuits 51 and 54. In these circuits, calculations are performed with congruences of mod p, mod q and mod r, and resultant expression indexes are used in the successive processing.
4-input parity checker 43 searches �T� that is an addition of S3, Sa2 and ζ of three elements. This parity checker is for performing addition of mod 2 between coefficients of the same degrees of the polynomial expressed by the input indexes. Vss is input to the remaining input node(s) of this parity checker.
Adder circuits 53 and 54 are for searching �y� based on y2+y=ζ/S3 corresponding to 2EC and calculating the expression index of error position �n� by transformation of x=Sy. The input portion of adder circuit 53 receives ζ and S−3 and calculates the expression index of ζ/S3 of the syndrome part in the solution searching polynomial. The calculated result, �S� and �1 error� are input to the input portion of the next adder circuit 54, and index �i� of �y� satisfying y2+y=0 will be decoded at the input portion.
If 1 error, ζ/S3 becomes zero, then there is no index of ζ/S3 in spite of that there are two solutions y=�1� and �zero� satisfying y2+y=0. That is, there is no index output from the preceding adder circuit. Therefore, when 1 error, the signal is directly received at the gate 72 of the syndrome calculation part, and the index of �y� satisfying y2+y=0 will be decoded. In this case, the solution is decoded as �1 error�. Including this case, expression indexes will be output as corresponding to indexes �n� of two errors from �i� as a result of decoding and index σ1.
Further, in case there is not searched index �i� of the decoding result �y� at the input portion, it designates that 2EC system is not adaptable, so that signal �no solution 2EC� is generated. In case whether this signal is output or S=0 (double root), there is no solution in the 2EC-EW system, and gate 75 generates signal �not solved 2EC�.
Adder circuits 55 and 56 are for searching �z� based on z3+z=ζ5/2/η3/2 corresponding to 3EC and calculating the expression index of transformation of X=az. The adder circuit 55 receives expression indexes of ζ5/2 and η−3/2 to output the expression index of ζ5/2/η3/2.
The next adder circuit 56 is for searching �z� based on z3+z=ζ5/2/η3/2 corresponding to 3EC and calculating the expression index of σx based on the transformation of az. The input signals of this adder are resultant zi of the preceding portions and the expression index of index σa of �a�.
At the input portion of adder 56, index �j� satisfying z3+z=ζ5/2/η3/2 will be decoded. Based on the relationship between the decode result �j� and �a�, the expression index of index �az� corresponding three errors from the expression index σa. In case there is not searched index �j� of the decoding result �z� at the input portion, it designates that 3EC system is not adaptable, so that signal �no solution 3EC� is generated.
In case whether this signal is output or η=0, there is no solution in the 3EC-EW system, and gate 76 generates signal �not solved 3EC�.
Parity checker 44 disposed on the right end calculates the expression index of error position �n� as the index of �X�, i.e., as the sum of X=az+S.
The signal �non correctable�, which is generated when there are four or more errors and it is not correctable, will be generated from OR gate 74 when there is obtained �no solution 1EC� or �not solved 2EC� or �not solved 3EC�.
Error correcting part 60 is a logic circuit, which finally corrects the read data of the memory core 10 and outputs it. Where the error location information from 2EC part is used is the case of T=0, i.e., ζ=0 or T=0. Therefore, gate 62 is on by �0� output of gate 61, so that error position information from 3EC is not used. In case 2EC condition is not satisfied, gate 62 is off while gate 63 is on, so that the error position information from 3EC will be used.
When error position information is input, the coefficient of data polynomial ν(x) corresponding to the error position is inverted in logic at XOR gate 64, and corrected data �dn� is output. In case of �no error� or �non correctable�, gate 77 outputs through signal �through�, and read data will be output as it is as data �dn�.
The coefficients �D� and �T� of the error searching polynomial, i.e., cubic polynomial (x) shown in Expression 16 constitute simultaneous equations containing two variables together with S, ζ and η as shown in the following Expression 21
SD+T=ζ (ζ+S 3)D+S 2 T=η [Exp. 21]To express �D� and �T� by the syndromes, the simultaneous equations will be solved. Since the coefficient matrix becomes ζ, equations to be solved are represented as follows:
If ζ≠0, �D� and �T� will be decided. Therefore, go to the process of searching the error searching equation (x)=0. If ζ=0, one of the unknowns, for example �T�, is optionally set, and �D� may be searched in accordance with a method of solving the simultaneous equations with two elements. However, if three errors are generated, there is no optional relationship among �S�, �D� and �T�. Therefore, in case the optional relationship is satisfied, it designates four errors, or two errors or less. If there is not obtained a solution in the branch of 2EC-EW, it designates four or more errors.
The solving method of the error searching cubic equation will be formalized here for making it printed on a circuit system. The cubic equation to be solved is represented as follows: w3+w=ζ5/η3. Since ζ≠0, it is confirmed that �w� is not zero element or �1�.
When selecting one root �w�, β0=(w+1)η/ζ, and β1=α=(wη/ζ)1/2 are obtained. Since β0/β1 2=(w+1)/w, the quadratic error searching equation will be as follows: z2+z=(w+1)/w. Since (w+1)/w≠0, two roots �z1� and �z2� are obtained. As a result, together with the root α=β1 of the linear equation, three error position solutions will be obtained as follows: X1=β1+S; X2=β1z1+S; and X3=β1z2+S.
ζ=0 designates �1 error�. This is equivalent to ζ=0 and η=0, and error position is X1=S. S=0 designates �no error�. If η≠0, it designates that there are 4 errors or more.
Adder circuits 84 and 85 are for searching �y� based on y2+y=ζ/S corresponding 2ECr and then calculating the expression index of error position �n� based on the transformation of X=Sy. Inputs of the adder circuit 84 are ζ and S−3, and this input portion is for calculating the expression index of the syndrome part of the solution searching polynomial. Inputs of the adder circuit 85 is the result of the adder circuit 84, S and signal �1 error�, and this input portion decodes the index �i� of �y� satisfying y2+y=ζ/S3.
When 1 error, ζ/S3 becomes zero, i.e., there is no index of ζ/S3 to be output from the former adder circuit in spite of that there are �1� and zero as �y� satisfying y2+y=0. Therefore, signal �1 error� is directly received from gate 72, which is disposed at the syndrome calculation part, and index of �y� satisfying y2+y=0 is decoded. In this case, 1-error solution will be decoded.
Including this case, from decoded �i� and index σ1 of �S�, expression indexes of indexes �n�s corresponding to two errors are output as the calculation result. In case index �i� of �y� is not searched as a decode result at the input portion, 2EC system is not adaptable, so that signal �no solution 2EC� is generated. When this signal is generated, or S=0, there is not obtained solutions in 2EC-EW, so that gate 75 generates signal �not solved 2EC�.
Adder circuits 86, 87 and 88, corresponding to 3EC system, are for obtaining �w� and �w+1� based on w3+w=ζ5/η3, thereby calculating z1=(w+1)/w; searching β1=(Aw)1/2; and obtaining �z� based on z2+z=zj, thereby calculating the expression index of transformation of X=β1z, respectively.
The initial adder circuit 86 receives the expression index of wi=ζ5/η3 to decode �w� satisfying w3+w=w1, and calculates (w+1)/w to output �zj�. If there is no corresponding �w�, there is no solution. Therefore, signal �no solution w� is generated for designating that it is not solvable.
Adder circuit 88 calculates Aw based on two outputs �A� and �w�, and generates the power (Aw)1/2 as β1.
Adder circuit 87 searches �z� based on z2+z=zi corresponding two errors of 3EC, and calculates the expression index of the transformation of β1z. Input to the adder circuit 87 are the preceding result zi and the expression index of β1, and this input portion decodes the index �j� of �z� satisfying z2+z=zj. From the decoded results �j� and β1, the expression index corresponding to two errors will be output as the calculation result.
In case there is not searched the index �j� of �z� at the input portion, it designates that there is no solution, so that signal �no solution z� is generated.
In case there is not searched solution in accordance with the 3EC decoding method, and signal �no solution w� or �no solution z� is generated, or in case of η=0 in 3EC, it is not solvable in 3EC-EW, so that gate 79 generates signal �not solved 3EC�.
Parity checker circuits 46 and 47 calculate X=β1z+S and X1+S, respectively, and calculate the expression indexes of error positions �n� as the indexes of �X�.
Signal �non correctable� will be obtained through OR gate 74 when signal �no solution 2EC�, �solved 2EC� or �solved 3EC� is generated.
The information from 3EC is used when the condition of 2EC is not satisfied, and the coefficients of data polynomial ν(x) corresponding to error positions �n�s are inverted by XOR logic to be generated as corrected data �dn�. When signal �no error� or �non correctable� is generated, through signal �through� is generated, and data �dn� is output as it is.
Since finite field elements constituting the code of system are �h� excepting zero factor, coefficients of (h−1)-degree polynomial express data, Coefficient parts up to (4n−1)-degree are used as check bits of data. Information polynomial will be expressed in the following Expression 26.
f(x)x 4n =q(x)g(x)+r(x) r(x)=b 4n−1 x 4n−1 +b 4n−2 x 4n−2 + . . . +b 1 x+b 0 [Exp. 27]
The coefficients b4n−1�b0 of the remaining polynomial r(x) are used as check bits, which constitute data bits to be stored in the memory together with information bits ah−1�a4n.
v ⁡ ( x ) = ⁢ f ⁡ ( x ) ⁢ x 4 ⁢ n + r ⁡ ( x ) + e ⁡ ( x ) = ⁢ q ⁡ ( x ) ⁢ g ⁡ ( x ) + e ⁡ ( x ) [ Exp . ⁢ 28 ] Search error polynomial e(x) from read data, and error correction may be achieved.
ν(x)≡S1(x)mod m1(x)→e(x)≡S 1(x)mod m 1(x)ν(x)≡S3(x)mod m3(x)→e(x)≡S 3(x)mod m 3(x)ν(x)≡S5(x)mod m5(x)→e(x)≡S 5(x)mod m 5(x)ν(x)≡S7(x)mod m7(x)→e(x)≡S 7(x)mod m 7(x) [Exp. 29]
If errors are present at degrees �t�, �j�, �k� and �l�, e(x) is represented as follows: e(x)=xi+xj+xk+xl. Therefore, search degrees �i�, �j�, �k� and �l�, and error locations may be decided, i.e., which data is erroneous will be determined.
So, calculation is performed in GF(2n) with respect to the indexes of roots α of m1(x)=0 to search �i�, �j�, �k� and �l�. Assume that the remaining polynomial obtained by dividing xn by m1(x) is referred to pn(x), αn=pn(α). Therefore, unknown numbers X1, X2, X3 and X4, and syndromes S1, S3, S5 and S7 are defined as follows.
Note here that indexes of X1, X2, X3 and X4 are �i�, �j�, �k� and �l�, respectively, and indexes of S1, S3, S5 and S7 are σ1(=σ), σ3, σ5 and σ7, respectively.
Λ R ⁡ ( x ) = ⁢ ( x - X 1 ) ⁢ ( x - X 2 ) ⁢ ( x - X 3 ) ⁢ ( x - X 4 ) = ⁢ x 4 + Sx 3 + Dx 2 + Tx + Q = 0 ⁢ ⁢ S = S 1 = X 1 + X 2 + X 3 + X 4 ⁢ ⁢ D = X 1 ⁢ X 2 + X 2 ⁢ X 3 + X 3 ⁢ X 4 + X 4 ⁢ X 1 ⁢ ⁢ T = X 1 ⁢ X 2 ⁢ X 3 + X 2 ⁢ X 3 ⁢ X 4 + X 3 ⁢ X 4 ⁢ X 1 + X 4 ⁢ X 1 ⁢ X 2 ⁢ ⁢ Q = X 1 ⁢ X 2 ⁢ X 3 ⁢ X 4 [ Exp . ⁢ 32 ] There is a certain relationship between these coefficients and syndromes S1=S, S3, S5 and S7, which constitute simultaneous equations as shown in the following Expression 33.
SD+T=ζ (ζ+S 3)D+S 2 T+SQ=η (η+S 5)D+S 4 T+(ζ+S 3)Q=θ [Exp. 33]
�D�, �T� and �Q� may be obtained by solving the simultaneous equations. Note here that ζ=S3+S3, η=S5+S5 and θ=S7+S7 are set for the convenience of calculation.
To express �D�, �T� and �Q� with syndromes, the above-described simultaneous equations containing three variables may be solved with coefficient matrix of as shown in the following Expression 34.
=S3 ζ+Sη+ζ 2 D=S 3 η+S 2ζ2 +Sθ+ζη T=S 4 η+S 2θ+Θ3 Q=S 4ζ2 +S 2ζη+ζθ+η2 [Exp. 34]When ≠0, �D�, �T� and �Q� are decided, and go to the process of searching error of the search equation R(x)=0. If the equation has zero element or double root, branch to 3EC-EW.
In case of =0, one of unknowns, for examples �Q� is optionally set, and �D� and �T� may be solved. If just four errors are generated, there is not optional relationship between �S�, �D� and �T�. Therefore, this case designates that there are generated five or more errors, or three or less errors. In case of three or less errors, it is branched to 3EC-EW, and in case of five or more errors, it corresponds to the case of �not solved 3EC� in 3EC-EW.
x 4 +Sx 3 +Dx 2 +Tx+Q=0 [Exp. 35]Next, it will be examined the solution method of 4EC-EW, i.e., such a condition that the above-described biquadratic equation has just four and different solutions. Since a case including zero element or double root is out on the above-described condition, this case will be initially examined.
In this case, there is a certain relationship between coefficients �S�, �D�, �T� and �Q�. That is, B=S, a+c=D, ab=T and ac=Q, and a=T/S and c=SQ/T. From these, it is obtained D=a+c=T/S+SQ/T, so that it is obtained a relationship of: S2Q+SDT+T2=0. Therefore, in case of Q=0 or S2Q+SDT+T2=0, the solution method of 3EC-EW will be adapted.
The solution method of the biquadratic error searching equation will be explained below in accordance with some cases classified based on quantities determined by the syndromes. The following four cases, Case 1�Case 4, are defined, in each of which is not zero.
X 4 + SX 3 + ( b ⁢ / ⁢ S ) ⁢ X + B = ( X 2 + α 1 ⁢ X + α 0 ) ⁢ ( X 2 + β 1 ⁢ X + β 0 ) = 0 [ Exp . ⁢ 37 ] Based on the relationship between the coefficients of the factorized equations, α0, α1, β0 and β1, and the quantities derived from the syndromes, unknown quantity δ=α0+β0 is introduced, and the following cubic equation to be satisfied by δ will be obtained.
Since �b� is used as denominators in this equation, b≠0 is a necessary condition of this case.
Solve this cubic equation, and select one root �δ�, and two quadratic equations with unknown �ε�, which is to satisfy the coefficients of the factorized equations, will be obtained as follows.
(ε/δ)2+(ε/δ)+B/δ 2=0(ε/S)2+(ε/S)+δ/S 2=0 [Exp. 39]
Solve these equations, and coefficients (α0, β0) and (α1, β1) are obtained, respectively. Further, solve the following quadratic equations with these coefficients to obtain unknown �X�, and the solutions of the error searching biquadratic equation may be obtained based on X=x+a.
(X/α 1)2+(X/α 1)+α0/α1 2=0(X/β 1)2+(X/β 1)+β0/β1 2=0 [Exp. 40]
Note here that the unknown coefficients are transformed to be elements of GF(2) for the sake of using a table when the respective equations are solved. That is, the unknown variable is set to be δ1/b1/2 in the cubic equation for searching �δ�; the unknown variable is set to be δ/δ in the quadratic equations for searching α0 and β0; and the unknown variables are set to be X/α1 and X/β1 in the factorized quadratic equations.
Based on the relationships, α0β0=B, β1α0+α1β0=0, δ+α1β1=0 and α1+β1=S, between the coefficients of the factorized equations, α0, α1, β0 and β1, and the quantities derived from the syndromes, unknown quantity δ=α0+β0 is introduced, and the following cubic equation to be satisfied by �δ� will be obtained.
From this equation, δ=c1/3 is directly searched, and two quadratic equations with the unknown �δ�, which are the same as those in Expression 39, will be obtained. Solve these equations, and coefficients α0, α1, β0 and β1 are obtained.
Solve the factorized equations (shown in Expression 40) with the coefficients satisfying the above-described relationships, and unknown �X� is obtained, and the solution of the error searching biquadratic equation will be obtained based on X=x+a. Here, based on the above-described relationship, it is obtained α0/α1 2=δ/(S2u1) and β0/β1 2=δ/(S2u2).
�a� can not be defined because of S=0 while b=D2+SD=D2 and c=S2Q+SDT+T2=T2. Since c=0 is a condition of double root, it is c≠0 as far as 4EC solution is considered. ζ≠0 and η≠0 from D=ζη≠0, and =ζ2, D�η/ζ, T=ζ and Q=η2/ζ2+θ/ζ are obtained.
Based on the relationship between the coefficients α0, α1, β0 and β1, and the quantities derived from the syndromes, unknown quantity δ=α0+β0 is introduced, and the following cubic equation to be satisfied by �δ� will be obtained,
The condition of D≠0 in this Case 3 is necessary because �D� becomes the dominator of the cubic equation. This equation is cubic without 2-degree term, Solve this equation, and select one root (δ+D)/D, and two quadratic equations with unknowns �ε� will be obtained as follows.
(ε/δ)2+(ε/δ)+Q/δ 2=0ε2 +δ+D=0 [Exp. 45]
Solve the quadratic equations with the above-described coefficients as shown in the following Expression 46, error searching biquadratic equation with unknown �X� may be solved,
(X/α 1)2+(X/α 1)+α0/α1 2=0(X/β 1)2+(X/β 1)+β0/β1 2=0 [Exp. 46]
Based on the relationships, α0β0=Q, β1α0+α1β0=T, δ+α1β1=0 and α1+β1=0, between the coefficients of the factorized equations, α0, α1, β0 and β1, and the quantities derived from the syndromes, unknown quantity δ=α0+β0 is introduced, and the following cubic equation to be satisfied by �δ� will be obtained.
This is the same as Expression 42 in Case 2. This equation is easily searched, and δ=c1/3 is directly obtained. By use of �δ�, two quadratic equations with the unknown �ε� are obtained as shown in the following Expression 49.
(ε/δ)2+(ε/δ)+Q/δ 2=0ε2+δ=0 [Exp. 49]
Solve the quadratic equations with the above-described coefficients, which is the same as shown in the Expression 46, error searching biquadratic equation with unknown �X� may be solved.
One root �w� is decoded from the cubic equation of: w3+w=c/b3/2, and referred to as δ=b1/2w. Following it, roots u1, u2, v1 and v2 are decoded from the quadratic equations of: u2+u=B/δ2; and v2+v=δ/S2, and referred to as: α0=δu1; β0=δu2, α1=Sv1 and β1=Sv2.
Further, roots y1, y2, z1 and z2 are decoded from the quadratic equations of: y2+y�α0/α1 2; and z2+z=β0/β1 2, and finite field elements designating four error positions are obtained as follows: X1=α1y1+a; X2=α1y2+a; X3=β1z1+a and X4=β1z2+a.
Note here that quadratic equations with �u� and �v� are the same equations because of the relationship of B/δ2=δ/S2.
One root �w� is decoded from the cubic equation of: w3+wc/b3/2, and �w+1� is selected and referred to as δ=b1/2(w+1). Following it, roots u1 and u2 are decoded from the quadratic equations of u2+u=Q/δ2, and referred to as: α0=δu1; β0=δu2 and α1=β1=(b1/2w)1/2.
At the next Step 2, various quantities of product and quotient of the various powers based on the calculation results and �S� are calculated. Quantities necessary for calculating sums are four, i.e., S3ζ, Sη, S4η and S2θ.
Calculated in the following Step 5 are sum Q, product �D� and quotient �T� of the quantities obtained in the preceding step. Further in the Step 6, three quantities �Q�, �a� and �ST� are calculated here, which are necessary in the next step.
�b�, ζT, Ta and S2Q are calculated in the Step 7, and �c� and �B� are calculated in the final Step 8. To reduce the number of sums in the calculating step of �c�, the equation is transformed by use of the relationship of ζ=SD+T.
Based on the conditions of the respective error searching described above, the solution searching operations performed in parallel may be summarized as follows, Note here quantities, such as �S�, �η� and the like, which are obtained from the syndromes, are used in common to every error search. The coefficients, �T�, �T�, �Q� and the like, in the error searching equation, are individual quantities in the equation, and these are distinguished from each other by suffix numbers. For example, coefficient �D� will be referred to as �D2� in 2EC and �D3� in 3EC.
The error searching equation is a quadratic equation defined by x2+Sx+D2=0. There is a relationship between coefficient �D2� and syndrome �S� such as SD2=ζ. To satisfy that this equation has two roots different from each other, it becomes a condition that there is not zero element and double root. Therefore, S≠0 and D2≠0, and then η≠0. In this case, if no solution, it becomes three or more errors. When S0 or ζ=0, 1EC or less; when S≠0, η=0 and D2=0, 1 error of x+S=0 when D2=0; and when S=0, no error.
SD+T=ζ→SD+T=0(ζ+S 3)D+S 2 T+SQ=η→SQ=η (η+S 5)D+S 4 T+(ζ+S 3)Q=0→ηD+S 3 Q=η(S 2 +D)=θ =S 3 ζ+Sη+ζ 2 → =Sη c=S 2 Q+SDT+T 2 →c=S 2 Q= [Exp. 50]From cQ=0, SQ=0 is obtained, and =0 is satisfied. Further, if =0, and c=0, and then cQ=0 is satisfied. Therefore, only the case of =0 is to be considered. In this case, η=0 or S=0. From F=Sη, in case of S=0, θ=0 from η. Therefore, η=0 is always satisfied. On the other hand, from ζ=η=0 (θ=0), =0 and cQ=0 are satisfied. This is the condition of 1EC in the 4EC calculation.
Corresponded to that the error searching of 1EC or less results in �no solution� is the case where contradiction is generated under the branching condition. That is, if η=0 and θ≠0, and it is contradictory. If S=0 and η≠0, it is judged to be contradictory based on the relationship between the syndromes and the coefficients. In this case, it is judged that there are 5 errors or more.
SD 3 +T 3 −ζ→SD 3=ζ(ζ+S 3)D 3 +S 2 T 3=η→ζ(S 2 +D 3)=η =S 3 ζ+Sη+ζ 2→ =0 [Exp. 51]Since =0, i.e., the condition of 2EC in 4EC is always satisfied, there is no need of considering cQ=0. Therefore, the condition of branching to 2EC is: =0 and ζ≠0.
FIG. 8 shows the configuration of the 4EC-EW-BCH system, which is able to correct errors up to 4 bits, and outputs a warning when there are 5 or more errors. In the encode part 20 a, necessary degrees are selected and the corresponding coefficients are used in accordance with data bit configuration. Therefore, unnecessary coefficients are dealt with fixed data �0� or �1�, which are not stored in the memory core 10. As a result, the system may be constituted to be adapted to the memory capacitance.
The degrees used as the information bits are selected to be able to minimize the calculation scale and system scale. In general, supposing that information data are defined by �ai�, input is expressed by h−1−4n degree polynomial f(x) with the coefficients of �ai�. When f(x) x4n is divided by code generation polynomial g(x) and remainder r(x) is obtained, coefficients of polynomial f(x) x4n+r(x) are dealt with data bits to be stored in the memory core 10.
Syndrome operation part 30 a is for dividing ν (x) by m1(x), m3(x), m5(x) and m7(x) to search syndromes S, S3, S5 and S7, respectively. Syndromes are represented by �expression indexes� which are distinguished from each other by mod p, mod q and mod r (where, h=pqr).
FIG. 9 shows the internal clocks generated from the clock generation circuit 300. �CL� is a basic clock used for controlling the memory and data transferring. This clock has several 10 naec cycle time and is synchronized with the control clock prepared outside the memory. This clock CL is used as a trigger, and internal clocks ck1-ck16 are generated. The explanation of the method of clock generation is omitted here. For example, the method of clock generating disclosed in JP-A-2005-332497 may be useful.
The respective steps are operated with clocks ck1-ck8. These steps are ones for calculating the finite field elements from syndromes as shown in FIG. 6. That is, the numbers of these steps 1 to 8 correspond to those of clocks ck1-ck8. Note here that in case one input of four-input parity checker is not used, �0�, i.e., Vss, is applied to it.
The solution method of 4EC system will be explained first. CUBE 103 is formed of: one adder circuit 111 used for calculating quantity �H�, to which the unknown part of the cubic equation for �w� is equivalent, from the syndrome; decoder calculation circuit 112 used for searching �w� from the cubic equation of w3+w=H; and another adder circuit 113 used for calculating quantity �δ� to be obtained from �w� as the product of �w� or �w+1� and �b1/2�.
SQUARE 104 has; two adder circuits 121 and 122 used for calculating the quantities �J� and �K� to be obtained from �δ�, to which the unknown parts of the quadratic equations for �u� and �v� are equivalent; decoder calculation circuits 123 and 124 used for searching �u� and �v� from two quadratic equations of u2+u=J and v2+v=K, respectively; and four adder circuits 125-128 used for calculating the coefficients �α0�, β0�, �α1� and �β1�, respectively, of the factorization to quadratic equations from the biquadratic equation.
SQUARE 104 further has parenthesized circuit portions, in which adder circuits 121 and 122, decoder calculation circuits 123 and 124, and adder circuits 125-128 are multiplexed to be used as the latter half calculation portion. That is, SQUARE 104 further has: two adder circuits 121 a and 122 a used for calculating the quantities �L� and �M�, to which the unknown parts of the quadratic equations for �y� and �z� (to be searched for obtaining the roots of the error searching biquadratic equation) are equivalent; decoder calculation circuits 123 a and 124 a used for searching �y� and �z� from two quadratic equations of y2+y=L and z2+Z=M, respectively; four adder circuits 125 a-128 a used for calculating the biquadratic equation based on �y� and �z�.
The former half calculation portions and the latter halt calculation portions in SQUARE 104 are distinguished from each other with suffix �a� and without suffix, and it is shown that these circuits are common ones used in time-sharing. To hold the result of the former half calculation portions, there is prepared the register portion 100, in which �α1� and �β1� are stored.
The calculation results of SQUARE 104 are added to the quantities obtained from the syndrome, respectively, to serve as the true error-searching results. To calculate these sums, there are four parity checker circuits 105-108 each with two inputs. To hold the results �X1�, �X2�, �X3� and �X4�, there is prepared the register portion 102.
CUBE 103 calculates H=cb−3/2 in adder circuit AD1 with clock ck9, search �w� from w3+w=H in decoder calculation circuit 112 and calculates δWb1/2 in adder circuit AD4 with clock ck10.
SQUARE 104 calculates J=Bδ−2 and K=δS−2 in adder circuits AD1 and AD4, respectively, with clock ck11. Further, �u� and �v� are decoded from u2+u=J and v2+v=K in calculating circuits 123 and 124, respectively, with clock ck12, and α0=δu1, β0=δu2, α1=Sv1 and β1=Sv2 are calculated in adder circuits AD1-AD4, respectively.
SQUARE 104 calculates J=Bδ−2 in adder circuit AD1 and K=δS−2 in adder circuit AD4 with clock ck9. Further, �u� and �v� are decoded as �u1 and u2� and �v1 and v2� from u2+u=J and v2+v=K in calculating circuits 123 and 124, respectively, with clock ck10, and α0δu1, β0δu2, α1=Sv1 and β1Sv2 are calculated in adder circuits AD1-AD4, respectively.
CUBE 103 calculates H=cb−3/2 in adder circuit AD1 with clock ck9, searches �w� and �w+1� from w3+w=H in decoder calculation circuit 112 with clock ck10 and calculates δ=(w+1)b1/2 in adder circuit AD4.
SQUARE 104 calculates J=Qδ−2 in adder circuit AD1 with clock ck11, calculates �u1� and �u2� from u2+u=J in decoder calculating circuit 123 with clock ck12, and calculates α0=δu1, β0=δu2 and α1 2=β12=wb1/2 in adder circuits AD1, AD2 and AD4, respectively.
At the output portion of SQUARE 104, parity checker circuits PC1 to PC4 calculate X1=a+α1y1, X2=a+α1y2, X3=a+β1z1 and X4=a+β1z2 with a=�0� with clock ck15, and the calculated results will be stored in register 102 with clock ck16′. Although the calculating step of clock ck15 is not necessary in principle, it is used here with a=�0� for keeping the procedure as unchangeable as possible.
SQUARE 104 calculates J=Qδ−2 in adder circuit AD1 with clock ck9, calculates �u1� and �u2� from u2+u=J in decode calculating circuit 123 with clock ck10, and calculates α0=δu1 and β0=δu2 in adder circuits An1 and AD2, respectively. Further, α1 2=β1 2=δ is set.
At the output portion of SQUARE 104, parity checker circuits PC1 to PC4 calculate X1=a+α1y1, X2=a+α1y2, X3=a+β1z1 and X4=a+β1z2 with a=�0� with clock ck13, and the calculated results will be stored in register 102 with clock ck14′.
CUBE 103 calculates H=ζ5η−3 and A=ηζ−1 in adder circuits AD1 and AD3, respectively, with clock ck9, calculates �w� and �w+1� from w3+w=H in decoder calculation circuit 112 with clock ck10 and calculates α2=β1 2=wA in adder circuit AD4.
SQUARE 104 calculates K=ζS−3 in adder circuit AD4 with clock ck9, calculates �v1� and �v2� from v2+v=K in decoder calculating circuit 124 with clock ck10 and calculates X1=Sv1 and X2=Sv2 in adder circuits AD3 and AD4, respectively.
FIG. 19 shows the procedure in case of 1EC or less. ζ=0, η=0 and θ=0 because of 1EC or less. ES part 100 is not used, and the calculation procedure will be finished at SEC part 90. X1=S is stored in register 102 with clock ck3′. If S=0, it becomes �no error�.
It is the expression index that it becomes possible in appearance to effectively decrease the index number in one-to-one correspondence to the finite field element. For example, consider the finite field GF(2n). Domain of index thereof is: h=2n−1. When the domain �h� is factorized into primes p1, p2, . . . , pi (h), the expression equivalent to the finite element αm corresponding to the index �m� will be obtained as follows:
α m ⇔ ⁢ m ⁡ ( mod ⁢ ⁢ h ) ⇔ ⁢ { m ⁡ ( mod ⁢ ⁢ p ⁢ ⁢ 1 ) , m ⁡ ( mod ⁢ ⁢ p ⁢ ⁢ 2 ) , � ⁢ , m ( mod ⁢ ⁢ pi ⁡ ( h ) } [ Exp . ⁢ 52 ] This is for expressing the index as the domain components obtained by factorizing the domain, and is referred to as �expression index� in correspondence to the �index�. By use of this expression index, the domain is made to be small in appearance. That is, the domain number of the index is �h� (from 0 to h−1) while that of the expression index is �pi(h)� (from 0 to pi(h)−1) defined by the maximum prime pi(h).
αi�αj=αi+j {i(p1),i(p2), . . . ,i(pi(h))}{j(p1),(p2), . . . ,j(pi(h))}={i+j(p1),i+j(p2), . . . ,i+j(pi(h))} [Exp. 53]Therefore, the product of the finite field elements becomes the sum of index components with modulo of the factorized primes. That is, the bit number of domain Chit is �n�, and the addition thereof is reduced in scale into the parallel addition operations of log2 pi(h) bits,
Next, some practical cases of �n� will be compared below.
4EC Check Bit Number: Check bit number �4n� of 4EC system is shown here because the system scales are compared with each other in consideration of that: 4-bit dealt in the 4EC system formed as the on-chip decode scheme is considered as the maximum error correction number with a high speed BCH processing.
Memory Redundancy Rate: In correspondence to the information bit number 2n−1 effective as the memory data, check bit number is set to be �4n�. Therefore, the memory redundancy rate is 4n/2n−1.
h=2n−1 Factorization; the primes of domain �h� of the index are shown here.
That is, if there are the following relationships of: F(w)=w3+w, F(w)=w2+w and F(w)=w with respect to finite field element �w�, decoders are formed by grouping F(w) with respect to the respective expression index components of �w�, and the expression index component of �w� in the group is selected for the expression index components of H=F(w).
FIG. 21 shows the summary of three kinds of decoder schemes with the expression index components mod 3, mod 11 and mod 31. α*, β* and γ* represent the groups of F(w) of mod 3=α, mod 11=β and mod 31=γ, respectively. For example, F(w)=w3+w is used as the decoder of searching a cubic searching equation; F(w)=w2+w is for searching a quadratic equation; and F(w)=w is for converting the polynomial expression of �w�.
{α,β}(=F(w):w mod 3=α and w mod 11=β)=α* β*α*={α,0} {α,1} {α,2} {α,3} . . . {α,9} {α,10}β*={0,β} {1,β} {2,β} [Exp. 54]That is, take OR logic between the decoder circuit element and the output for {α,β}, α and β will be obtained.
For example, elements of GF(210) are obtained as the remainder of the irreducible polynomial x10+x3+1 on GF(2). The element that the index is �n� is the remainder polynomial obtained by dividing xn, which is represented as follows by combinations of coefficients: xn=pn(x)=Pn 9x9+Pn θx8+Pn 7x7++Pn 2x2+Pn 1x+Pn 0.
To transform this coefficient expression to expression index, as shown in FIG. 23, the coefficients are classified into three groups of four-bit, four-bit and two-bit, and each four-bit or two-bit binary is converted to hexadecimal numbers. That is, A0�A15, B0�B15 and C0�C3 are obtained in order from the lower coefficient side of the polynomial.
FIG. 24 shows a pre-decode circuit for obtaining A0�A15 from the lowest 4-bit binary. Since the finite field is represented by the combination of Ai, Bi and Ci, decoder circuit {α,β} or γ is represented as an OR logic of NAND of Ai, Bi and Ci, as shown in FIG. 25. This decoder operates as follows: when clock CLK is raised, if the polynomial expression of Ai, Bi and Ci belonging to {α, β} or γ is in this decoder, node ND is discharged and this raises the output.
If composing the result of the expression index decoder with OR logics as shown in FIG. 26, the expression index components α and β are obtained. As a result, the polynomial expression of xα=(Pσ 9, Pσ 8, Pσ 7, . . . , Pσ 2, Pσ 1, Pσ 0) of the finite field element xσ may be converted to the �expression index� expression.
Passed on the data bus between adders are expression index components. Therefore, in case time-sharing is used with clocks �ckm� and �ckn�, adder input multiplexer 400 is necessary at the input portion. That is, in case α is input with clock �ckm�, and β is input with clock �ckn�, the input expression index components are multiplexed in the multiplexer 400 formed of clocked inverters to be input index �i�.
Converting is performed in such a manner that nodes ND0, ND1, . . . , ND3/4 are charged up while clocks �ckm� and �ckn� are not activated, and these are discharged in accordance with the component indexes �i�s, so that binary-expressed �i�s will be obtained. Binary expressions are defined by node levels of 2-bit (0, 1), 4-bit (0, 1, 2, 3), and 5-bit (0, 1, 2, 3, 4) corresponding to the expression index components i(3), i(11) and i(31), respectively, and the node levels are held in latches during the clock pulse time.
The circuit functions with clocks �ckm+1� and �ckn+1�, which are one-clock delayed to �ckm� and �ckn�, respectively. The decoder output is latched with clocks �ckm+1� and �ckn+1� during the ECC cycle, and serves to be usable in the successive clock cycles. A part of the output latches 404 serves as the register portion 91 and the like, which has been specifically explained in the SEC part in the ECC circuit block.
A power of element becomes a multiple of expression index. As shown in FIG. 40, the component indexes of the expression index {(31), i(11), i(3)} are multiplied by �m�, and new components are obtained as shown under x(m) columns. Combining these transformations, required expression indexes will be obtained.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS3418629 *Apr 10, 1964Dec 24, 1968IbmDecoders for cyclic error-correcting codesUS4058851 *Oct 18, 1976Nov 15, 1977Sperry Rand CorporationConditional bypass of error correction for dual memory access time selectionUS4099160 *Jul 15, 1976Jul 4, 1978International Business Machines CorporationError location apparatus and methodsUS4142174 *Aug 15, 1977Feb 27, 1979International Business Machines CorporationHigh speed decoding of Reed-Solomon codesUS4498175 *Sep 30, 1982Feb 5, 1985Tokyo Shibaura Denki Kabushiki KaishaError correcting systemUS4509172 *Sep 28, 1982Apr 2, 1985International Business Machines CorporationDouble error correction - triple error detection codeUS4567568 *Mar 10, 1983Jan 28, 1986Tokyo Shibaura Denki Kabushiki KaishaApparatus for dividing the elements of a Galois fieldUS4567594 *Jun 7, 1983Jan 28, 1986Burroughs CorporationIn a disk storage systemUS4574361 *Mar 10, 1983Mar 4, 1986Tokyo Shibaura Denki Kabushiki KaishaApparatus for dividing the elements of a Galois fieldUS4604655 *Oct 21, 1983Aug 5, 1986Pioneer Electronic CorporationMethod of recording and reproducing video format signalUS4608692 *Sep 6, 1984Aug 26, 1986Kabushiki Kaisha ToshibaError correction circuitUS4677622 *Jun 20, 1984Jun 30, 1987Hitachi, Ltd.Error correction method and systemUS4782490 *Mar 16, 1987Nov 1, 1988Cythera CorporationMethod and a system for multiple error detection and correctionUS4841300 *Jun 17, 1987Jun 20, 1989Mitsubishi Denki K.K.Error correction encoder/decoderUS4958349 *Nov 1, 1988Sep 18, 1990Ford Aerospace CorporationApparatus for decoding in linear error correcting codeUS5040179 *Aug 18, 1989Aug 13, 1991Loral Aerospace Corp.High data rate BCH encoderUS5155734 *Feb 9, 1990Oct 13, 1992Canon Kabushiki KaishaError correcting deviceUS5459740 *Nov 23, 1992Oct 17, 1995International Business Machines CorporationMethod and apparatus for implementing a triple error detection and double error correction codeUS5537429 *Feb 5, 1993Jul 16, 1996Mitsubishi Denki Kabushiki KaishaError-correcting method and decoder using the sameUS5710782 *Dec 28, 1995Jan 20, 1998Quantum CorporationSystem for correction of three and four errorsUS5761102 *Dec 28, 1995Jun 2, 1998Quantum CorporationSystem and method for determining the cube root of an element of a galois field GF(2)US5771246 *Sep 17, 1996Jun 23, 1998Quantum CorporationMultiple-burst-correction systemUS5887005 *Jun 26, 1997Mar 23, 1999Integrated Device Technology, Inc.Methods and apparatus for error correctionUS5889793 *Jun 27, 1997Mar 30, 1999Integrated Device Technology, Inc.Methods and apparatus for error correctionUS5974583 *Oct 17, 1997Oct 26, 1999Samsung Electronics Co., Ltd.Error correcting method and deviceUS5978956 *Dec 3, 1997Nov 2, 1999Quantum CorporationFive-error correction systemUS6185134Dec 8, 1999Feb 6, 2001Kabushiki Kaisha ToshibaFlash memory control method, flash memory system using the control method and flash memory device using the control methodUS6199188 *Mar 8, 2000Mar 6, 2001Quantum CorporationSystem for finding roots of degree three and degree four error locator polynomials over GF(2M)US6272659 *May 18, 1998Aug 7, 2001Cirrus Logic, Inc.Error correction code processor employing adjustable correction power for miscorrection minimizationUS6286123 *Aug 12, 1998Sep 4, 2001Samsung Electronics Co., Ltd.Circuit for calculating error position polynomial at high speedUS6343367 *Mar 29, 1999Jan 29, 2002Maxtor CorporationError correction system for five or more errorsUS6360348 *Aug 27, 1999Mar 19, 2002Motorola, Inc.Method and apparatus for coding and decoding dataUS6374383 *Jun 7, 1999Apr 16, 2002Maxtor CorporationDetermining error locations using error correction codesUS6560747 *Nov 10, 1999May 6, 2003Maxtor CorporationError counting mechanismUS6643819 *Jan 26, 2000Nov 4, 2003Maxtor CorporationHybrid root-finding techniqueUS6651212Aug 31, 2000Nov 18, 2003Hitachi, Ltd.Recording/reproduction device, semiconductor memory, and memory card using the semiconductor memoryUS6651214 *Jan 6, 2000Nov 18, 2003Maxtor CorporationBi-directional decodable Reed-Solomon codesUS6928601 *Mar 6, 2002Aug 9, 2005International Business Machines CorporationDecoding circuit, and decoder, decoding method and semiconductor device that use the decoding circuitUS7010738 *Mar 6, 2002Mar 7, 2006International Business Machines CorporationCombinational circuit, and encoder, decoder and semiconductor device using this combinational circuitUS7076722 *Nov 12, 2002Jul 11, 2006Kabushiki Kaisa ToshibaSemiconductor memory deviceUS7228467 *Oct 17, 2003Jun 5, 2007Quantum CorporationCorrecting data having more data blocks with errors than redundancy blocksUS20030028842 *Mar 6, 2002Feb 6, 2003International Business MachinesDecoding circuit, and decoder, decoding method and semiconductor device that use the decoding circuitUS20030101405 *Nov 12, 2002May 29, 2003Noboru ShibataSemiconductor memory deviceUS20070198902Jan 19, 2007Aug 23, 2007Kabushiki Kaisha ToshibaSemiconductor memory deviceUS20070220400Feb 13, 2007Sep 20, 2007Kabushiki Kaisha ToshibaSemiconductor memory deviceUS20070266291 *Mar 27, 2007Nov 15, 2007Kabushiki Kaisha ToshibaSemiconductor memory deviceUS20080082901Aug 28, 2007Apr 3, 2008Kabushiki Kaisha ToshibaSemiconductor memory deviceUS20090049366Aug 12, 2008Feb 19, 2009Kabushiki Kaisha ToshibaMemory device with error correction systemUS20100036901 *Aug 6, 2008Feb 11, 2010Sun Microsystems, Inc.Modulus-based error-checking techniqueUSRE40252Jan 20, 2005Apr 22, 2008Kabushiki Kaisha ToshibaFlash memory control method, flash memory system using the control method and flash memory device using the control methodJP2000173289A Title not availableWO2008099723A1Jan 30, 2008Aug 21, 2008Toshiba KkSemiconductor memory with reed- solomon decoder* Cited by examinerNon-Patent CitationsReference1U.S. Appl. No. 12,524,880, filed Jul. 29, 2009, Haruki Toda.Referenced byCiting PatentFiling datePublication dateApplicantTitleUS8291303 *Aug 12, 2008Oct 16, 2012Kabushiki Kaisha ToshibaMemory device with error correction system for detection and correction errors in read out dataUS20090049366 *Aug 12, 2008Feb 19, 2009Kabushiki Kaisha ToshibaMemory device with error correction system* Cited by examinerClassifications U.S. Classification714/781, 714/784, 714/785International ClassificationH03M13/00Cooperative ClassificationH03M13/1575, G06F11/1068, H03M13/3715, H03M13/152European ClassificationG06F11/10M8, H03M13/37A1, H03M13/15P2, H03M13/15P13Legal EventsDateCodeEventDescriptionSep 9, 2009ASAssignmentOwner name: KABUSHIKI KAISHA TOSHIBA,JAPANFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:TODA, HARUKI;US-ASSIGNMENT DATABASE UPDATED:20100513;REEL/FRAME:23209/708Effective date: 20090831Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:TODA, HARUKI;REEL/FRAME:023209/0708Owner name: KABUSHIKI KAISHA TOSHIBA, JAPANRotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google