Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-05-27
2004-08-03
Tu, Christine T. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C365S049130, C711S108000, C711S111000
Reexamination Certificate
active
06772383
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to error detecting and correcting codes and, more particularly, to error detecting and correcting codes applicable to cache memories.
2. Background Information
It is axiomatic that data entering a data processor, whether it originates in a local memory, or is received from a remote source via a communication link, must be correct. For this reason many error detecting codes (EDC) and error correcting codes (ECC) have been developed to insure the integrity of the information to be processed. Common to all of these codes is redundancy, wherein additional bits are added to the information bits, as a function thereof, to permit the algorithm controlling the check bits to be recomputed at the destination for error detection and possible correction, if the code is sufficiently redundant. Computer memories are an example of a source of data entering a data processor where it is advantageous to use error detecting and error correcting codes. The most likely source of errors in computer memories is corruption of the data during the time the data is held in the memory. Such soft (intermittent) errors may be induced by background cosmic radiation and alpha particle bombardment.
It is well known in the prior art to add a parity bit to units of data being stored in computer memories to detect a single bit error in the data unit when the unit is read. Typically, a parity bit is added for each 8 bit byte of data in the memory. Thus, 9 bits of storage are used for each 8 bit byte of data storage provided. Parity protected memories are limited in that the process requesting faulty data only knows that the data is faulty. There is no general mechanism to allow the process to recover from the error. Most often, a memory fault requires that the process be terminated. It is also well known in the prior art to add error correction codes to units of data being stored to detect and correct errors. This provides a system that can recover from detected errors. For example, a 32 bit computer word can be protected by adding a 6 bit ECC. The ECC allows all single bit errors to be detected and corrected. A 7 bit ECC detects and corrects single bit errors and also detects double bit errors.
To speed memory access, computers often use cache memory, which is a small high speed memory that provides fast access to a copy of the data in current use. Various schemes for managing data transfers between the main memory and the cache memory are well known in the art. All cache memories must provide a means for finding data associated with an address in the larger main memory in the smaller cache memory. One commonly used technique for constructing a cache memory is the set associative cache.
A set associative cache memory contains a predetermined number of cache lines, each line containing a predetermined number of bytes. The low order address bits are used to locate a line and a byte in the cache memory corresponding to any data byte in the main memory. However, there are many bytes of data in the main memory that have the same low order address bits and which would be located in the same place in the cache memory. Therefore, the unused high order address bit, termed the tag bits, are stored in an associated tag memory. When cache memory is accessed, the tag bits stored on the line being accessed are compared to the high order incoming address bits to see if the cache memory contains the byte being accessed. If the tag bits are the same as the high order address bits then there is a cache hit, the cache contains a copy of the main memory address being accessed. Thus, a cache memory read involves first reading the tag memory to see if the cache line contain the desired data, and then reading the data from the data memory if there is a hit.
N-way set associative cache memories provide N locations, where N is 2 or more, that are accessed by the same low order address bits. This allows the number of conflicts for use of a storage location to be reduced because each main memory location can be located in 1 of N locations. When an N-way cache memory is accessed, N tags are retrieved and each tag is compared to the high order incoming address bits to see if any of the N ways of the cache memory contains the byte being accessed.
Cache memory, like all memory, is subject to data corruption. Error correction is especially desirable in cache memory because the majority of memory accesses are likely to involve the cache memory in a well-designed system. It is well known in the prior art to add ECC to the tag memory and to the data memory. However, the number of bits required by an ECC is geometrically related to the number of bits being protected. ECCs to protect short word lengths increase the amount of storage disproportionately. An exemplary computer architecture might use a physical memory address of 44 bits and employ a 512 kilobyte (kb) cache. The cache line might be 8 bytes (64 bits) long. The bottom 3 address bits select a byte within the cache line, the middle 16 bits are the address which selects a cache line and the remaining 25 upper bits are the tag. To provide single bit error correction, a 25 bit tag requires 5 ECC bits and a 64 bit (8 byte) cache line requires 7 ECC bits. Thus, for each cache line in this example, there will be a total of 89 data bits and 12 ECC bits. This represents about 13% additional storage for the ECC bits. However, about 41% of the redundancy is being used to protect the 25 tag bits which represent about 28% of the data.
Accordingly, there is a need for a method and apparatus that allows error correcting codes to be applied more efficiently to set associative cache memories and other applications that require protection of multiple units of related data.
SUMMARY OF THE INVENTION
A computer data signal comprises a first code group and a second code group. The first code group has a first symbol and an error detection code for the first symbol. The second code group has a second symbol and an error correction code. The error correction code provides error correction for a third symbol that includes the first symbol and the second symbol.
REFERENCES:
patent: 4241446 (1980-12-01), Trubisky
patent: 4604750 (1986-08-01), Manton et al.
patent: 4649542 (1987-03-01), Nishimura et al.
patent: 4651321 (1987-03-01), Woffinden et al.
patent: 4742517 (1988-05-01), Takagi et al.
patent: 4945512 (1990-07-01), DeKarske et al.
patent: 5226150 (1993-07-01), Callander et al.
patent: 5345582 (1994-09-01), Tsuchiya
patent: 5357527 (1994-10-01), Coates et al.
patent: 5450340 (1995-09-01), Nicolaidis
patent: 5459850 (1995-10-01), Clay et al.
patent: 5557622 (1996-09-01), Hassoun et al.
patent: 5642494 (1997-06-01), Wang et al.
patent: 5809524 (1998-09-01), Singh et al.
patent: 5841961 (1998-11-01), Kozaru et al.
patent: 5916314 (1999-06-01), Berg et al.
patent: 6038693 (2000-03-01), Zhang
patent: 6101614 (2000-08-01), Gonzales et al.
patent: 6430723 (2002-08-01), Kodama et al.
(Adaptive source rate control for real-time wireless video transmission; Mobile Networks and Applications, pp 49-60, 1998).*
Ritthongpitak et al.(Optimal Two-Level Unequal Error control Codes for Computer Systems; IEEE, 1996).
Fu John
Huang Sunny
Miin Jeen
Mulla Dean
Quach Nhon Toai
Intel Corporation
Lamarre Guy
Tu Christine T.
LandOfFree
Combined tag and data ECC for enhanced soft error recovery... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Combined tag and data ECC for enhanced soft error recovery..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combined tag and data ECC for enhanced soft error recovery... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3269318