Content-addressable memory (CAM): a 4-word circuit, live
A content-addressable memory (CAM) is searched by value instead of by address: you give it a word, the search key, and it compares the key with every stored word at the same time and reports which ones match. This live one stores four 4-bit words; each word has its own comparator and match line M0 to M3, and HIT is 1 when any word matches.
Ordinary RAM answers "what is stored at address 2?". A CAM answers the reverse question, "where is 1001 stored?", in a single step, because the comparison happens in every word at once rather than one address after another. The write side here is the same as the register file: WE AND the decoded write address WA1 WA0 drives the load input of one 4-bit register, which stores D3 to D0 on the rising edge of CLK. The read side is what makes it a CAM: each register feeds a 4-bit equality comparator, four XNOR gates (one per bit, 1 when the bits agree) ANDed together, with the key K3 to K0 as its other input. Its output is that word's match line, and an OR of the four match lines gives HIT. Searching needs no clock: change K and the match lines change at once. If two words hold the same value, both match lines go high; a real CAM follows the match lines with a priority encoder to turn them into one address. The circuit opens with WE = 1, so you can write word 0 straight away: set D, turn CLK on and off, change WA and repeat, then set K to search. The words start unknown until they are written, as in real hardware.
Open this circuit in the lab →
What you need
- 4× 4-bit register with load: the four stored words, each four D flip-flops and a load multiplexer per bit
- 2× NOT + 4 AND: the 2-to-4 decode of the write address WA1 WA0
- 4× AND: each decoded line AND WE, the load signal of one word
- 4× 4-bit equality comparator: 4 XNOR + 3 AND each: match line Mk = 1 when word k equals K3..K0
- 3× OR: HIT = M0 + M1 + M2 + M3
Step by step
- Place inputs
D3toD0,WA1,WA0,WE,CLK,K3toK0and probesM0toM3andHIT. - Place four 4-bit registers with load on CLK, with D3 to D0 as their data inputs, and load register k from (decoded WA = k) AND WE.
- Give each register an equality comparator: XNOR each stored bit with the matching key bit and AND the four results. That output is the match line Mk.
- OR the four match lines into
HIT. - Write a word into each address (set WA and D, pulse CLK), then set WE = 0 and change K: the match line of every word equal to K lights at once.
Ports and what they do
| Inputs | When | What happens |
|---|---|---|
| WA1 WA0, D3..D0, WE = 1 | rising edge of CLK | Word WA stores D; the other three keep their values |
| WE = 0 | rising edge of CLK | No word changes |
| K3..K0 | any time | Mk = 1 for every word k equal to K; HIT = 1 if any match (no clock needed) |
The checked sequence
| Step | Operation | Result |
|---|---|---|
| 1 to 4 | Write word 0 = 0011, 1 = 0101, 2 = 1001, 3 = 1110 | One word stores per clock |
| 5 to 8 | Search K = 0011, 0101, 1001, 1110 | Only M0, M1, M2, M3 in turn; HIT = 1 |
| 9 to 11 | Search K = 0000, 1111, 0111 | No match line; HIT = 0 |
| 12 | Write word 2 = 0101, search 0101 | M1 and M2 both match |
| 13 | Search 1001 | No match: the old value of word 2 is gone |
| 14 | Write 1001 to word 0 with WE = 0, search 1001 and 0011 | No match, then M0: word 0 still holds 0011 |
Before the page is built, the 4-bit equality comparator is swept on all 256 input pairs and the CAM is run through this 30-step sequence, with every match line and HIT checked after every step.
You can also read the full theory in the lesson on cache memory. Prefer to build it yourself from scratch? Open the digiwleea lab and place the gates on the canvas, or start from the logic gate simulator.
More builds: Registers and counters
All 246 build guides, by topic
Each of these is one step from a transistor to a working CPU. Build every gate from CMOS transistors and work all the way up in the free digiwleea lab, with the free theory reference alongside.
Open the content-addressable memory (CAM, 4 x 4-bit) in the lab →Frequently asked
What is content-addressable memory?
Memory that is searched by content: you supply a value and it reports which stored words equal it, comparing all of them at once. RAM does the opposite, returning the word stored at an address you supply.
How does a CAM work?
Every stored word has its own comparator, XNOR gates that check each bit against the search key, ANDed into a match line. All the comparators work in parallel, so a search takes one step however many words there are, and an encoder turns the match lines into an address.
Where is content-addressable memory used?
Wherever a lookup must be fast: network switches look up MAC addresses in CAM, routers use ternary CAM for IP route lookup, and a CPU's TLB and fully associative caches use the same parallel tag match.
What is a ternary CAM (TCAM)?
A CAM whose stored bits can be 0, 1 or X (don't care). An X matches either key bit, which lets one entry stand for a whole range of keys, such as an IP address prefix.
What are the disadvantages of CAM?
Every search compares every word, so a CAM needs a comparator per word and uses much more area and power per bit than RAM. That is why CAMs are kept small and used only where the parallel search pays off.
What is the difference between CAM and RAM?
RAM takes an address and returns the data stored there. CAM takes data and returns where it is stored, or whether it is stored at all.