Error correction method and apparatus for disk drive emulator

• US 5,668,976 A
• Filed: 10/21/1994
• Issued: 09/16/1997
• Est. Priority Date: 11/04/1993
• Status: Expired due to Term

• Current Assignee: Cirrus Logic Incorporated
• Original Assignee: Cirrus Logic Incorporated
• Inventors: Zook, Christopher P.
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): Fiul, Dan
• Application Number:
  US08/327,681
• Time in Patent Office: 1,061 Days
• Field of Search: 395/182.04, 395/500, 395/430, 371/41, 371/40.1, 371/30, 371/40.2, 371/40.4, 365/218, 364/578
• US Class Current: 703/24
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• CPC Class Codes: G06F 11/1004 to protect a block of data words, e.g. CRC or checksum G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence
• CPC Class Codes: G06F 7/726 Inversion; Reciprocal calculation; Division of elements of a finite field
• CPC Class Codes: H03M 13/00 Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes error detection or error correction for analogue/digital, digital/analogue or code conversion H03M1/00 – H03M11/00; specially adapted for digital computers G06F11/08; for information storage based on relative movement between record carrier and transducer G11B, e.g. G11B20/18; for static stores G11C
• CPC Class Codes: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence
• CPC Class Codes: H03M 13/35 Unequal or adaptive error protection, e.g. by providing a different level of protection according to significance of source information or by adapting the coding according to the change of transmission channel characteristics

Abstract

