CAM — Content Addressable Memory Verilog: Binary, Ternary, TLB

Q: What is Content Addressable Memory (CAM)?

A CAM (Content Addressable Memory) is a special memory that is searched by content rather than by address. You provide a search key (data), and the CAM returns the address(es) of matching entries in a single clock cycle. This is the opposite of normal RAM where you provide an address to get data.

Q: What is the difference between binary CAM and ternary CAM?

A binary CAM (BCAM) stores exact bit patterns and returns a match only for an exact comparison. A ternary CAM (TCAM) stores three-valued data: 0, 1, and X (don't-care). During search, an X bit matches both 0 and 1, enabling wildcard or prefix matching. TCAMs are used in network routing tables where IP subnet masks are don't-cares.

Q: What is a match line in a CAM?

A match line is a wire that is initially precharged high. For each bit in a CAM row, a compare cell pulls the match line low if the search key bit differs from the stored bit. If all bits match (and no cell pulls the line low), the match line stays high, indicating a hit for that row. In VLSI, match lines are implemented as differential bit cells for speed.

Q: How does a priority encoder work in a CAM?

A CAM can have multiple matching rows. A priority encoder takes the match vector (one bit per row) and outputs the index of the highest-priority (usually lowest-index) matching row. This converts the parallel match result into a single address that can index a parallel data RAM to retrieve associated data.

Q: Where are TCAMs used in practice?

TCAMs are used in network routers for longest-prefix match (LPM) routing — the don't-care bits represent subnet masks. Other uses: firewall ACL lookup, TLB (Translation Lookaside Buffer) for virtual-to-physical address translation, cache tag comparison, and network classification (5-tuple flow matching).

What is Content Addressable Memory?

Normal RAM: you provide an address, you get data. A CAM reverses this: you provide data (the search key), and the CAM returns the address of the matching row — in a single clock cycle, regardless of depth.

Binary CAM (BCAM)

Each row stores an exact N-bit pattern. A search compares the key against all rows simultaneously. The match vector has a 1 at positions that match the key exactly.

Verilog — Binary CAM (8-entry, 8-bit key)

module bcam #(
  parameter DEPTH  = 8,    // number of entries
  parameter KEY_W  = 8     // key width in bits
)(
  input  wire              clk,
  // Write port
  input  wire              we,
  input  wire [$clog2(DEPTH)-1:0] waddr,
  input  wire [KEY_W-1:0]  wkey,
  // Search (combinational)
  input  wire [KEY_W-1:0]  skey,       // search key
  output reg  [DEPTH-1:0]  match,      // one-hot match vector
  output wire              hit,        // any match found
  // Priority-encoded first match
  output wire [$clog2(DEPTH)-1:0] match_addr
);
  reg [KEY_W-1:0] cam [0:DEPTH-1];
  reg [DEPTH-1:0] valid;              // valid bit per entry

  integer i;

  // Synchronous write
  always @(posedge clk) begin
    if (we) begin
      cam[waddr]   <= wkey;
      valid[waddr] <= 1'b1;
    end
  end

  // Combinational search — compare key against all rows
  always @(*) begin
    for (i = 0; i < DEPTH; i = i+1)
      match[i] = valid[i] && (cam[i] == skey);
  end

  assign hit = |match;   // OR-reduce: 1 if any row matched

  // Priority encoder: lowest matching row index
  assign match_addr = priority_enc(match);

  function automatic [$clog2(DEPTH)-1:0] priority_enc;
    input [DEPTH-1:0] m;
    integer j;
    begin
      priority_enc = 0;
      for (j = DEPTH-1; j >= 0; j = j-1)
        if (m[j]) priority_enc = j[$clog2(DEPTH)-1:0];
    end
  endfunction
endmodule

Ternary CAM (TCAM)

Each row stores two arrays: data[] and mask[]. A bit with mask=0 is a don't-care (X) — it matches both 0 and 1. A bit with mask=1 must match exactly. This enables wildcard and prefix matching used in routing tables.

TCAM match condition per bit: match_bit = (mask == 0) || (data == key_bit). Row matches only when all bits match.

Verilog — Ternary CAM (TCAM)

