4.1.13 · D5Memory Technologies
Question bank — Content-addressable memory (CAM)
Before we start, a short refresher on every symbol and picture this page leans on, so nothing appears un-earned.
The three notations you must read fluently
Three symbols appear in the formulas below. Read them slowly here once, then the rest of the page is plain English.
Look at the four building blocks before you read any equation:
The left pair are the per-bit detectors ( = differ, = agree). The right pair remind you what "OR a list" and "AND a list" evaluate to.
Why disagreement, and why a wired-OR — from first principles
Why NOT sews through an OR to give an AND of XNORs
Why precharge-HIGH then conditionally discharge is optimal
True or false — justify
CAM is simply RAM with the read direction reversed.
True in spirit: RAM maps address→data, CAM maps data→address, so it is the inverse lookup — but physically CAM adds a comparator to every cell, so it is not "the same chip wired backwards."
If a search key matches no stored word, the match lines are in an undefined state.
False. Every match line was precharged HIGH; if nothing matches, each row has at least one mismatching bit that discharges its line, so all match lines correctly read LOW.
A single mismatching bit anywhere in a row is enough to make that whole row report "no match."
True. The mismatches are wired-OR onto one match line, so one disagreeing cell pulls the shared wire LOW regardless of how many other bits agreed.
In a binary CAM (BCAM) at most one row can ever match a given key.
False. Duplicate stored words all match the same key, so several match lines can be HIGH at once — which is exactly why a Priority Encoder is required.
The don't-care value in a TCAM is a third data value the CPU can read back later.
False. is a matching property encoded by a mask bit; it says "ignore this position during search," and is never returned as stored data.
CAM performs its search in time because it uses a very fast sequential comparator.
False. The speed is parallel, not fast-sequential: every row compares itself in the same clock cycle, so wall-clock time does not grow with the number of rows.
Because CAM search is , it is strictly better than RAM and should replace it everywhere.
False. Each CAM cell costs ~9–16 transistors versus 1T DRAM / 6T SRAM, and every search charges every match line, so CAM is large, hot, and expensive — used only where parallel search pays off.
The equation is just a restatement of De Morgan's law.
True. "NOT(any bit mismatches)" equals "all bits match"; pushing the NOT through the big-OR turns it into a big-AND and flips each XOR into an XNOR — see Boolean Algebra & De Morgan's Laws.
Precharging the match line HIGH is optional; you could instead precharge LOW and pull matched lines HIGH.
False in practice. Pulling matched lines HIGH would need active drivers that already know the answer, which is slower; precharge-HIGH-then-conditionally-discharge is the fast dynamic-logic style CAM depends on.
A TCAM row storing all don't-cares matches every possible search key.
True. Every bit position is masked, so no cell can ever discharge the line — this is the "default route" trick in routers.
The XOR gate detecting mismatch could be replaced by an XNOR gate feeding the same wired-OR line.
False. Wired-OR discharges on a HIGH; you need the gate to go HIGH on disagreement (XOR), so swapping to XNOR would discharge on every agreement and invert the whole logic.
Spot the error
"CAM stores the address you want in a special register, then reads the data at that address."
Wrong: that describes ordinary RAM addressing. CAM takes data in and produces the address as output; nothing tells it the address beforehand.
"To search, first drive every match line LOW, then let matched cells charge their line up."
Wrong: lines are precharged HIGH and mismatches discharge them. Charging matched lines up would require knowing which rows match before searching — a chicken-and-egg problem.
"A TCAM needs the same ~6 transistors per cell as SRAM."
Wrong: TCAM needs to encode three states (0/1/X) and to do masked comparison, costing ~16 transistors — roughly two storage bits plus compare logic per cell.
"With two matching rows the CAM outputs both addresses simultaneously on the output bus."
Wrong: a single address bus cannot carry two addresses. The Priority Encoder collapses the multiple HIGH match lines into one chosen address (usually lowest index / highest priority).
"In longest-prefix matching the router picks whichever prefix matched first in the table."
Wrong: it must pick the longest (most specific) matching prefix; the encoder priority is arranged so longer prefixes win, not table position by accident. See Longest Prefix Matching.
"A fully-associative cache avoids CAM because comparing all tags at once would be too slow."
Wrong: a fully-associative cache is a CAM on the tags — comparing all tags at once is precisely what makes it fully associative, at the cost of power and area (see Cache Memory).
"The row-match formula uses XOR () to mean equality, since equal bits give the same value."
Wrong: XOR outputs on difference. Equality is XNOR (); the row match is the AND of XNORs, or equivalently NOT(OR of XORs).
Why questions
Why does CAM detect disagreement per cell rather than directly computing agreement?
Because a shared wired-OR match line is trivial to pull LOW on any mismatch, letting physics do the "any-bit-differs" OR for free — building a big AND-of-agreements tree would need extra gates and a slow series path.
Why can multiple rows legitimately match at once even in an exact-match BCAM?
Because duplicate entries store identical words, so a key equal to that word makes every copy's match line stay HIGH — the encoder then breaks the tie.
Why is a Priority Encoder logically necessary and not just a convenience?
Because the raw output is a set of match lines, and downstream logic (a port number, a physical frame) needs exactly one address — the encoder makes the answer deterministic.
Why does the don't-care bit help IP routing but not a plain dictionary lookup?
Because IP prefixes deliberately leave the host portion unspecified (
192.168.*.*), and matches both and there; an exact dictionary lookup has no positions it wants to ignore.Why is CAM described as power-hungry even for a search that finds nothing?
Because every match line is precharged and, on a miss, every row discharges — energy is spent charging thousands of lines each cycle regardless of the result.
Why does a Translation Lookaside Buffer (TLB) use CAM instead of a lookup table indexed by page number?
A virtual page number space is huge and sparse; indexing directly would need an impossibly large table, so CAM searches only the resident entries in parallel by content.
Why is the mask term written as using OR?
Because is the mask bit ("ignore this position") and is logical OR: setting forces the whole term HIGH regardless of , so a masked (don't-care) position can never discharge the line.
Edge cases
What happens if the search key equals no stored word at all?
Every match line discharges to LOW; the encoder signals "no match" (often via a separate match-found flag), and no address is asserted.
What happens if a BCAM has two identical stored words and you search for it?
Both rows' match lines stay HIGH; the priority encoder deterministically returns the higher-priority (typically lower-index) address, silently ignoring the other.
What does a TCAM row of all don't-cares do to search results?
It matches every key, so it always contributes a HIGH match line — used intentionally as a catch-all/default rule at lowest priority.
What is the match result when the search key is longer or shorter than the stored word width?
It cannot happen validly — CAM word width is fixed by hardware; the key is padded/truncated to that width before search, and mismatched framing simply yields whatever those fixed bits compare to.
If a glitch discharges a match line mid-search, what does the row report?
A false "no match" — the dynamic match line has no way to distinguish a real mismatch from noise, which is why precharge/evaluate timing and shielding matter in CAM design.
In a TCAM, what if two prefixes of the same length both match one address?
That is a configuration error (overlapping equal-length rules); the encoder still picks one by priority, but the table should be built so equal-length prefixes are mutually exclusive.
What is the match-line state for a row where some bits are don't-care and the rest disagree with the key?
NO match — masking only excuses the don't-care positions; any unmasked bit that disagrees still discharges the line.
Recall One-line self-test
RAM: address in, data out. CAM: what in, what out? ::: Data (search key) in, address out — the inverse mapping, computed in parallel across all rows.