Error detection/correction and fault detection/recovery – Pulse or data error handling – Memory testing
Reexamination Certificate
1999-03-26
2001-09-04
DeCady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Memory testing
C714S733000, C714S735000, C714S742000
Reexamination Certificate
active
06286116
ABSTRACT:
BACKGROUND OF THE INVENTION
Content addressable memory, known as CAM, are memory structures used to store similar pieces of data, or to store data that are frequently used in certain parts of computer programs. These data are stored in the CAM either with no particular order, or in the order in which they were previously used by the computer program. When an operating computer program reaches a step where a particular piece of data is needed, the program first asks if the required data is present in the CAM. The data in the CAM is sorted through, a process known as a sieve, and if data match is found, then the program does not have to take the time to go to the main memory to fetch the data. This results in a large time savings, and thus faster program operation.
Typically it is not the data itself that is sieved and matched, but a shorter summarization of the data, known as a tag. It is easier to sieve and match the short tags and thus the size of the content addressable memory can be reduced. The tag is associated with a specific element in a cache memory that holds the data. Thus CAM memories are useful in computers, and numerous CAM memories are found in most typical modern microprocessors and computer systems.
An example of the use of a CAM is found in memory testing. In the testing of a random access memory (RAM) device, several different types of tests will be done, and it may be interesting to know how many different locations on the RAM are defective. It would confuse the data to have the same RAM location, for example column 3 and row 4, listed as defective two or three different times. Thus the testing sequence might be to exercise the RAM with what is known as a rippling ones test, and find that location
3
,
4
fails. This is stored in the CAM. The next test might be a rippling zeros test which also finds location
3
,
4
defective. The CAM is examined and the location
3
,
4
is found by matching and thus the rippling zeros test is not recorded as a new failure. Next, there may be a checkerboard test done which finds location
3
,
4
and location
15
,
1
failing. Matching both locations against the CAM will result in finding location
3
,
4
already in the memory and location
15
,
1
a new failure location, which is then recorded. Thus two distinct locations are found and recorded as failures from the three tests, versus the four failures which would have resulted from the two bad locations over the three tests.
It is well known how to test memories for proper functionality. Typical memory types such as random access memory (RAM) may be tested by writing a logic high, or a one into each memory location in turn, and reading that memory location value to check if a one is written there. The same thing is done by writing a logical low or zero. These two tests determine if any particular bit of the RAM is stuck either high or low. Frequently a checkerboard of alternating ones and zeros is written and read to test the memory. The checkerboard pattern is particularly useful for finding single RAM bit elements that have leakage paths to adjacent RAM elements, something which is not truly tested by the ones or zeros tests where the voltage level may remain high because the adjacent cell to which a leak exists is also high. There also exist tests which write a one into a memory of all zeros, and ‘walks’ the one value through the memory. The comparable walking zero test is also well known in the art.
While the described testing process may be sufficient to completely test RAMs, it is not sufficient for completely testing CAMs, because a CAM is accessed by means of a compare of each of a number of individual bits that make up the tag that is stored in the CAM. Thus a CAM test must test not only that what is written into the CAM, i.e., the stuck-at tests described above, but also that the compare bits work as well. Some CAMs also have a wild card feature which allows matching to selected parts of the entire word. As a result of these features, it is more difficult in general to test CAMs than other types of devices.
It is also much more difficult to test a memory that is built into a logic or microprocessor device. This is known as an embedded memory. This is because in the embedded memory case, not all of the inputs to the memory are accessible to the tester. In general, none of the memory inputs are accessible since only the microprocessor ever needs to write or read from the embedded memory, and input pads are almost always in short supply due to the large increase in device size required for additional input pads. Thus, it is known to be difficult to design tests for embedded memories which will sufficiently test the memory function by exercising the microprocessor alone.
It is known in the art to add some circuitry to the embedded memory to allow what is known as a built-in self test, or BIST. The addition of BIST does add some increased area to the silicon device, but much less than the addition of input and output pads, and it also results in reduced testing difficulty and improved testing fault coverage. BIST is becoming very common in the art for testing various memory types such as RAM, ROM and FIFO, but BIST for CAMs present more difficult problems than for the other memory types, because CAMs have different operating modes than other memory types. Specifically, CAMs have to be tested for the ability to compare or match a test data value with different data values and find the correct data value stored in the CAM. For additional information on BIST for CAMs, see U.S. Pat. No. 5,107,501 by Yervant Zorian, issued Apr. 21, 1992. However, prior art BIST for CAMs requires that the CAM have an additional read port, bus and circuitry added to each cell of the CAM, which adds area to the silicon device. Additionally, the BIST testing of CAMs has controllability and observability problems even with the additional circuitry, read ports and buses, because the propagation logic needed to transport the CAM output to an observability point such as an output pad is long and complex.
Therefore, it would solve a problem in the art to provide a built-in self test mechanism that is simple, adds less cost to the silicon device, and provides better precision in verifying the location of the CAM defect.
SUMMARY OF THE INVENTION
A method and apparatus for built in self testing (BIST) of content addressable memories (CAMs) is disclosed, comprising the steps of creating a set of unique binary data patterns, with the number of unique patterns being at least as large as the number of words contained in the CAM. The method works best when the number of words in the CAM is less than the number of bits in each word, and where the patterns each differ from the other patterns at two or more bit locations. A different one of the unique patterns is written into each of the word locations contained in the CAM, and then each one of the unique patterns is compared individually with each CAM entry. An OR gate is used to determine whether each one of the compared unique patterns matches the contents of one of the words contained in the content addressable memory, and to indicate an error or memory fault if any one of the compared patterns did not indicate a match with any of the stored patterns. This provides CAM failure information without requiring that the CAM data be externally read, and thus does not require that the CAM have a read port. The unique patterns are inverted one bit at a time, and compared to the stored patterns after each bit inversion. There should be no matches found. This testing helps determine cause and location of the fault, without requiring any read operations.
The testing is repeated using the logical complement of each unique pattern, and repeated again using the reverse of each unique pattern. With the described set of tests the location and type of memory fault may be determined without ever having to read the contents of the content addressable memory. Without the requirement of memory reading, there is no need to add read ports to CAMs that are frequently embedded i
Compaq Computer Corporation
De'cady Albert
Hamilton Brook Smith & Reynolds P.C.
Torres Joseph D.
LandOfFree
Built-in test method for content addressable memories does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Built-in test method for content addressable memories, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Built-in test method for content addressable memories will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2529166