Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-05-17
2003-02-11
Ton, David (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S762000, C714S758000, C714S793000
Reexamination Certificate
active
06519734
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a single bit error correction, double burst error detection technique and more particularly to a single bit error correction, double burst error detection code which may be used with RAMs (Random Access Memories) which experience single and adjacent bit errors due to the impingement of high energy particles.
2. Description of Related Art
A microprocessor executing software from RAMs can experience single and adjacent bit errors from high energy particles. Previous attempts to alleviate these errors involve using error correction codes. However, these error correction codes substantially increase the number of bits which must be added to the base microprocessor word width. This both increases the amount of RAM memory needed as well as slowing the processing time due to the increased word length and increased processing time needed for error correction.
There have been many previous attempts to formulate error correction codes, particularly single bit error correcting-double bit error detecting codes. One such attempt is disclosed in an article entitled: “A Class of Optimal Minimum Odd-Weight-Column SEC-DED Codes,” by M. Y. Hsaio, IBM J. Res. Dev., Jul. 14, 1970.
While the technique of Hsaio results in useful correction codes, the addition of the number of parity bits needed for error detection and correction by the Hsaio technique often results in too high an overhead, thereby rendering the technique of Hsaio unusable in certain applications.
U.S. Pat. No. 4,345,328 to White discloses an apparatus for and method of providing single bit error correction and double bit error detection using through checking parity bits. A coding scheme is implemented which uses through checking parity bits appended to each byte as check bits. The remaining check bits are generated such that the combination of through checking parity bits and remaining check bits together provide single bit error correction and double bit error detection. While the scheme of White is useful, it is considerably more complex in handling certain types of double bit errors than that of the present invention.
U.S. Pat. No. 4,905,242 to Popp discloses an error detection and correction apparatus utilizing seven internally generated check bits which are applied to incoming data signals on the next clock. The technique of Popp used a reduced set of check bits to only handle single bit errors in order to reduce the complexity of the technique and was able to pipeline the error checking activity. The present invention, on the other hand, is likewise of low complexity, yet adds double burst error detection.
U.S. Pat. No. 5,457,702 to Williams et al. discloses a system for correcting a single bit error and detecting burst errors. The technique of Williams et al. uses a complex set of error checking bits to increase the error checking performance to handle burst errors but at the high overhead due to the large number of check bits needed for the technique. On the other hand, the technique of the present invention takes a different approach so as to detect certain types of burst errors with less complexity and more efficiency.
U.S. Pat. No. 4,523,314, to Burns et al. discloses an improved error indicating system utilizing adder circuits for use with an error correction code system capable of detecting and indicating multiple bits errors and detecting and correcting single bit errors. As with the above-cited patents, Burns et al. system is more complex than that of the present invention.
SUMMARY OF THE INVENTION
The object of the present invention is to provide an error correction code that can correct the most likely error pattern namely, a single bit error, as well as detecting but not correcting the next most likely error pattern, namely, two adjacent bits in error, with fewer parity bits than any other presently used code.
In the present invention, errors are detected and corrected by the generation of specific syndromes for the error pattern. A systematic code is developed by constructing a parity check matrix which, when multiplied by a vector retrieved from a RAM and corrupted by errors, produces a product known as a syndrome which is a member of one of two mutually exclusive sets. Each possible single bit error corresponds one to one with a member of the first set of syndromes and each two bit adjacent error corresponds non-uniquely to a member of the second separate set of syndromes.
REFERENCES:
patent: 4345328 (1982-08-01), White
patent: 4464753 (1984-08-01), Chen
patent: 4523314 (1985-06-01), Burns et al.
patent: 4713816 (1987-12-01), Van Gils
patent: 4718067 (1988-01-01), Peters
patent: 4821270 (1989-04-01), Mauge
patent: 4905242 (1990-02-01), Popp
patent: 5315544 (1994-05-01), Yokote et al.
patent: 5457702 (1995-10-01), Williams et al.
patent: 5491702 (1996-02-01), Kinsel
patent: 5922080 (1999-07-01), Olarig
Hsiao, “A Class of Optical Minimum Odd-weight-column SED-DED Codes,”IBM J. Res. Develop., 14, Jul. 1970, pp. 395-401.
Lin et al.,Error Control Coding: Fundamentals and Applications, Chapter 16, “Applications of Block Codes for Error Control in Data Storage Systems,” Prentice-Hall Inc., 1983.
Bodnar Lance M.
Chapelle Gregory P.
Antonelli Terry Stout & Kraus LLP
Ton David
TRW Inc.
LandOfFree
Single bit error correction, double burst error detection... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Single bit error correction, double burst error detection..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Single bit error correction, double burst error detection... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3175771