Foundations — Content-addressable memory (CAM)

This page is a toolbox check. Before you read the parent note CAM topic note, every symbol, gate, and idea it uses gets built here from the ground up — no prior notation assumed. If a smart 12-year-old can follow line one, we did our job.

The starting picture: a wall of labelled boxes

Memory — any memory — is a row of boxes. Each box holds some bits and each box has a number (its address).

Everything below exists to make that reverse arrow happen in parallel. Prerequisite ideas from Static RAM (SRAM) (how one bit is stored) sit underneath this whole page.

Symbol 1 — a single bit and what "$0$" / "$1$" mean

We will use two bits constantly:

• $D$ — the stored bit sitting inside a memory cell (the "D" is for Data).
• $S$ — the search bit you are looking for (the "S" is for Search).

Why give them different letters? Because the entire job of a CAM cell is to ask "is my stored $D$ the same as your incoming $S$?" — we must be able to name the two things we compare.

Symbol 2 — comparing two bits: same or different?

There are only four possible pairs of $(D,S)$. Let's tabulate whether they agree:

Two useful signals fall right out of this table, and they are exact opposites of each other.

Why do we need both? A row matches only when every bit agrees. Later we'll see it's cheaper in hardware to hunt for disagreement (XOR) and let any single disagreement veto the match — so XOR is the workhorse, and XNOR ($D\odot S$) is the tidy way to write "this bit agrees."

Symbol 3 — the bar, the wedge, the vee: NOT, AND, OR

The parent note writes a scary-looking line:

$\text{ML}=\overline{{\bigvee }_i(D_i\oplus S_i)}={\bigwedge }_i\overline{(D_i\oplus S_i)}$

Let's disarm every symbol.

The subscript $i$ is just a counter naming the bit position: $D_0$ is bit 0, $D_1$ is bit 1, and so on. In a full array we add a second subscript $r$ for the row: $D_{r,i}$ = the $i$-th bit of the word stored in row $r$.

Symbol 4 — De Morgan's Law: why "no mismatch" = "all match"

That double-equals in the parent's formula is not magic; it is one rule.

Apply it to the match line:

$\overline{{\bigvee }_i(D_i\oplus S_i)}={\bigwedge }_i\overline{(D_i\oplus S_i)}={\bigwedge }_i(D_i\odot S_i)$

Read left to right: "NOT (any bit mismatches)" becomes "every bit does-not-mismatch" becomes "every bit is equal." That last equality uses $\overline{D\oplus S}=D\odot S$ — NOT-XOR is XNOR. This is the single most important algebraic move in the whole topic, and it comes straight from Boolean Algebra & De Morgan's Laws.

Symbol 5 — the Match Line and "precharge / discharge"

The subscript version ${\text{ML}}_r$ just names the match line of row $r$.

Symbol 6 — the $X$ don't-care and the mask bit $M$

The per-bit TCAM rule is:

${\text{match}}_i=M_i\vee (D_i\odot S_i)$

Read it: "bit $i$ counts as matched if it is masked ($M_i=1$), or if it genuinely equals the search bit." A memory built from these — where each cell stores $0$, $1$, or $X$ — is a Ternary CAM (TCAM), the engine behind Longest Prefix Matching in routers.

Symbol 7 — the priority encoder and $O(1)$

How the pieces feed the topic

Equipment checklist

Test yourself — reveal only after answering out loud.

Ready? Now open the parent note CAM topic note and every symbol will already be an old friend.