Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-11-30
2002-10-01
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S763000
Reexamination Certificate
active
06460157
ABSTRACT:
TECHNICAL FIELD
This invention relates, in general, to computer error correction codes and, in particular, to conversions from one or more source error correction codes to one or more destination error correction codes.
BACKGROUND ART
The small size of computer transistors and capacitors, combined with transient electrical and electromagnetic phenomena cause occasional errors in stored information in computer memory systems. Therefore, even well-designed and generally reliable memory systems are susceptible to memory device failures.
In an effort to minimize the effects of these memory device failures, various error checking schemes have been developed to detect, and in some cases correct, errors in messages read from memory. The simplest error detection scheme is the parity bit. A parity bit is an extra bit included with a binary data message or data word to make the total number of 1's in the message either odd or even. For “even parity” systems, the parity bit is set to make the total number of 1's in the message even. For “odd parity” systems, the parity bit is set to make the total number of 1's in the message odd. For example, in a system utilizing odd parity, a message having two 1's would have its parity bit set to 1, thereby making the total number of 1's odd. Then, the message including the parity bit is transmitted and subsequently checked at the receiving end for errors. An error results if the parity of the data bits in the message does not correspond to the parity bit transmitted. As a result, single bit errors can be detected. However, since there is no way to detect which particular bit is in error, correction is not possible. Furthermore, if two or any even number of bits are in error, the parity will be correct and no error will be detected. Parity therefore is capable of detecting only odd numbers of errors and is not capable of correcting any bits determined to be in error.
Error correction codes (ECCs) have thus been developed to not only detect but also correct bits determined to be in error. ECCs utilize multiple parity check bits stored with the data message in memory. Each check bit is a parity bit for a group of bits in the data message. When the message is read from memory, the parity of each group, including the check bit, is evaluated. If the parity is correct for all of the groups, it signifies that no detectable error has occurred. If one or more of the newly generated parity values are incorrect, a unique pattern called a syndrome results which may be used to identify the bit in error. Upon detection of the particular bit in error, the error may be corrected by complementing the erroneous bit.
A widely used type of ECC utilized in error control in digital systems is based on the codes devised by R. W. Hamming, and thus take the name “Hamming codes”. One particular subclass of Hamming codes includes the single error correcting and double error detecting (SEC-DED) codes. As their name suggests, these codes may be utilized not only to correct any single bit error but also to detect double bit errors.
Another type of well-known ECC is the single symbol correction and double symbol detection (SSC-DSD) codes which are used to correct single symbol errors and detect double errors. In systems implementing these types of codes, the symbol represents a multiple bit package or chip. Hence, as the name implies, an SSC-DSD code in a system utilizing n bit symbols would be capable of correcting n bits in a single symbol and detecting errors occurring in double symbols.
As can be expected, the structure and format of these ECCs depend on and vary with the bandwidth supported by the particular component in which the individual ECCs have been implemented. For instance, depending on the architecture of the implementing system, data fetched out of main memory may be in the form of 128 bit words requiring the use of 12 ECC check bits for protection whereas data fetched out of an L2 cache may take the form of 64 bit words requiring the use of 8 ECC check bits for protection. As can be imagined, problems often arise during transmission between components operating under differing bandwidths.
In a typical conversion process, when transmitting protected data between components operating under differing bandwidths (and thus differing ECCS), a source ECC is first decoded with any errors occurring in the data being corrected at that time. Then, the data is converted to meet the format of the destination component and later protected with an ECC scheme corresponding to that format. Thus, a period of time exists after error detection and correction at the source component but before the implementation of error protection in the destination component where data corruption may occur. Under these circumstances, erroneous data would appear as being error-free to the destination component and would subsequently become protected under the destination ECC scheme even with the existence of corrupted data.
Thus, a need exists for a conversion mechanism capable of protecting data being transmitted from components operating under one ECC scheme to components operating under different ECC schemes. In addition, as speed in processing is always desirable, a further need exists for such a mechanism which converts between ECC schemes rapidly and efficiently without the use of unnecessary or redundant logic.
SUMMARY OF THE INVENTION
A data protection capability for protecting data during conversion between different error correction codes (ECCs) is provided which generates the destination ECC prior to error detection and correction in the source ECC. Errors detected in the source ECC are then corrected in the destination ECC thereby resulting in an overlap between the protection imparted by the differing error correction schemes. In addition, by commencing generation of the destination ECC before error detection in the source ECC, the conversion occurs in parallel thus resulting in a time savings over serial processes. Finally, various logic reduction techniques are implemented to further reduce the amount of time required during conversion.
In one example, a method of protecting data during conversion from at least one source error correction code to at least one destination error correction code, wherein the at least one source error correction code and the at least one destination error correction code both comprise a set of data bits representing the data, and wherein the at least one destination error correction code further comprises a plurality of destination check bits to be generated from the set of data bits during conversion for protecting the data after conversion is disclosed. This method comprises: generating, during conversion from the at least one source error correction code to the at least one destination error correction code, the plurality of destination check bits prior to a detection for errors in the at least one source is error correction code to ensure that the data bits are protected throughout the conversion; detecting any errors in the at least one source error correction code; and correcting any errors, detected in the at least one source error correction code, by complementing any erroneous bits in the at least one destination error correction code.
In another example, a system for protecting data during conversion from at least one source error correction code to at least one destination error correction code, wherein the at least one source error correction code and the at least one destination error correction code both comprise a set of data bits representing the data, and wherein the at least one destination error correction code further comprises a plurality of destination check bits to be generated from the set of data bits during conversion for protecting the data after conversion is disclosed. This system comprises: means for generating, during conversion from the at least one source error correction code to the at least one destination error correction code, the plurality of destination check bits prior to a detection for err
Chen Chin-Long
Hsiao Mu-Yue
Meaney Patrick J.
Shen William Wu
Cutter, Esq. Lawrence D.
De'cady Albert
Harris Cynthia
Heslin Rothenberg Farley & & Mesiti P.C.
Radigan, Esq. Kevin P.
LandOfFree
Method system and program products for error correction code... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method system and program products for error correction code..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method system and program products for error correction code... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2925656