Content-addressable memory (CAM): Worked examples — Hardware deep dive

We only need three facts from the parent, and we restate them so nothing is assumed:

Formula The three rules we lean on

Row match rule. A row's match line $ML_{r}$ stays HIGH (a "1", meaning this row matched) only if every bit agrees. Formally $ML_{r} = \prod_{i} (D_{r, i} ⊙ S_{i})$ , where $\prod$ means "AND them all together", $D_{r, i}$ is the stored bit, $S_{i}$ is the search bit, and $⊙$ (XNOR) is "1 when the two bits are equal".
One disagreement kills the row. Because the bits are ANDed, a single mismatching bit drags $ML_{r}$ to LOW (a "0", meaning no match).
TCAM don't-care (stored mask). A cell can hold a special mask $M_{i} = 1$ meaning "don't-care" — that bit matches both 0 and 1. Match rule per bit becomes $match_{i} = M_{i} + (D_{i} ⊙ S_{i})$ (the $+$ is OR: "either it's masked, or it agrees").
Global search mask. When the query (not the storage) chooses to ignore some positions, we supply a mask $G$ with $G_{i} = 1$ meaning "ignore bit $i$ this search". The per-bit rule is $match_{i} = G_{i} + (\overline{G_{i}} \cdot (D_{i} ⊙ S_{i}))$ : if $G_{i} = 1$ the bit passes automatically; if $G_{i} = 0$ it must genuinely agree. (This is the same shape as the stored-mask rule, but the mask now travels with the search key instead of the stored word.)

Figure — Content-addressable memory (CAM)

Throughout, a row that matches = its match line is HIGH. The priority encoder then squeezes all the HIGH lines into one output address: the lowest row index wins (unless we say otherwise, e.g. longest-prefix routing). See Priority Encoder for that tie-breaker box, and Boolean Algebra & De Morgan's Laws for why "NOT any-mismatch = all-agree".

The scenario matrix

Every CAM search falls into one of these case-classes. The last column names the example that nails it.

#	Case class	What is special about it	Example
A	Exact single match (BCAM)	Exactly one row equals the key	Ex 1
B	Total miss	No row matches at all	Ex 2
C	Multiple matches, tie-break	Two identical rows, encoder must choose	Ex 3
D	All-zero key (ordinary) vs all-masked stored (matches everything)	The two "degenerate" inputs behave oppositely	Ex 4
E	Single-bit-off near miss	Row differs by exactly one bit — still a full miss	Ex 5
F	TCAM don't-care in stored word	Stored $X$ matches both 0 and 1	Ex 6
G	TCAM masked search key (global mask)	We search ignoring some bit positions	Ex 7
H	Longest-prefix routing (real-world)	Many prefixes match; most specific wins	Ex 8
I	Limiting behaviour (timing/power)	What " $O (1)$ " really means as $R, n$ grow	Ex 9
J	Exam twist (encoder + power reasoning)	Combine match-count with priority + energy	Ex 10

Cell A — Exact single match

Worked example Example 1 — one row equals the key (BCAM)

A 4-bit BCAM stores: R0=1100, R1=0101, R2=1110. Search key $S =$ 0101. (Reminder: bit0 = leftmost bit.) Forecast: Which single row's match line stays HIGH?

Compare R0 1100 vs 0101 bit by bit. Bit0 (leftmost): 1 vs 0 → disagree. Why this step? One disagreement is enough — its wired-OR tap fires and no need to check the rest, R0 is dead. ML0 = LOW.
Compare R1 0101 vs 0101. 0=0, 1=1, 0=0, 1=1 → all four XNORs are 1. Why this step? Every bit agrees, so no tap fires and nothing discharges the precharged line; ML1 stays HIGH.
Compare R2 1110 vs 0101. Bit0: 1 vs 0 → disagree → ML2 = LOW. Why this step? Again, the first disagreeing bit taps the line LOW and settles it.
Encoder. Only ML1 is HIGH → output address = 1. Why this step? The priority encoder's job is to turn a set of HIGH match lines into a single binary address; with exactly one line HIGH there is no tie, so it simply emits that line's index.