module tcam #(
  parameter DEPTH = 8,
  parameter KEY_W = 8
)(
  input  wire              clk,
  // Write
  input  wire              we,
  input  wire [$clog2(DEPTH)-1:0] waddr,
  input  wire [KEY_W-1:0]  wdata,    // pattern bits
  input  wire [KEY_W-1:0]  wmask,    // 1=compare, 0=don't-care
  // Search
  input  wire [KEY_W-1:0]  skey,
  output reg  [DEPTH-1:0]  match,
  output wire              hit,
  output wire [$clog2(DEPTH)-1:0] match_addr
);
  reg [KEY_W-1:0] tdata [0:DEPTH-1];   // stored patterns
  reg [KEY_W-1:0] tmask [0:DEPTH-1];   // compare masks
  reg [DEPTH-1:0] valid;

  integer i;

  always @(posedge clk) begin
    if (we) begin
      tdata[waddr] <= wdata;
      tmask[waddr] <= wmask;
      valid[waddr] <= 1'b1;
    end
  end

  // Ternary compare: bit matches if mask=0 (X) OR data bit == key bit
  always @(*) begin
    for (i = 0; i < DEPTH; i = i+1)
      match[i] = valid[i] &&
                 (((tdata[i] ^ skey) & tmask[i]) == {KEY_W{1'b0}});
      // XOR finds differing bits; AND with mask zeroes don't-cares;
      // all-zero means full match
  end

  assign hit = |match;

  assign match_addr = priority_enc(match);

  function automatic [$clog2(DEPTH)-1:0] priority_enc;
    input [DEPTH-1:0] m;
    integer j;
    begin
      priority_enc = 0;
      for (j = DEPTH-1; j >= 0; j = j-1)
        if (m[j]) priority_enc = j[$clog2(DEPTH)-1:0];
    end
  endfunction
endmodule

The TCAM compare trick: ((data XOR key) AND mask) == 0. XOR highlights differing bits. Masking zeroes out don't-care positions. If the result is all-zeros, every care bit matched.

Practical Example — TLB (Translation Lookaside Buffer)

A TLB uses a CAM to translate virtual page numbers (VPN) to physical page numbers (PPN) in a single cycle. Each TLB entry stores a VPN as the search key; on a hit, the associated PPN is retrieved from a parallel data RAM.

Verilog — Fully Associative TLB (8-entry)

module tlb #(
  parameter ENTRIES = 8,
  parameter VPN_W   = 20,  // virtual page number bits
  parameter PPN_W   = 20   // physical page number bits
)(
  input  wire              clk,
  input  wire              rst_n,
  // Lookup (combinational)
  input  wire [VPN_W-1:0]  vpn_in,
  output wire [PPN_W-1:0]  ppn_out,
  output wire              hit,
  // Fill (write new translation)
  input  wire              fill,
  input  wire [$clog2(ENTRIES)-1:0] fill_idx,
  input  wire [VPN_W-1:0]  fill_vpn,
  input  wire [PPN_W-1:0]  fill_ppn,
  // Invalidate (flush on context switch)
  input  wire              flush
);
  reg [VPN_W-1:0] vpn_cam  [0:ENTRIES-1];
  reg [PPN_W-1:0] ppn_data [0:ENTRIES-1];
  reg [ENTRIES-1:0] valid;

  integer i;

  // Flush clears all valid bits
  always @(posedge clk or negedge rst_n) begin
    if (!rst_n || flush) begin
      valid <= {ENTRIES{1'b0}};
    end else if (fill) begin
      vpn_cam [fill_idx] <= fill_vpn;
      ppn_data[fill_idx] <= fill_ppn;
      valid   [fill_idx] <= 1'b1;
    end
  end

  // Parallel CAM search (combinational)
  reg [ENTRIES-1:0] match;
  always @(*) begin
    for (i = 0; i < ENTRIES; i = i+1)
      match[i] = valid[i] && (vpn_cam[i] == vpn_in);
  end

  assign hit = |match;

  // Read PPN from data RAM at matching row
  reg [$clog2(ENTRIES)-1:0] match_idx;
  always @(*) begin
    match_idx = 0;
    for (i = ENTRIES-1; i >= 0; i = i-1)
      if (match[i]) match_idx = i[$clog2(ENTRIES)-1:0];
  end

  assign ppn_out = hit ? ppn_data[match_idx] : {PPN_W{1'b0}};
endmodule

CAM + Data RAM — Standard Pairing

A standalone CAM only returns an address. In practice, CAMs are paired with a normal RAM (Data RAM) indexed by the CAM's output address to retrieve the associated payload.

Verilog — BCAM + parallel data RAM

module cam_with_data #(
  parameter DEPTH   = 8,
  parameter KEY_W   = 8,
  parameter DATA_W  = 32
)(
  input  wire              clk,
  // Write: store key→data mapping
  input  wire              we,
  input  wire [$clog2(DEPTH)-1:0] waddr,
  input  wire [KEY_W-1:0]  wkey,
  input  wire [DATA_W-1:0] wdata,
  // Lookup
  input  wire [KEY_W-1:0]  skey,
  output wire [DATA_W-1:0] sdata,    // associated data on hit
  output wire              hit
);
  // CAM array
  reg [KEY_W-1:0]  cam  [0:DEPTH-1];
  reg [DEPTH-1:0]  valid;

  // Parallel data RAM (indexed by same address)
  reg [DATA_W-1:0] dram [0:DEPTH-1];

  reg [DEPTH-1:0] match;
  integer i;

  always @(posedge clk) begin
    if (we) begin
      cam  [waddr] <= wkey;
      dram [waddr] <= wdata;
      valid[waddr] <= 1'b1;
    end
  end

  always @(*) begin
    for (i = 0; i < DEPTH; i = i+1)
      match[i] = valid[i] && (cam[i] == skey);
  end

  assign hit = |match;

  // Read data at first matching row
  reg [$clog2(DEPTH)-1:0] midx;
  always @(*) begin
    midx = 0;
    for (i = DEPTH-1; i >= 0; i = i-1)
      if (match[i]) midx = i[$clog2(DEPTH)-1:0];
  end

  assign sdata = hit ? dram[midx] : {DATA_W{1'b0}};
endmodule

BCAM vs TCAM vs RAM

Feature	BCAM (binary)	TCAM (ternary)	Normal RAM
Search input	Exact key	Key + don't-care mask	Address
Wildcard match	No	Yes (X bits)	N/A
Multiple matches	Possible	Possible	N/A
Search latency	1 cycle (parallel)	1 cycle (parallel)	1 cycle (indexed)
Area per bit	~4–6 gates/bit	~6–8 gates/bit (extra mask)	1 (SRAM) – 6 (FF)
Typical depth	≤256 in FPGA	≤128 in FPGA (custom ASIC: 128K+)	Unlimited
Main use	Cache tag array, ARP table	IP routing (LPM), firewall ACL	General storage

Interactive CAM Simulator

8-entry CAM Simulator

Write entry

Row (0–7)

Key (8-bit hex)

Search

Search key (hex)

CAM Entries

Row	Key	Mask	Valid	Match

Result

—

FAQ

What is Content Addressable Memory (CAM)?

A CAM is searched by content (data) rather than address. You present a search key, and the CAM returns the row index of any matching entry in a single clock cycle. Opposite of RAM: RAM gives data from address; CAM gives address from data.

What is the difference between binary CAM and ternary CAM?

BCAM: exact match only — every bit must equal the search key. TCAM: three-valued (0, 1, X) — X bits match both 0 and 1. TCAMs enable wildcard/prefix matching used in IP routing (subnet masks) and firewall ACLs.

What is a match line in a CAM?

A match line is precharged high. Each compare cell pulls it low if its stored bit differs from the search key bit. If no cell fires, the match line stays high = row hit. In RTL, this is modeled as: match[i] = (cam[i] == skey).

How does a priority encoder work in a CAM?

Multiple rows can match. A priority encoder takes the match vector and outputs the index of the highest-priority (lowest-index) matching row. This single address indexes the parallel data RAM to retrieve the associated payload.

Where are TCAMs used in practice?

Network routers use TCAMs for longest-prefix match (LPM) — subnet masks are the don't-care bits. Also: firewall ACL lookup, TLB for virtual-to-physical translation, cache tag comparison, and 5-tuple flow classification in packet processors.