Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-05-17
2003-03-18
Ton, David (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S761000, C714S753000, C714S758000
Reexamination Certificate
active
06536009
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a technique for generating correction codes and more particularly, the present invention relates to a technique for generating correction codes that can correct a single error and detect two adjacent errors in an information word for a range of (n, k) values, where k denotes the length of the information word in bits and n denotes the length of the coded information word in bits.
2. Description of the Related Art
A microprocessor executing software and utilizing RAMs (Random Access Memories) can experience single and adjacent bit errors from high-energy particles impacting the RAMs. Previous attempts to alleviate these errors involved 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 needed as well as slowing the processing time due to the increased word length and increased processing time needed for error correction.
Furthermore, digital communication techniques are now widely being used in many areas today including digital telephony, digital cable TV transmission, and the Internet. All of these digital communication techniques have required the use of error correction and error detection to correct for noise and interference in the communication path.
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 uses a reduced set of check bits to only handle single bit errors in order to reduce the complexity of the technique and is 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
A technique for generating correction codes that can correct a single error and detect two adjacent errors in an information word for a range of (n, k) values, where k denotes the length of the information word in bits and n denotes the length of the coded information word in bits, first generates a parity check matrix. Upon generating the parity check matrix, a received word is multiplied by the parity check matrix to produce a syndrome corresponding to one of two mutually exclusive sets of syndromes if the word contains at least one error, each single bit error in the word corresponding one-to-one with a member of the first of two sets of syndromes and each two bit adjacent error corresponding non-uniquely to a member of the other set of syndromes and a syndrome containing all zeros if the word contains no errors. The actual information in the word is corrected by inverting a bit containing an error if the produced syndrome corresponds to one of the sets of syndromes and an uncorrectable two bit adjacent error is reported if the produced syndromes corresponds to the other of the two sets of syndromes and no error is reported if the produced syndrome contains all zeros.
REFERENCES:
patent: 4345328 (1982-08-01), White
patent: 4523314 (1985-06-01), Burns et al.
patent: 4905242 (1990-02-01), Popp
patent: 5315544 (1994-05-01), Yokote et al.
patent: 5457702 (1995-10-01), Williams et al.
patent: 5490155 (1996-02-01), Abdoo et al.
patent: 5740188 (1998-04-01), Olarig
patent: 5841795 (1998-11-01), Olarig et al.
patent: 5938773 (1999-08-01), Hauck et al.
patent: 6219817 (2001-04-01), Holman
Hsiao, “A Class of Optical Minimum Odd-weight-column SED-DED Codes,”IBM J. Res. Develop., Jul. 14, 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.
Antonelli Terry Stout & Kraus LLP
Ton David
TRW Inc.
LandOfFree
Technique for generating single-bit error-correcting,... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Technique for generating single-bit error-correcting,..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Technique for generating single-bit error-correcting,... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3039946