ECC for component failures using Galois fields

Details ECC for component failures using Galois fields ECC for component failures using Galois fields

2007-03-06

2007-03-06

Lamarre, Guy J. (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S786000

Reexamination Certificate

active

10696891

ABSTRACT:
An apparatus comprises a check bit encoder circuit and a check/correct circuit. The apparatus operates on encoded data blocks, wherein each encoded data block includes a data block, a first plurality of check bits, and a second plurality of check bits. The encoded data block is logically arranged as an array of R rows and N columns, and each of the N columns comprises data bits from a respective one of the plurality of components. The first check bits form a first column of the array, and each of the first check bits covers a row of the array. The second check bits form a second column of the array and are defined to cover bits in the array according to a plurality of check vectors. Each check vector corresponds to a different bit in the array and is an element of a Galois Field (GF(2R)). The check vectors are derived from a plurality of unique elements of GF(2R), each of which corresponds to a different column of the array. The check vector in row X of the column is the product, in GF(2R), of the unique element for that column and alphaX, wherein alpha is a primitive element of GF(2R).

REFERENCES:
patent: 4376300 (1983-03-01), Tsang
patent: 4433388 (1984-02-01), Oosterbaan
patent: 4434459 (1984-02-01), Holland et al.
patent: 4556977 (1985-12-01), Olderdissen et al.
patent: 4584681 (1986-04-01), Singh et al.
patent: 4604751 (1986-08-01), Aichelmann, Jr. et al.
patent: 4617664 (1986-10-01), Aichelmann, Jr. et al.
patent: 4665537 (1987-05-01), Moriyama
patent: 4949342 (1990-08-01), Shimbo et al.
patent: 5020060 (1991-05-01), Murai et al.
patent: 5058115 (1991-10-01), Blake et al.
patent: 5077737 (1991-12-01), Leger et al.
patent: 5164944 (1992-11-01), Benton et al.
patent: 5177747 (1993-01-01), Capps et al.
patent: 5228046 (1993-07-01), Blake et al.
patent: 5233614 (1993-08-01), Singh
patent: 5251219 (1993-10-01), Babb
patent: 5255226 (1993-10-01), Ohno et al.
patent: 5276834 (1994-01-01), Mauritz et al.
patent: 5291496 (1994-03-01), Andaleon et al.
patent: 5303302 (1994-04-01), Burrows
patent: 5463644 (1995-10-01), Rodi et al.
patent: 5490155 (1996-02-01), Abdoo et al.
patent: 5502675 (1996-03-01), Kohno et al.
patent: 5537421 (1996-07-01), Dujari et al.
patent: 5574856 (1996-11-01), Morgan et al.
patent: 5606662 (1997-02-01), Wisor
patent: 5640353 (1997-06-01), Ju
patent: 5682394 (1997-10-01), Blake et al.
patent: 5757823 (1998-05-01), Chen et al.
patent: 5758056 (1998-05-01), Barr
patent: 5790715 (1998-08-01), Iizuka
patent: 5812564 (1998-09-01), Bonke et al.
patent: 5822257 (1998-10-01), Ogawa
patent: 5867642 (1999-02-01), Vivio et al.
patent: 5872790 (1999-02-01), Dixon
patent: 5909541 (1999-06-01), Sampson et al.
patent: 5923682 (1999-07-01), Seyyedy
patent: 5928367 (1999-07-01), Nelson et al.
patent: 5953265 (1999-09-01), Walton et al.
patent: 5978952 (1999-11-01), Hayek et al.
patent: 5987628 (1999-11-01), Von Bokern et al.
patent: 6009548 (1999-12-01), Chen et al.
patent: 6018817 (2000-01-01), Chen et al.
patent: 6038680 (2000-03-01), Olarig
patent: 6044483 (2000-03-01), Chen et al.
patent: 6052818 (2000-04-01), Dell et al.
patent: 6065102 (2000-05-01), Peters et al.
patent: 6070255 (2000-05-01), Dell et al.
patent: 6076182 (2000-06-01), Jeddeloh
patent: 6101614 (2000-08-01), Gonzales et al.
patent: 6115828 (2000-09-01), Tsutsumi et al.
patent: 6141789 (2000-10-01), Cypher
patent: 6158025 (2000-12-01), Brisse et al.
patent: 6167495 (2000-12-01), Keeth et al.
patent: 6181614 (2001-01-01), Aipperspach et al.
patent: 6209113 (2001-03-01), Roohparvar
patent: 6223301 (2001-04-01), Santeler et al.
patent: 6233716 (2001-05-01), Cypher
patent: 6233717 (2001-05-01), Choi
patent: 6246616 (2001-06-01), Nagai et al.
patent: 6282686 (2001-08-01), Cypher
patent: 6301680 (2001-10-01), Cypher
patent: 6301780 (2001-10-01), Templeton
patent: 6367046 (2002-04-01), Chapman et al.
patent: 6374383 (2002-04-01), Weng
patent: 6393597 (2002-05-01), Cypher
patent: 6453440 (2002-09-01), Cypher
patent: 6473880 (2002-10-01), Cypher
patent: 6477682 (2002-11-01), Cypher
patent: 6505305 (2003-01-01), Olarig
patent: 6704838 (2004-03-01), Anderson
patent: 6738947 (2004-05-01), Maeda
patent: 6766493 (2004-07-01), Hoffman et al.
patent: 6779150 (2004-08-01), Walton et al.
patent: 6973613 (2005-12-01), Cypher
patent: 6976194 (2005-12-01), Cypher
patent: 6996766 (2006-02-01), Cypher
patent: 2001/0001158 (2001-05-01), Tetrick
patent: 2003/0093744 (2003-05-01), Leung et al.
patent: 2003/0163777 (2003-08-01), Holt
patent: 2003/0233611 (2003-12-01), Humlicek et al.
patent: 2004/0054956 (2004-03-01), Byrd
Dell Computer Corp., David Locklear, “Chipkill Correct Memory Architecture,” Aug. 3, 2000, 3 pages.
Dell, “A White Paper on the Benefits of Chipkill-Correct ECC for PC Server Main Memory,” IBM Microelectronics Division, Nov. 1997, pp. 1-23.
“The IBM Eserver pSeries 690, Reliability, Availability, Serviceability (RAS),” IBM Technical White Paper, Sep. 2001, 24 pages.
“Parallel Parity,” http://bbs-koi.uniinc.msk.ru/tech1/1994/er—cont/block.htm, 1994, 1 pg.
“Modulo-2 Arithmetic,” http://bbs-koi.uniinc.msk.ru/tech1/1994/er—cont/modulo.htm, 1994, 1 pg.
“Introduction to Error Control,” http://bbs-koi.uniinc.msk.ru/tech1/1994/er—cont/intro.htm, 1994, 1 pg.
Barker et al. “ASCII Table,” http://www.eng2.uconn.edu/cse/Cour...08W/References/Ref—ASCIITable.html, Feb. 1998, 1 pg.
“Parity & Computing parity,” http://bbs-koi.uniine.msk.ru/tech1/1994/er—cont/parity.htm, 1994, 2 pgs.
“Error Correction with Hamming Codes,” http://bbs-koi.uniine.msk.ru/tech1/1994/er—cont/hamming.htm, 1994, 2 pgs.
Barker et al. “Hamming Code, Background Information,” http://www.eng2.uconn.edu/cse/Courses/CSE208W/Hamming/Background.html, Feb. 1998, 3 pgs.
Barker et al., “Hamming Code, Theory,” http://www.eng2.uconn.edu/cse/Courses/CSE208W/Hamming/Theory.html, Mar. 1998, 2 pgs.
“NUMA: Delivering the Next Level of Commodity SMP Performance,” http://199.245.235.23
ewsletters/html/vpoint5.html, 1996, 4 pgs.
Barker et al. “General Definitions,” http://www.eng2.uconn.edu/cse/Cour...8W/References/Ref—Definitions.html, Feb. 1998, 3 pgs.
Barker et al. “Hamming Code, Lab Procedure,” http://www.eng2.uconn.edu/cse/Courses/CSE208W/Hamming/Procedure.html, Jun. 1998, 3 pgs.
Burskirk, “32-Bit-Wide Memory Tolerates Failures,” NT Tech Notes, Oct. 1990, p. 818.
C. L. Chen, “Symbol Error Correcting Codes for Memory Applications,” IBM Corporation, IEEE, 1996, pp. 200-207.
IEEE Transactions of Computers, vol. 41, No. 2, Feb. 1992, 5 pages.
Hamada, et al., “A Class of Error Control Codes for Byte Organized Memory Systems -SbEC-(Sb+S)ED Codes-,” IEEE Transactions of Computers, vol. 46, No. 1, Jan. 1997, 5 pages.
Costello, Jr., et al., “Applications of Error-Control Coding,” IEEE Transactions on Information Theory, vol. 44, No. 6, Oct. 1998, pp. 2531-2560.
Ziegler, et al., “Cosmic Ray Soft Error Rates of 16-Mb DRAM Memory Chips,” IEEE Journal of Solid-State Circuits, vol. 33, No. 2, Feb. 1998, pp. 246-252.
Peterson, et al., “Error-Correcting Codes,” Second Edition, The MIT Press, 1972, pp. 357-373.
Shu Lin, “Error Control Coding, Fundamental and Applications,” Prentice-Hall, 1983, pp. 503-525 and 532.
IBM Technical Disclosure Bulletin, “Memory Chip Failure-Detection Mechanism”, Mar. 1991, vol. 33, No. 10A, XP000110029, pp. 240-242.
Saxena, et al., “Error Detection and Handling in a Superscalar, Speculative Out-of-Order Execution Processor System,” IEEE, 1995, pp. 464-471.
Rolf Johansson, “Two Error-Detecting and Correcting Circuits for Space Applications,” IEEE 1996, pp. 436-439.
IBM Technical Disclosure Bulletin, “Concurrent On-Lin Array Chip Sparing From Scrub-Assisted Fault Data,” Dec. 1991, vol. 34, No. 7A, pp. 16-19.
Polianskikh, B. et al., “design and Implementat

Affiliated with

Also associated with

Rating

ECC for component failures using Galois fields does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with ECC for component failures using Galois fields, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and ECC for component failures using Galois fields will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3736464