Verify: Read back address 1 as if it were RAM → stored word R1 = 0101 = the key. The round-trip data→address→data returns the key, so the match is genuine. ✓

Cell B — Total miss

Worked example Example 2 — the key is not in the memory

Same store R0=1100, R1=0101, R2=1110. Search key $S =$ 1111. (bit0 = leftmost.) Forecast: How many match lines stay HIGH?

R0 1100 vs 1111. Bit2: 0 vs 1 → disagree → ML0 LOW. Why this step? Bit2 disagrees, so R0's tap fires and drains its line — R0 is out.
R1 0101 vs 1111. Bit0: 0 vs 1 → disagree → ML1 LOW. Why this step? Bit0 disagrees, so R1's tap fires and drains its line — R1 is out.
R2 1110 vs 1111. Bit3 (last): 0 vs 1 → disagree → ML2 LOW. Why this step? Bit3 disagrees, so R2's tap fires and drains its line — R2 is out.
Encoder. All match lines LOW. The encoder raises a separate "no-match" flag (often called hit/miss). Output address is undefined/invalid. Why this step? The encoder can only output an index when some line is HIGH; with zero HIGH lines its address bits are meaningless, so hardware exposes a dedicated valid/hit wire to say "nothing was found".

Verify: 1111 differs from every stored word in ≥1 position (checked in steps 1–3). No row can equal it, so zero matches is correct — this is why real CAMs carry a distinct match-found wire. ✓

Cell C — Multiple matches, tie-break

Worked example Example 3 — duplicate rows both match

Store R0=1010, R1=0011, R2=1010 (R0 and R2 are identical). Search key $S =$ 1010. (bit0 = leftmost.) Forecast: Two lines will go HIGH — which address comes out?

R0 1010 vs 1010. bit0 1=1, bit1 0=0, bit2 1=1, bit3 0=0 → all agree → ML0 HIGH. Why this step? We must check every bit to declare a match, because a match needs the AND of all bits — one silent disagreement would flip the verdict.
R1 0011 vs 1010. bit0: 0 vs 1 → disagree → tap fires → ML1 LOW. Why this step? The very first disagreeing bit is decisive under the wired-OR, so R1 is eliminated immediately.
R2 1010 vs 1010. all four bits agree → ML2 HIGH. Why this step? Duplicate data legitimately produces two HIGH match lines — this is the exact situation the parent's "only one row can match" mistake warns about.
Priority encoder resolves the tie. With lowest-index-wins policy → output = 0. Why this step? The encoder is deterministic: it must output one address, so when several lines are HIGH it applies a fixed priority rule (lowest index). See Priority Encoder.

Verify: Both address 0 and 2 hold 1010, so either is a "correct" location, but the encoder's rule forces 0. Re-reading address 0 gives 1010 = key. ✓

Cell D — The two degenerate inputs, side by side

Worked example Example 4 — all-zero