An error correction system (10) is provided for correcting up to two bits per sector stored in a solid state non-volatile memory (12) which emulates a disk drive. The error correction system (10) includes an ECC/remainder generator (100), a bank of remainder registers (102), and a calculation circuit (104), all under supervision of a controller (106). During a write-to-memory operation, error correction system (10) generates ECC bytes for storage in the memory (12). In a write operation, an entire sector acquired from memory (12) is used to generate ECC check remainder bytes REM₀ -REM₃. The check remainder bytes REM₀ -REM₃ are utilized to generates syndromes S₁, S₃ and a factor S_B, the syndromes in turn being used to obtain either one or two error location positions (α^L1, α^L2). The mathematical calculation circuit (104) not only generates the syndromes S₁, S₃ and factor S_B, as well as the error location positions (α^L1, α^L2), but also generates the addresses of the bit errors in the sector (L1-64 [complemented], L2-64[complemented].

Claims

1. An error correction system for a solid state disk drive which emulates the operation of a magnetic disk drive, the error correction system comprising:

an ECC/remainder generator which sequentially receives bytes of a sector and generates ECC bytes in a write operation and check remainder bytes in a read operation;

a bank of remainder registers which are loaded with the check remainder bytes;

a calculation circuit which serially receives contents of the bank of remainder registers for generating two syndromes.

2. The error correction system of claim 1, wherein the bank of remainder registers are parallel loaded with the check remainder bytes.

3. The error correction system of claim 2, wherein the bank of remainder registers comprises a plurality of multibit registers which are parallel loaded with the check remainder bytes, wherein the four multibit registers are connected to operate as a serial shift register, and wherein subsequent to generation of the two syndromes, the two syndromes are serially loaded into predetermined bits of the serial shift register.

4. The error correction system of claim 1, wherein the calculation circuit serially receives contents of the bank of remainder registers for generating the two syndromes and a range check factor.

5. The error correction system of claim 4, wherein the error correction system uses a 32 bit code generator polynomial which is the product of two 14-bit polynomials and a 4-bit polynomial, and wherein the 4-bit polynomial is used to generate the range check factor.

6. The error correction system of claim 4, wherein the calculation circuit uses the range check factor to verify validity of corrections performed by the error correction system.

7. The error correction system of claim 1, wherein the error correction system uses a 32 bit code generator polynomial which is the product of two 14-bit polynomials and a 4-bit polynomial.

8. The error correction system of claim 7, wherein a first of the two 14-bit polynomials is the polynomial (x¹⁴ +x¹⁰ +x⁹ +x⁶ +x⁵ +x⁴ +1), wherein a second of the two 14-bit polynomials is the polynomial (X¹⁴ +X⁶ +X⁵ +X² +1), and wherein the 4-bit polynomial is the polynomial (x⁴ +1).

9. The error correction system of claim 1, wherein the calculation circuit comprises a first bank of calculation registers and a second bank of calculation registers, and wherein the first bank of calculation registers and the second bank of calculation registers has a feedback circuit, and wherein the contents of the bank of remainder registers is serially shifted into each of the first bank of calculation registers and the second bank of calculation registers for generating a first syndrome in the first bank of calculation registers and a second syndrome in the second bank of calculation registers.

10. The error correction system of claim 9, wherein the calculation circuit evaluates an expression ##EQU4## wherein S₁ is the first syndrome, S₃ is the second syndrome, and α

⁰ is 1, and wherein the calculation circuit uses the evaluation of C to determine a number of errors in the sector.

11. The error correction system of claim 10, wherein the calculation circuit evaluates a trace function of C to determine if the sector is uncorrectable.

12. The error correction system of claim 9, wherein the calculation circuit uses the first syndrome to determine at least a first error locator value.

13. The error correction system of claim 12, wherein the calculation circuit determines the first error locator value α

^L1 using the formula α

^L1 =S₁ y, wherein S₁ is the first syndrome and y is found such that y² +y+C=0 by taking a linear combination

space="preserve" listing-type="equation">y.sub.k =Σ

.sub.j a.sub.k,j C.sub.j

and wherein values for a_k,j are stored in a linear look-up table included in the calculation circuit.

14. The error correction system of claim 13, wherein the calculation circuit determines a second error locator value α

^L2 using the formula α

^L2 =S₁ +α

^L1.

15. The error correction system of claim 12, wherein the calculation circuit comprises a third bank of calculation registers, and wherein the contents of the bank of remainder registers is serially shifted into the third bank of calculation registers for generating the range check factor in the third bank of calculation registers.

16. The error correction system of claim 15, wherein the calculation circuit uses the at least one error locator value to determine whether an error bit is in a data portion of the sector.

17. The error correction system of claim 12, wherein the calculation circuit takes the log of the at least one error locator value to determine an error address.

18. The error correction system of claim 17, wherein the calculation circuit loads the at least one error locator value into the first bank of calculation registers, and wherein the calculation circuit includes:

means for generating a sequence of values;

a linear combination circuit for linearly combining a first set of the sequence of values with the at least one error locator in order to generate a linear combination x₁ in the second bank of calculation registers, wherein a number of bits contained in x₁ is half a number of bits contained in the error locator;

a look-up table stored in a memory which determines log(x₁);

wherein a second set of the sequence of values is linearly combined using the linear combination circuit to generate a linear combination x₀, wherein a number of bits contained in x₀ is half the number of bits contained in the error locator; and

wherein the look-up table determines log(x₀).

19. An error correction method for a solid state disk drive which emulates the operation of a magnetic disk drive, the error correction method comprising:

sequentially receiving bytes of a sector and generating ECC bytes in a write operation and check remainder bytes in a read operation;

loading a bank of remainder registers with the check remainder bytes;

serially inputting contents of the bank of remainder registers into a calculation circuit and using the calculation circuit to generate two syndromes in the read operation.

20. The error correction method of claim 19, wherein the bank of remainder registers are parallel loaded with the check remainder bytes.

21. The error correction method of claim 20 wherein the bank of remainder register comprises a plurality of multibit register which are parallel loaded with the check remainder bytes, and wherein the method further comprises:

operating the plurality of multibit registers as a serial shift register for shifting the contents thereof into the calculation circuit; and

subsequent to generation of the two syndromes, serially loading the two syndromes into predetermined bits of the serial shift register.

22. The error correction method of claim 19, further comprising:

serially inputting contents of the bank of remainder registers into the calculation circuit; and

using the calculation circuit to generate the two syndromes and a range check factor.

23. The error correction method of claim 22, wherein the error correction method uses a 32 bit code generator polynomial which is the product of two 14-bit polynomials and a 4-bit polynomial, and wherein the 4-bit polynomial is used to generate the range check factor.

24. The error correction method of claim 22, further comprising using the at least one error locator value to determine whether an error bit is in a data portion of the sector.

25. The error correction method of claim 19, wherein the error correction method uses a 32 bit code generator polynomial which is the product of two 14-bit polynomials and a 4-bit polynomial.

26. The error correction method of claim 25, wherein a first of the two 14bit polynomials is the polynomial (x¹⁴ +x¹⁰ +x⁹ +x⁶ +x⁵ +x⁴ +1), wherein a second of the two 14-bit polynomials is the polynomial (x¹⁴ +x⁶ +x⁵ +x² +1), and wherein the 4-bit polynomial is the polynomial (x⁴ +1).

27. The error correction method of claim 19, further comprising:

serially shifting the contents of the bank of remainder registers into each of a first bank of calculation registers and a second bank of calculation registers comprising the calculation circuit; and

generating a first syndrome in the first bank of calculation registers and a second syndrome in the second bank of calculation registers.

28. The error correction method of claim 27, further comprising using the calculation circuit to evaluate an expression ##EQU5## wherein S₁ is the first syndrome, S₃ is the second syndrome, and α

⁰ is 1; and

using the calculation circuit to evaluate C to determine a number of errors in the sector.

29. The error correction method of claim 28, further comprising using the calculation circuit to evaluate a trace function of C to determine if the sector is uncorrectable.

30. The error correction method of claim 27, further comprising using the calculation circuit to determine at least a first error locator value using the first syndrome.

31. The error correction method of claim 30, wherein the calculation circuit determines the first error locator value α

^L1 using the formula α

^L1 =S₁ y, wherein S₁ is the first syndrome and y is found such the Y² +y+C=0 by taking a linear combination

space="preserve" listing-type="equation">y.sub.k =Σ

.sub.j a.sub.k,j c.sub.j

and wherein values for a_k,j are obtained from a linear look-up table included in the calculation circuit.

32. The error correction method of claim 31, further comprising using the calculation circuit to determine a second error locator value α

^L2 using the formula α

^L2 =S₁ +α

^L1.

33. The error correction method of claim 30, further comprising serially shifting the contents of the bank of remainder registers into the third bank of calculation registers included in the calculation circuit for generating the range check factor in the third bank of calculation registers.

34. The error correction method of claim 33, further comprising operating the calculation circuit to use the at least one error locator value to determine whether an error bit is in a data portion of the sector.

35. The error correction method of claim 30, further comprising operating the calculation circuit to take the log of the at least one error locator value and thereby determine an error address.

36. The error correction method of claim 35, wherein operating the calculation circuit to take the log of the at least one error locator value comprises:

loading the at least one error locator value into the first bank of calculation registers,

generating a sequence of values;

linearly combining a first set of the sequence of values with the at least one error locator in order to generate a linear combination x₁ in the second bank of calculation registers, wherein a number of bits contained in x₁ is half a number of bits contained in the error locator;

accessing a look-up table stored in a memory to determine log(x₁);

linearly combined a second set of the sequence of values with the at least one error locator in order to generate a linear combination x₀, wherein a number of bits contained in x_o is half a number of bits contained in the error locator; and

accessing the look-up table to determine log(x₀).

37. The error correction method of claim 19, wherein the calculation circuit is used to:

serially receive the contents of the bank of remainder registers into each of a first bank of calculation registers and a second bank of calculation registers comprising the calculation circuit and to generate a first syndrome in the first bank of calculation registers and a second syndrome in the second bank of calculation registers;

serially receive the contents of the bank of remainder registers into a third bank of calculation registers and to generate a range check factor;

determine if the sector is uncorrectable

determine a number of errors in the sector;

determine a first error locator value using the first syndrome;

determine a second error locator value;

taking the log of the first error locator value and the second error locator value and thereby determine error addresses in the sector.

38. The error correction method of claim 37, wherein the number of errors in the sector is determined by evaluating an expression ##EQU6## wherein S₁ is the first syndrome, S₃ is the second syndrome, and α

⁰ is 1.

39. The error correction method of claim 37, wherein the calculation circuit determines the first error locator value α

^L1 using the formula α

^L1 =S₁ y, wherein S₁ is the first syndrome and y is found such that y² +y+C=0 by taking a linear combination

space="preserve" listing-type="equation">y.sub.k =Σ

.sub.j a.sub.k,j c.sub.j

and wherein values for a_k,j are obtained from a linear look-up table included in the calculation circuit.

40. The error correction method of claim 37, wherein the calculation circuit determines the second error locator value α

^L2 using the formula α

^L2 =S₁ +α

^L1.

41. The error correction method of claim 37, wherein taking the log of the at least one error locator value comprises:

loading the at least one error locator value into the first bank of calculation registers,

generating a sequence of values;

linearly combining a first set of the sequence of values with the at least one error locator in order to generate a linear combination x₁ in the second bank of calculation registers, wherein a number of bits contained in x₁ is half a number of bits contained in the error locator;

accessing a look-up table stored in a memory to determine log(x₁);

linearly combined a second set of the sequence of values with the at least one error locator in order to generate a linear combination x₀, wherein a number of bits contained in x₁ is half a number of bits contained in the error locator; and

accessing the look-up table to determine log(x₀).

42. An error correction system for a solid state disk drive which emulates the operation of a magnetic disk drive, the error correction system correcting as many as two errors per sector applied to the system by the solid state disk drive by using a 32 bit code generator polynomial, the 32 bit code generator polynomial being the product of two 14-bit polynomials and a 4-bit polynomial, and wherein the 4-bit polynomial is used to generate a range check factor for determining whether error(s) occurred in a data portion of the sector.

43. The error correction system of claim 42, wherein a first of the two 14-bit polynomials is the polynomial (x¹⁴ +x¹⁰ +x⁹ +x⁶ +x⁵ +x⁴ +1), wherein a second of the two 14-bit polynomials is the polynomial (X¹⁴ +X⁶ +X⁵ +X² +1), and wherein the 4-bit polynomial is the polynomial (x⁴ +1).

44. The error correction system of claim 42, wherein the error correction system comprises:

an ECC/remainder generator which sequentially receives bytes of the sector and generates ECC bytes in a write operation and check remainder bytes in a read operation;

a bank of remainder registers which are loaded with the check remainder bytes;

a calculation circuit which serially receives contents of the bank of remainder registers for generating two syndromes.

45. An error correction system for a solid state disk drive, the error correction system using a generator polynomial which is the product of three polynomials, the error correction system comprising:

an ECC/remainder generator which sequentially receives bytes of the sector and generates ECC bytes in a write operation and check remainder bytes in a read operation;

a bank of remainder registers which are loaded with the check remainder bytes;

a calculation circuit which serially receives contents of the bank of remainder registers and uses a first of the three polynomials for generating a first syndrome;

a second of the three polynomials for generating a second syndrome; and

a third of the three polynomials for generating a range check factor.

46. The error correction system of claim 45, wherein the error correction system emulates the operation of a magnetic disk drive.

47. The error correction system of claim 45, wherein the error correction system corrects as many as two errors per sector applied to the system by using a 32 bit code generator polynomial, the 32 bit code generator polynomial being the product of two 14-bit polynomials and a 4-bit polynomial, and wherein the 4-bit polynomial is used to generate the range check factor.

48. The error correction system of claim 47, wherein a first of the two 14-bit two polynomials is the polynomial (x¹⁴ +x¹⁰ +x⁹ +x⁶ x⁵ +x⁴ +1), wherein a second of the two 14-bit polynomials is the polynomial (x¹⁴ +x⁶ +x⁵ +x² +1) and wherein the 4-bit polynomial is the polynomial.

49. The error correction system of claim 45, wherein at least one error locator value is used to determine whether error(s) occurred in a data portion of the sector.

50. The error correction system of claim 45, wherein the bank of remainder registers comprises four 8-bit registers which are parallel loaded with the check remainder bytes, wherein the four 8-bit registers are connected to operate as a serial shift register, and wherein subsequent to generation of the two syndromes and range check factor, the two syndromes and range check factor are serially loaded into the serial shift register.

51. The error correction system of claim 45, wherein the error correction system employs a bit oriented code that processes a byte at a time.

52. An error correction system for correcting a sector of data received from a solid state disk drive, the error correction system employing a code generator polynomial which has a code generator length greater than necessary for correcting as many as two errors per sector applied to the error correction system by the solid state disk drive, the code generator polynomial being utilized by the system to generate at least one syndrome and a range check factor.

53. The error correction system of claim 52, wherein the at least one syndrome is utilized to generate at least one error location, and the range check factor is utilized by the system to check the at least one error location determined by the system.

54. The error correction system of claim 52, wherein the code generator polynomial is a 32 bit code generator polynomial, the 32 bit code generator polynomial being the product of two 14-bit polynomials and a 4-bit polynomial, and wherein the 4-bit polynomial is used to generate the a range check factor.

55. The error correction system of claim 52, wherein a first of the two 14-bit polynomials is the polynomial (x¹⁴ +x¹⁰ +x⁹ +x⁶ +x⁵ +x⁴ +1), wherein a second of the two 14-bit polynomials is the polynomial (X¹⁴ +X⁶ +X⁵ +X² +1), and wherein the 4-bit polynomial is the polynomial (x⁴ +1).