Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-05-01
2004-01-06
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S776000
Reexamination Certificate
active
06675344
ABSTRACT:
TECHNICAL FIELD
The technical field is computer and networking systems that implement error correcting code schemes.
BACKGROUND
Modern computer systems use various interconnection mechanisms to allow communications between various components of the computer system. In a multi-computer system, central processing units or the interconnect chipsets may communicate with one another through various defined transactions such as a fetch request, a data return, and a snoop request, for example. Transactions may be sent in each interconnect using a protocol format defined by the specification for that interconnect. Such a transaction may include one or more packets. Different transactions may need different packet lengths. For example, a number of packets required to send a fetch request may be less than a number of packets required to send a cache line data return. A packet is the basic unit of data transmission and includes a number of cycles of data transfer in the interconnect structure.
Most interconnect structures provide a form of error detection and/or correction. An error correcting code (ECC) and associated circuit gives the computer system the ability to tolerate various anticipated errors and to provide a high degree of reliability during data transmission. One approach to implementing an ECC is to provide the ECC at the packet level such that each packet is independently protected by the underlying ECC for anticipated failures.
Error correction codes have been developed that both detect and correct certain errors. One well known class of ECC algorithm is the “Hamming codes,” which are widely used for error detection and correction in digital communications data storage systems. The SEC-DED Hamming code is capable of detecting double bit errors and correcting single bit errors. A detailed description of the Hamming codes is found in Shu Lin et al., “Error Control Coding, Fundamentals and Applications,” Chapter 3 (1982). Another well known ECC algorithm is the “Reed-Solomon code” widely used for error correction in the compact disk industry. A detailed description of this ECC algorithm is found in Hove et al., “Error Correction and Concealment in the Compact Disk System,” Philips Technical Review, Vol. 40, No. 6, pp. 166-172 (1980). The Reed-Solomon code is able to correct multiple errors per word. Other conventional ECC algorithms include the b-adjacent error correction code described in D. C. Bossen, “B-Adjacent Error Correction,” IBM J. Res. Develop., pp. 402-408 (July 1970), and the odd weight column codes described in M. Y. Hsiao, “A Class of Optimal Minimal Odd Weight Column SEC-DED Codes,” IBM J. Res. Develop., pp. 395-400 (July 1970). The Hsiao codes, like the Hamming codes, are capable of detecting double bit errors and correcting single bit errors. The Hsiao codes use the same number of check bits as the Hamming codes (e.g., 8 check bits for 64 bits of data), but are superior in that hardware implementation is simplified and speed of error detection is improved.
Use of an ECC imposes an overhead on each transaction. The extra overhead required to implement the ECC reduces bandwidth available for data transmission and other functions.
SUMMARY
A method and an apparatus are used to maximize available transmission bandwidth by using multiple error correcting code (ECC) schemes. A transaction between components in an interconnected computer system may involve the transmission of header information in a header packet. One or more separate data packets may then be used to transmit other information, depending on the particular transaction and the interconnection buswidth. For example, a cache line data return transaction may involve transmission of 64 bytes of cache line data (i.e., 512 data bits). The transmission bus width may be 76 bits wide. Using a multiple ECC scheme, the header packet may be protected using a standard SEC-DED code of eight ECC bits. The data packets may be combined and protected by a single ECC code of eleven bits, thus significantly reducing the ECC overhead, and improving available data bandwidth.
To reduce data latency, parity bits may be distributed with each of the data packets, with the remaining ECC bits included in the last data packet. In an alternative embodiment, the remaining ECC bits may be placed anywhere in the transaction. This arrangement allows early detection of single bit errors in a specific data packet, and thus reduces latency.
REFERENCES:
patent: 4852100 (1989-07-01), Christensen et al.
patent: 5555250 (1996-09-01), Walker et al.
patent: 5555382 (1996-09-01), Thaller et al.
patent: 5740188 (1998-04-01), Olarig
patent: 5944843 (1999-08-01), Sharma et al.
patent: 6014720 (2000-01-01), Wang et al.
patent: 6038693 (2000-03-01), Zhang
patent: 6463506 (2002-10-01), McAllister et al.
Baker Stephen M.
Hewlett--Packard Development Company, L.P.
LandOfFree
Multiple ECC schemes to improve bandwidth does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiple ECC schemes to improve bandwidth, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiple ECC schemes to improve bandwidth will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3220784