key vs all-masked stored word This one example covers both degenerate ends so you see they behave oppositely. Part 1 (all-zero search key). BCAM store R0=0000, R1=1010. Search key $S =$ 0000. Part 2 (all-masked stored word). TCAM row R0 stores 0000 with mask $M =$ 1111 (every bit don't-care). Search keys $S =$ 0110 then $S =$ 1111. Forecast: Does an all-zero key match "everything"? Does an all-masked row?

Part 1 — compare all-zero key 0000 to R0 0000. bit0 0=0, bit1 0=0, bit2 0=0, bit3 0=0 → all agree → ML0 HIGH. Why this step? An all-zero key is just an ordinary value; it matches a row that literally stores 0000, nothing magic.
Part 1 — compare 0000 to R1 1010. bit0: 0 vs 1 → disagree → ML1 LOW. Why this step? The zero key does not match everything — it fails on any row that stores a 1 in a compared position, proving "all-zero key" ≠ "matches all".
Part 2 — apply stored-mask rule $match_{i} = M_{i} + (D_{i} ⊙ S_{i})$ with $M_{i} = 1$ everywhere. Why this step? $M_{i} = 1$ makes $match_{i} = 1 + (\dots) = 1$ regardless of the bits (OR with 1 is always 1).
Part 2 — key 0110: all four match $_{i} = 1$ → AND = 1 → ML0 HIGH. Why this step? Every position is masked, so the wildcard row **** lets this key through.
Part 2 — key 1111: again every $M_{i} = 1$ forces match $_{i} = 1$ → ML0 HIGH. Why this step? A fully-masked row is a wildcard that matches all $2^{4} = 16$ keys — this is the always-on default route in routers.
Encoder. In Part 2 the wildcard row's line never drops, so for any key it emits address 0. Why this step? A permanently-HIGH line is a permanent candidate; routers place such a default at lowest priority so specific rows can override it.

Verify: Part 1 — 0000 equals R0 (0000) but not R1 (1010), so exactly one match, not all. Part 2 — the mask rule predicts HIGH for both 0110 and 1111, i.e. all 16 keys match. The two degenerate inputs behave oppositely: zero key is ordinary; all-masked storage is a wildcard. ✓

Cell E — Single-bit near miss

Worked example Example 5 — off by exactly one bit

BCAM store R0=10110, R1=10010. Search key $S =$ 10100. (5-bit words; bit0 = leftmost, bit4 = rightmost.) Forecast: R0 and R1 each differ from 10100. Will either squeak through?

R0 10110 vs 10100. Scan bit0 1=1, bit1 0=0, bit2 1=1, then bit3 1 vs 0 → one disagreement → its tap fires → ML0 LOW. Why this step? CAM has no notion of "close" — this single wrong bit is as fatal as ten, because the wired-OR discharges the whole line the instant any tap fires.
R1 10010 vs 10100. Scan finds bit2 0 vs 1 and bit3 1 vs 0 disagree → taps fire → ML1 LOW. Why this step? Two disagreements only reinforce the miss; even one would already have killed the row, so R1 is out.
Encoder. No line HIGH → asserts the no-match (miss) flag. Why this step? With zero HIGH lines the encoder has no valid index to emit, so — exactly as in Example 2 — it raises the dedicated miss wire.

Verify: 10100 is not equal to 10110 (differ at bit3) nor to 10010 (differ at bits 2,3). Exact-match hardware must reject both → zero matches confirmed. (If you wanted "nearest" matches you'd need a Hamming-distance CAM, a different, costlier beast.) ✓

Cell F — TCAM don't-care in the stored word

Worked example Example 6 — stored

$X$ absorbs both 0 and 1 A TCAM row stores $D =$ 1X0X (bits 1 and 3 are don't-care, i.e. $M =$ 0101). Two searches: $S_{a} =$ 1100 and $S_{b} =$ 1001. (bit0 = leftmost.) Forecast: Should both keys match this single stored pattern?

Search $S_{a} =$ 1100 with $M =$ 0101.
- bit0: $M = 0$ , compare $1 ⊙ 1 = 1$ ✓
- bit1: $M = 1$ → match $_{1} = 1$ (don't-care) ✓
- bit2: $M = 0$ , compare $0 ⊙ 0 = 1$ ✓
- bit3: $M = 1$ → match $_{3} = 1$ ✓ → AND = 1 → MATCH. Why this step? Only the unmasked bits (0 and 2) are enforced; the masked bits pass automatically, so 1100 fits the pattern.
Search $S_{b} =$ 1001 with same row.
- bit0: $1 ⊙ 1 = 1$ ✓; bit1: masked ✓; bit2: $0 ⊙ 0 = 1$ ✓; bit3: masked ✓ → MATCH. Why this step? 1001 also fixes bit0=1 and bit2=0, so it too fits — proving the pattern 1X0X names a set of keys, not one.
Now $S_{c} =$ 1010 — bit2: $D = 0$ vs $S = 1$ , $M = 0$ → $0 ⊙ 1 = 0$ → one hard bit fails → NO MATCH. Why this step? Violate one enforced (unmasked) bit and its tap fires, killing the row no matter how many masked bits agreed.

Verify: The pattern 1X0X covers exactly ${1000, 1001, 1100, 1101}$ . $S_{a} = 1100$ ✓, $S_{b} = 1001$ ✓ are in the set; $S_{c} = 1010$ ✗ is not. Predictions match membership. ✓

Cell G — TCAM masked search key (global search mask)

Worked example Example 7 — ignore chosen bit positions during the search

BCAM-style store R0=110010, R1=100110, R2=110110. We search $S =$ 110110 with a global search mask $G =$ 000110, meaning "ignore bits 3 and 4". (6-bit words; bit0 = leftmost, bit5 = rightmost.) Forecast: With bits 3–4 ignored, which rows survive?

Write the per-bit rule for this search: $match_{i} = G_{i} + (\overline{G_{i}} \cdot (D_{i} ⊙ S_{i}))$ ; with $G =$ 000110 this forces match $_{3}$ =match $_{4}$ =1 and enforces genuine agreement on bits {0,1,2,5}. Why this step? The global mask lets one query find a family of stored words; writing the rule first tells us exactly which positions are still checked.
R0 110010: enforced bits {0,1,2,5} give 1,1,0,0; key gives 1,1,0,0 → all agree, masked bits pass → MATCH. Why this step? Every enforced bit agrees and bits 3,4 are gated by $G$ , so nothing fires the tap.
R1 100110: enforced bits give 1,0,0,0; key gives 1,1,0,0 → bit1 differs → NO MATCH. Why this step? Bit1 is not masked ( $G_{1} = 0$ ), so its disagreement is enforced and fires the tap.
R2 110110: enforced bits give 1,1,0,0 = key → MATCH. Why this step? A second, different stored word satisfies the same reduced query — the masked search deliberately accepts a family, so multi-match is expected.
Encoder (lowest index) → output 0. Why this step? R0 and R2 both stay HIGH, another multi-match tie; the deterministic lowest-index rule picks R0.

Verify: Reduce all words to bits {0,1,2,5}: R0→1100, R1→1000, R2→1100, key→1100. Matches are R0 and R2 (both 1100), R1 (1000) misses. Lowest index → 0. ✓

Cell H — Longest-prefix routing (the real-world one)

Worked example Example 8 — most specific prefix wins

A router TCAM (we use 8-bit "IPs" to keep it readable). Entries, longer prefix = more specific:

R0: 1010**** (prefix /4) → port P0
R1: 101011** (prefix /6) → port P1
R2: 10101100 (prefix /8, a full host) → port P2 Incoming address $S =$ 10101101. (8-bit; bit0 = leftmost.) Forecast: Which ports match, and which one is actually chosen?

R0 1010**** vs 10101101. First 4 bits 1010 = key's first 4 bits 1010 ✓; rest masked → MATCH. Why this step? The /4 prefix only enforces 4 bits; all of them agree, so R0's line stays HIGH.
R1 101011** vs 10101101. First 6 bits 101011 = key's 101011 ✓; last 2 masked → MATCH. Why this step? The /6 prefix enforces 6 bits, all agree, so R1 also stays HIGH — two prefixes are consistent with this address.
R2 10101100 vs 10101101. All 8 bits compared; bit7: 0 vs 1 → mismatch → NO MATCH. Why this step? A full host demands an exact 8-bit hit; the final bit differs, so its tap fires and R2 drops out.
Priority = longest prefix. Rows are physically ordered so the longest matching prefix has highest priority; R1 (/6) beats R0 (/4) → output port P1. Why this step? Longest-prefix routing sends the packet by the most specific rule; see Longest Prefix Matching. The Priority Encoder enforces that order.

Verify: Matching set = {R0, R1}. Prefix lengths 4 and 6 → longest is 6 → R1 → port P1. R2 correctly excluded by its last bit. ✓

Cell I — Limiting behaviour (what " $O (1)$ " really means)

Worked example Example 9 — does bigger memory mean slower search?

A CAM has $R$ rows of $n$ bits. Compare the search time and the energy per search as we grow $R$ from 1k → 1M rows (keeping $n = 32$ ). Forecast: Which stays constant, which grows?

Search time. All $R$ match lines are precharged and evaluated in parallel in one cycle, so adding rows adds parallel hardware, not sequential steps → time stays $O (1)$ (constant number of cycles). Why this step? Parallelism is the whole point: every row checks itself simultaneously (the wired-OR does the work — see Dynamic Logic (Precharge/Evaluate)).
The fine print. In practice a longer match line and a bigger priority encoder add a small propagation delay $\propto lo g R$ or a wire-RC term. Why this step? Real wires and gates have finite speed, so " $O (1)$ " means cycle count, not literal zero growth — still vastly better than $O (R)$ sequential reads.
Energy per search. Every search precharges every match line, so switched charge (and thus energy) scales linearly: $E \propto R \cdot n$ . Why this step? Each of the $R$ lines is a capacitor charged to $V$ then (often) discharged; total switched charge grows with the number of lines, which is why CAM is power-hungry.

Verify: Going 1k→1M rows multiplies rows by $1 0^{3}$ : search cycles unchanged (still 1), energy per search up by $\approx 1 0^{3}$ . That linear power blow-up is exactly why the parent warns "CAM is power-hungry, use only where needed." ✓

Cell J — Exam twist (encoder + power reasoning)

Worked example Example 10 — count matches, pick the address, estimate relative power

A 6-row BCAM stores: R0=0011, R1=1100, R2=0011, R3=0011, R4=1010, R5=0011. Search $S =$ 0011. (bit0 = leftmost.) Forecast: (a) how many match lines fire? (b) what address is output? (c) if one search costs energy proportional to total match lines charged, how does this compare to a 6-row RAM read?

(a) Find matching rows. Compare 0011 to each: R0=0011 ✓, R1=1100 (bit0 differs) ✗, R2=0011 ✓, R3=0011 ✓, R4=1010 (bit1 differs) ✗, R5=0011 ✓ → matching rows R0, R2, R3, R5, i.e. four lines fire. Why this step? Duplicate 0011 entries each independently keep their wired-OR line HIGH, so multiple lines fire at once — the multi-match case again, now at scale.
(b) Encoder output. Among the HIGH lines {0,2,3,5}, lowest-index-wins → output address 0. Why this step? The encoder must return exactly one address; its deterministic priority rule breaks the four-way tie by choosing the smallest index.
(c) Relative power. All 6 match lines were precharged regardless of how many matched, so charge $\propto 6$ lines, whereas a RAM read activates essentially 1 addressed row → CAM burns roughly 6× the per-access energy of a single RAM read. Why this step? CAM pays to interrogate every row on every search (precharge cost is independent of the match count); RAM touches only the addressed one — the exact area/power price the parent flags for "search all at once".

Verify: Number of matches = count of rows equal to 0011 = 4. Encoder output = min(0,2,3,5) = 0. Lines charged = 6 (all rows) → ≈ 6× a single RAM read. ✓

Recall Quick self-test on the matrix

Which case class is "a search key of all zeros"? ::: An ordinary key (Cell D, Part 1) — it matches only rows storing 0000, it does NOT match everything. Only masked storage matches everything. If three rows match, which address is returned? ::: The priority encoder's chosen one — lowest index by default, longest prefix in routing TCAMs. Does doubling the row count double the search time? ::: No — search stays $O (1)$ cycles (parallel). It roughly doubles the energy per search. Can a stored 1X0X match 1010? ::: No — bit2 is an enforced 0 but the key has 1 there; a hard-bit mismatch kills it. In our convention, which end is bit0? ::: The leftmost bit. What does "wired-OR" compute on the match line? ::: The OR of all bit-mismatches — any single mismatching cell can drain the shared precharged line to LOW.