Content addressable memory with base-three numeral system
A CAM cell is disclosed that can be selectively configured to store either base-2 data words or base-3 data words. When configured to store base-3 data words, the quaternary CAM cell compares 3 comparand bits representative of a base-3 comparand value with the base-3 data value stored in the CAM cell. Storing base-3 data words in such CAM cells increases the data storage density of associated CAM arrays.
1. A content addressable memory (CAM) device including an array having a plurality of quaternary CAM cells each configured to store a base-3 data value having one of four possible states represented by first and second data bits, wherein a respective CAM cell comprises:
first and second memory cells for storing the first and second data bits, respectively; and
a compare circuit, coupled to the first and second memory cells and to a match line, to selectively discharge the match line in response to a compare operation between a base-3 comparand value and the base-3 data value.
2. The CAM device of claim 1 , wherein the comparand value is represented by three comparand bits.
3. The CAM device of claim 2 , wherein the compare circuit is to compare the three comparand bits with the first and second data bits at the same time.
4. The CAM device of claim 2 , wherein the compare circuit comprises three pull-down transistors, each to selectively discharge the match line in response to a corresponding one of the three comparand bits.
5. The CAM device of claim 1 , wherein the four possible states consist of a logic 0 value, a logic 1 value, a logic 2 value, and a don't care state.
6. The CAM device of claim 1 , wherein the compare circuit comprises:
a first pull-down transistor connected between the match line and a first node, and having a gate to receive a first comparand bit;
a second pull-down transistor connected between the match line and a second node, and having a gate to receive a second comparand bit; and
a third pull-down transistor connected between the match line and a third node, and having a gate to receive a third comparand bit.
7. The CAM device of claim 6 , wherein the compare circuit further comprises:
a first relay transistor connected between the first node and the third node, and having a gate to receive a complemented second data bit; and
a second relay transistor connected between the second node and the third node, and having a gate to receive a complemented first data bit.
8. The CAM device of claim 7 , wherein the compare circuit further comprises:
a first gating transistor connected between the first node and ground potential, and having a gate to receive the first data bit; and
a second gating transistor connected between the second node and ground potential, and having a gate to receive the second data bit.
9. The CAM device of claim 8 , wherein:
the first, second, and third pull-down transistors are NMOS transistors;
the first and second relay transistors are NMOS transistors; and
the first and second gating transistors are NMOS transistors.
10. The CAM device of claim 1 , further comprising:
a comparand conversion circuit, coupled to the CAM array, to selectively convert a base-2 comparand value into the base-3 comparand value in response to a mode signal.
11. The CAM device of claim 1 , further comprising:
a data conversion circuit, coupled to the CAM array, to selectively convert a base-2 data value into the base-3 data value in response to a mode signal during write operations.
12. The CAM device of claim 1 , further comprising:
a data conversion circuit, coupled to the CAM array, to selectively convert the base-3 data value into a base-2 data value in response to a mode signal during read operations.
13. A content addressable memory (CAM) cell to store a base-3 data value having one of four possible states represented by first and second data bits, wherein the CAM cell comprises:
first and second memory cells for storing the first and second data bits, respectively; and
a compare circuit configured to compare a base-3 comparand value with the base-3 data value, wherein the base-3 comparand value is provided to the CAM cell as three comparand bits.
14. The CAM cell of claim 13 , wherein the compare circuit is to compare the three comparand bits with the first and second data bits at the same time.
15. The CAM cell of claim 13 , wherein the four possible states consist of a logic 0 value, a logic 1 value, a logic 2 value, and a don't care state.
16. The CAM cell of claim 13 , wherein the compare circuit comprises three pull-down transistors, each to selectively discharge the match line in response to a corresponding one of the three comparand bits.
17. The CAM cell of claim 13 , wherein the compare circuit comprises:
a first pull-down transistor connected between the match line and a first node, and having a gate to receive a first comparand bit;
a second pull-down transistor connected between the match line and a second node, and having a gate to receive a second comparand bit; and
a third pull-down transistor connected between the match line and a third node, and having a gate to receive a third comparand bit.
18. The CAM cell of claim 17 , wherein the compare circuit further comprises:
a first relay transistor connected between the first node and the third node, and having a gate to receive a complemented second data bit; and
a second relay transistor connected between the second node and the third node, and having a gate to receive a complemented first data bit.
19. The CAM cell of claim 17 , wherein the compare circuit further comprises:
a first gating transistor connected between the first node and ground potential, and having a gate to receive the first data bit; and
a second gating transistor connected between the second node and ground potential, and having a gate to receive the second data bit.
20. A method of performing a compare operation between a base-3 comparand word with a plurality of base-3 data words stored in corresponding rows of a content addressable memory (CAM) array, the method comprising:
receiving the base-3 comparand word, wherein the base-3 comparand word comprises a plurality of trit values;
providing each trit value to a corresponding column of CAM cells in the array, wherein each trit value is represented by three comparand bits; and
comparing each trit value with corresponding base-3 data values stored in the CAM cells of the corresponding column in the CAM array.
21. The method of claim 20 , further comprising:
converting a base-2 comparand word into the base-3 comparand word using a comparand conversion circuit; and
converting a base-2 data word into the base-3 data word using a data conversion circuit.
22. The method of claim 21 , further comprising:
selectively enabling the comparand conversion circuit and the data conversion circuit in response to a mode signal.
23. The method of claim 20 , wherein a respective base-3 data value is stored in a corresponding CAM cell as first and second data bits.
24. The method of claim 23 , wherein the first and second data bits collectively represent one of four possible states consisting of a logic 0 value, a logic 1 value, a logic 2 value, and a don't care state.
25. The method of claim 23 , wherein the CAM cell compares the three comparand bits with the first and second data bits at the same time.
26. The method of claim 20 , further comprising:
reading the base-3 data values from the CAM array; and
converting the base-3 data values into base-2 data values using a data conversion circuit.