Content-addressable memory (CAM): Visual walkthrough

We assume you know nothing. We will define every symbol the moment we use it.

Step 1 — Name the two bits we compare

WHAT. Inside a CAM there are two kinds of bits sitting side by side in every tiny cell:

$D$ — the stored data bit. This is the bit already living inside the memory (the "D" is for Data). It never changes during a search.
$S$ — the search bit. This is the bit you send in when you ask your question. ( $S$ for Search.)

Each is either $0$ or $1$ . Nothing more.

WHY. Before we can talk about "does a whole word match?", we must be crystal-clear on the smallest possible comparison: one stored bit against one search bit. Everything else is thousands of copies of this.

PICTURE. Below, the green box is the stored bit $D$ , the blue box is the search bit $S$ . The four possible pairings are laid out. Two agree (a match), two disagree (a mismatch).

Step 2 — Build a signal that fires on disagreement (XOR)

WHAT. We want one output bit — call it $m$ (for mismatch) — that is $1$ exactly when $D$ and $S$ disagree, and $0$ when they agree. Reading off the table in the figure above:

$m = D \oplus S$

Here $\oplus$ is the symbol for XOR ("exclusive OR"). Read it as: "one or the other, but not both." Term by term:

$D$ — the stored bit sitting to the left of $\oplus$ .
$\oplus$ — the operator: output $1$ when its two inputs differ.
$S$ — the search bit on the right.

WHY this tool and not another? We could have looked for agreement instead. But think about what a whole word needs: it matches only if every single bit agrees. Detecting "did anybody disagree?" turns out to be far cheaper in hardware than "did everybody agree?" — because a single disagreement can act on its own to spoil the match, without waiting for the others. XOR is precisely the gate whose output is "these two bits disagree." That's why we reach for XOR here and not, say, AND.

PICTURE. The truth table drawn as a little machine: two inputs in, one $m$ wire out, glowing red only on the two disagreeing rows.

Step 3 — One shared wire per row: the Match Line

WHAT. Take a whole word of $n$ bits (say $n = 4$ : bits $D_{0} D_{1} D_{2} D_{3}$ ). Run one single wire across all $n$ cells in that row. Call it the match line, written $ML$ . Before the search, we force this wire to be HIGH (logic $1$ ) — this is called precharge.

Now wire each cell so that if its bit mismatches, it connects the match line to ground and drains it to LOW ( $0$ ).

WHY. This is the whole trick of CAM. Instead of building a comparator that gathers up $n$ answers and combines them, we let the wire itself do the combining. Any one cell that disagrees can single-handedly pull the shared wire down. It's like a string of Christmas lights on one fuse: one broken bulb kills the whole strand. This is called a wired-OR — the wire physically computes "did any cell mismatch?" for free. See Dynamic Logic (Precharge/Evaluate) for the precharge-then-discharge style.

PICTURE. Four cells hanging off one horizontal match line. Each cell has a little switch (transistor) to ground. A green cell (match) leaves its switch open; a red cell (mismatch) closes its switch and the whole line drains down to LOW.

Step 4 — Write the row-match equation and read every symbol

WHAT. The match line stays HIGH only if no cell drained it — i.e. only if no bit mismatched. In logic:

$ML_{row} = \overline{⋁_{i = 0}^{n - 1} (D_{i} \oplus S_{i})}$

Let's read this term by term, left to right:

$ML_{row}$ — the value on the match line: $1$ = matched, $0$ = no match.
$⋁_{i = 0}^{n - 1}$ — a big OR over all bit positions $i$ from $0$ to $n - 1$ . It asks: "is there at least one $i$ where...?"
$(D_{i} \oplus S_{i})$ — our mismatch signal $m_{i}$ from Step 2, for bit $i$ .
The overline $\overline{\dots}$ — logical NOT: flip the result.

So in plain words: $ML = NOT (any bit mismatched) = "all bits agreed."$

WHY. We phrased the row-match as "not any mismatch" because that mirrors the hardware exactly: the wired-OR physically computes "any mismatch?", and the precharged-HIGH-then-drained wire physically computes the NOT (HIGH becomes the absence of a drain).

PICTURE. The OR-then-NOT drawn as a funnel: all four mismatch signals pour into one OR, whose output is inverted to give ML.

Step 5 — Flip it with De Morgan: "all bits equal"

WHAT. The formula from Step 4 hides a beautiful equivalent form. Using De Morgan's law (see Boolean Algebra & De Morgan's Laws) — "NOT of an OR equals the AND of the NOTs" — we push the overline inside:

$ML_{row} = ⋀_{i = 0}^{n - 1} \overline{(D_{i} \oplus S_{i})} = ⋀_{i = 0}^{n - 1} (D_{i} ⊙ S_{i})$

Term by term:

