Built-in self-test technique for content-addressable memories

Claim 2

The method according to claim 1 wherein the preselected sequences of the write and match/read operations comprise the following seven sequences: (a) performing a write operation W ⁰ on each successive row of cells (14), the write operation W ⁰ being performed by writing a word of all zeros into a row of cells; (b) performing a match/read operation M 1/0 , a write operation W ¹, a write operation W ⁰, and a write operation W ¹ in succession on each successive row of cells (14), the match/read operation M 1/0 performed by matching a word of all ones to every row of cells while reading the contents of a successive row to ascertain if the contents are all zeros, and the write operation W ¹ performed by writing a word of all ones into the successive row of cells; (c) successively performing a match/read operarion M 0→ and then a write operation W ¹ on a single row of cells (14), the match/read operation performed by matching each of a sequence of words, obtained by walking a zero through a ones word, to all of the rows of cells, while successively reading the contents of a successive row to determine if the contents correspond to the particular one of the words being matched; (d) performing a match/read operation M ¹, a write operation W ⁰, a match/read operation M ⁰ and a write operation W ⁰ in succession on each row of cells (14), the match read operation M ¹ performed by matching a word of all ones to every row of cells while reading the contents of the successive row to ascertain if the contents are all ones, and the match/read operation M ⁰ being performed by matching a word of all zeros to every row of cells while reading the contents of the successive row to ascertain if the contents are all zeros; (e) performing a match/read operation M ¹, a write operation W ⁰, a write operation W ¹, and a write operation W ⁰ in succession on each successive row of cells (14); (f) successively performing a match/read operation M 1→ and then a write operation W ⁰ on a single row of cells (14), the match/read operation performed by matching each of a sequence of words, obtained by walking a one through a zeros word, to all of the rows of cells, while successively reading the contents of the single row to determine if the contents correspond to the particular one of the words being matched; and (g) performing a match/read operation M ⁰, a write operation W ¹, a match/read operation M ¹ and a write operation W ⁰ in succession on each row of cells (14).

Claim 3

The method according to claim 2 wherein the rows of cells are tested by the steps of: (a) performing the write operation W ⁰ of the first step sequence successively on each row of cells (14); (b) performing the match-read operation M 1/0 and the write operation W ¹, the write operation W ⁰ and the write operation W ¹ of the second sequence of steps successively on each row of cells ( 14); (c) performing the match/read operation M ¹, the write operation W ⁰ and the match read operation M ⁰ on the fourth sequence of steps successively on each row of cells (14); (d) performing the match/read operation M ¹, the write operation W ⁰, and write operation W ¹ and the write operation W ⁰ of the fifth sequence of operations successively on each row of cells (14); and (e) performing the match/read operarion M ⁰, the write operation W ¹, the match/read operation M ¹ and the write operation of the seventh sequence of operations successively on each row of cells (14).

Claim 4

The method according to claim 2 wherein the encoder (30) of the content-addressable memory is tested by executing the write operation W⁰, the match/read operation M ⁰ and the write operation W ¹ of the fourth sequence successively on each row of cells (14).

Claim 5

The method according to claim 2 wherein the exclusive OR gates (22) of the content-addressable memory are tested by the steps of: (a) performing the write operation W ⁰ of the first sequence of steps on each successive row of cells (14) and the match/read operation M 1/0 of the second sequence of steps on each successive row of cells; (b) performing the write operation W ¹ of the second sequence of operations on each row of cells (14) and then performing and the match/read operation M 0→ of the third sequence of steps on one row of cells; (c) performing the write operation W ¹ of the third sequence on each row of cells (14) and then performing the match/read operation M ¹ of the fourth sequence of steps; and (d) performing the write operation W ⁰ of the fourth sequence on each row of cells (14) and then performing the match/read operation M 1→ of the fifth sequence of operations on the one row of cells.

Claim 6

The method according to claim 2 wherein the decoder (21) is tested by the steps of: (a) performing the match/read operation M 1/0 and the last write operation W ¹ of the sequence of operations on each successive row of cells; and (b) performing the match/read operation M ¹ and the last write operation W ⁰ of the fifth sequence of operations successively on each row of cells.

Claim 7

The method according to claim 2 wherein the CAM contains a wild card register (34) for masking the bits of the mask word in the mask register and wherein the wild card register is tested by the steps of: (a) applying a word of all ones to the match wild card register while simultaneously performing the match/read operation M 1/0 of the second sequence of operations; and (b) performing the match/read operation M ¹ of the fourth sequence of Operations.

Claim 8

A test system for testing a content-addressable memory comprised of a plurality of rows of memory cells (14), each cell having an associated exclusive OR (XOR) gate means (22), a decoder (21) for decoding the address of a row of cells into which data is to be read or written, a match word register (25) for storing a match word, and an encoder (30) for determining the address of the row containing a word matching the match word, the test system comprising: an up/down (bidirectional) (37) counter for supplying a count to the decoder of the CAM to address each of a successive row of cells; a test pattern generator (42) for supplying the content-addressable memory with a plurality of sequence of data words from a group consisting of all ones, all zeros, a waking one in a zeros word and a waking zero in a ones word; first means for (44,46) compacting data read from the content-addressable memory; second means (44,46) for compacting data indicative of the address of the rows containing a matching word; and a comparator (40) coupled to the encoder of the content-addressable memory for detecting the condition of the match row address output thereby.

Claim 9

The apparatus according to claim 8 wherein the first compactor means comprises: an AND gate (44) for ANDing the contents of the data read from the content-addressable memory; and an OR gate (46) for ORing the contents of the data read from the content-addressable memory.

Claim 10

The apparatus according to claim 8 wherein the second compacting means comprises: an AND gate (44) for ANDing the data indicative of the addresses of the rows containing matching words; and an OR gate (46) for ORing the data indicative of the addresses of the rows containing matching words.

Claim 11

The apparatus according to claim 8 wherein the content-addressable memory further includes a wild card register (34) for supplying a mask word to mask the match word and wherein the test system includes a wild card generator (42) for supplying a word of all ones and a word of all zeros to test the match register.