Content addressable memory having selectively interconnected rows of counter circuits
View Patent ↗A content addressable memory (CAM) device includes a plurality of CAM rows, a number of sequencing logic circuits, and a programmable interconnect structure. Each CAM row includes a number of CAM cells to generate a match signal on a match line and includes an enable input. Each sequencing logic circuit includes an input and an output, and is configured to count sequences of match signals from the CAM rows. The programmable interconnect structure selectively connects the match line of any CAM row to the input of any sequencing logic circuit, and selectively connects the output of any sequencing logic circuit to the enable input of any CAM row.
1. A content addressable memory (CAM) device, comprising:
a plurality of CAM rows, each CAM row including a number of CAM cells to generate a match result on a match line and including an enable input; and
a counter row including a counter circuit having an input to receive the match result from a first CAM row, having a first output to provide a continue signal to the enable input of the first CAM row, and having a second output to provide a trigger signal to the enable input of a second CAM row, wherein the continue signal selectively enables the first CAM row for a next compare operation, and the trigger signal selectively enables the second CAM row for the next compare operation.
2. The CAM device of claim 1 , wherein the first CAM row stores a character class specified by a regular expression, the second CAM row stores a suffix string specified by the regular expression, and the counter circuit detects overlapping sequences of m input characters that match the character class, wherein m is a quantifier number specified by the regular expression.
3. The CAM device of claim 2 , wherein the first CAM row asserts a character class match signal for each input character that matches the character class, and the counter circuit is configured to assert the trigger signal in response to m sequential assertions of the character class match signal.
4. The CAM device of claim 3 , wherein the counter circuit is configured to assert the continue signal in response to each assertion of the character class match signal.
5. The CAM device of claim 4 , wherein assertion of the continue signal pre-charges the match line of the first CAM row for the next compare operation, and assertion of the trigger signal pre-charges the match line of the second CAM row for the next compare operation.
6. The CAM device of claim 3 , wherein the counter circuit comprises:
a binary counter having an input to receive the character class match signal, and having an output to generate a character match count; and
compare logic having a first input to receive the character match count, a second input to receive the quantified number, a first output to generate the trigger signal, and a second output to generate the continue signal.
7. The CAM device of claim 6 , wherein the binary counter increments the character match count in response to sequential assertions of the character class match signal, the compare logic asserts the trigger signal if the character match count is equal to the quantifier number, and the compare logic asserts the enable signal if the character match count is less than the quantifier number.
8. The CAM device of claim 1 , further comprising:
a programmable interconnect structure selectively connected to each of the CAM rows and to the counter row.
9. The CAM device of claim 8 , wherein the programmable interconnect structure selectively routes the match result of the first CAM row as an enable signal to any number of selected CAM rows and the counter row at the same time.