Content-addressable memory (CAM)

WHY does CAM exist?

The classic killer app: a router's forwarding table. A packet arrives, you must instantly know which output port matches its destination IP. Sequential search is far too slow for line-rate networking — so routers use CAM.

WHAT exactly is CAM?

Two flavours:

HOW is it built? (Derivation from first principles)

We build CAM up from the humble comparison of one bit, then a word, then the whole array.

Step 1 — Compare one bit

We want a signal that says "stored bit $D$ ≠ search bit $S$". The logic function for inequality of two bits is XOR:

$\text{mismatch} = D \oplus S$

Why this step? Because a match requires every bit to agree. It's easier to build a circuit that detects disagreement and pulls a shared wire, than to AND together thousands of agreements.

Step 2 — The shared Match Line (ML)

Every cell in a row is wired to a single match line (ML), which is precharged HIGH before the search. Each cell contains a transistor path that discharges the ML to LOW if that bit mismatches.

So for a word of $n$ bits, the match line stays HIGH only if no bit discharges it:

$\text{ML}_{\text{row}} = \overline{\bigvee_{i=0}^{n-1} (D_i \oplus S_i)} = \bigwedge_{i=0}^{n-1}\overline{(D_i \oplus S_i)} = \bigwedge_{i=0}^{n-1}(D_i \odot S_i)$

where $\odot$ is XNOR (equality). This is just De Morgan: "NOT (any mismatch)" = "all bits equal".

Why this step? The wired-OR on ML is the trick that makes search parallel: one shared wire per row, and any single disagreeing cell can single-handedly kill the match. No adder or comparator tree needed — physics does the OR for free.

Step 3 — The full array + encoder

• $R$ rows, each an $n$-bit word, each with its own match line $\text{ML}_r$.
• All match lines are searched simultaneously — one comparison cycle for the whole memory.
• A priority encoder converts the (possibly many) HIGH match lines into a single output address (the highest-priority / lowest-index match).

$\text{search time} \ \propto\ O(1)\quad\text{(independent of } R,n\text{ in principle)}$

Worked examples

Common mistakes (steel-manned)

Where CAM is actually used

Active-recall flashcards

#flashcards/hardware

Connections

• Static RAM (SRAM) — CAM cell = SRAM storage + comparison logic
• Cache Memory — fully-associative caches use CAM for tag matching
• Translation Lookaside Buffer (TLB) — associative address translation
• Priority Encoder — resolves multiple simultaneous matches
• Boolean Algebra & De Morgan's Laws — match-line = NOT(OR of mismatches) = AND of equalities
• Longest Prefix Matching — TCAM + priority for IP routing
• Dynamic Logic (Precharge/Evaluate) — the electrical style of the match line

Concept Map

Hinglish (regional understanding)