$⋀_{i = 0}^{n - 1}$ — a big AND over all bits: "is it true for every $i$ ?"
$\overline{(D_{i} \oplus S_{i})}$ — NOT-of-XOR. XOR fires on disagreement, so its NOT fires on agreement. This gate has its own name: XNOR, symbol $⊙$ .
$D_{i} ⊙ S_{i}$ — the equality of bit $i$ : it is $1$ when $D_{i} = S_{i}$ .

So the same match line is equivalently: AND of all the per-bit equalities — "every bit is equal."

WHY. De Morgan lets us switch freely between the hardware view ("nobody drained the wire") and the human view ("all bits equal"). Both are the same silicon; De Morgan is the proof they're identical, so you can reason with whichever is clearer.

PICTURE. Left panel: the mismatch/OR/NOT view. Right panel: the equality/AND view. An "=" between them, with De Morgan named on the bridge.

Step 6 — Stack the rows: parallel search over the whole array

WHAT. A CAM has $R$ rows, each an $n$ -bit word, each with its own match line $ML_{0}, ML_{1}, \dots, ML_{R - 1}$ . The same search word $S$ is broadcast down every column to all rows at once. Every row runs its own Step-5 computation simultaneously.

WHY. Nothing waits for anything else. Row 5 doesn't need row 4's answer. All $R$ wired-OR wires drain (or don't) in the same instant. That is why:

$search time \propto O (1) (independent of R and n)$

Here $O (1)$ is computer-science shorthand for "constant time — doesn't grow as the table grows." Contrast a normal search over $R$ rows, which is $O (R)$ .

PICTURE. The full grid: $R$ match lines running horizontally, search columns running vertically, every row lighting its ML at the same time. Two rows go green (match), the rest go gray.

Step 7 — Edge case: many matches → the priority encoder

WHAT. Multiple rows can be HIGH at once (duplicate entries, or many TCAM prefixes in Longest Prefix Matching). But the CAM must output one address. A Priority Encoder takes the bundle of match lines and returns the address of the highest-priority (usually lowest-index) matching row.

WHY. A raw pile of "these rows matched" isn't an address — the encoder collapses it into a single number, deterministically, so ties never leave the output undefined.

PICTURE. Three match lines HIGH; the priority encoder picks the top one and emits its binary address; the losers are shown grayed.

Step 8 — Degenerate case: the don't-care bit (TCAM)

WHAT. In a Ternary CAM a cell can store a third state: $X$ , "don't-care." We add a per-bit mask $M_{i}$ . The masked per-bit match becomes:

$match_{i} = M_{i} + (D_{i} ⊙ S_{i})$

Term by term:

$M_{i}$ — the mask bit: $M_{i} = 1$ means "this position is a don't-care."
$+$ — logical OR.
$(D_{i} ⊙ S_{i})$ — the ordinary equality from Step 5.

So if $M_{i} = 1$ , the whole thing is $1$ regardless of $D_{i}, S_{i}$ — the bit always matches. If $M_{i} = 0$ , it falls back to plain equality.

WHY. This is what lets one CAM row match a whole range of search words — the foundation of IP prefix matching (192.168.*.*). The don't-care bits simply refuse to drain the match line.

PICTURE. A 4-cell row where bit 2 is masked ( $X$ ): search bits $0$ and $1$ both leave the line HIGH at that position; the other cells still enforce equality.

The one-picture summary

Everything above, compressed: one search bit meets one stored bit (Step 1–2) → mismatch drains a shared wire (Step 3) → row-match is "no drain" = "all bits equal" (Step 4–5) → all rows do this at once (Step 6) → a priority encoder names the winner (Step 7) → a mask bit adds don't-cares (Step 8).

Recall Feynman retelling — say it plainly

Picture a long row of light bulbs wired to a single string, and we start by turning the whole string ON (that's precharge). Every bulb has a tiny guard sitting under it. Your search word walks past and whispers a bit to each guard. If the guard's own stored bit disagrees, the guard yanks a cord and shorts the string to the floor — the whole string goes dark. So the string stays lit only if every single guard agreed — that's a matching row. Now stack thousands of such strings on top of each other and shout the search word to all of them in the same breath: every string decides for itself in the same instant, so it doesn't matter if there are ten strings or ten million — the answer arrives in one tick. Some strings might stay lit at once (duplicates, or wildcard rows where a guard was told "don't care, always agree"). A little referee — the priority encoder — points at the top lit string and reads out its seat number. That seat number is your answer: not the data, but where the data lives.

Recall Quick self-check

Which gate detects one-bit disagreement, and which equivalent gate detects agreement? ::: XOR ( $\oplus$ ) detects disagreement; XNOR ( $⊙$ ) detects agreement. They are NOTs of each other. Why does one mismatching cell kill the whole row? ::: All cells share one precharged match line (wired-OR); any cell can drain it to LOW on its own. How does De Morgan connect the two forms of the ML equation? ::: NOT(OR of mismatches) = AND of NOT-mismatches = AND of equalities. What makes a TCAM cell always match at a bit position? ::: A set mask bit $M_{i} = 1$ , since $match_{i} = M_{i} + (D_{i} ⊙ S_{i})$ .