Layout vs schematic (LVS)

WHY does LVS exist?

The three sign-off checks in physical verification:

• DRC (Design Rule Check): Is the layout manufacturable? (spacing/width rules)
• LVS (Layout vs Schematic): Does the layout match the intended circuit?
• ERC (Electrical Rule Check): Are there electrical bugs? (floating gates, etc.)

LVS answers the functional-equivalence question, not the manufacturability one.

WHAT is LVS, precisely?

Two netlists are equivalent when they are the same labeled graph:

• Nodes = electrical nets (wires)
• Edges/vertices = devices (transistors, R, C) with their terminals and parameters

HOW does LVS work? (derivation from first principles)

Think of the LVS engine as building and comparing two graphs. We derive each stage.

Stage 1 — Layout extraction (build the layout graph)

Net formation (union-find on polygons). Start with every polygon as its own net. Merge nets when:

• two shapes on the same layer overlap/abut, or
• shapes on two layers are joined by a contact/via where those layers are allowed to connect.

This is exactly a union-find (disjoint-set) problem. If there are $N$ polygons and $E$ overlap/via relations, labeling all nets costs

$T_{\text{connectivity}} = O\big((N+E)\,\alpha(N)\big)$

Why this formula? Union-find with path compression + union by rank does each of the $E$ merges and $N$ finds in near-constant amortized time $\alpha(N)$ (inverse Ackermann ≈ 4 for any real chip). So it's essentially linear in geometry.

Device recognition. A device is a pattern of overlapping layers. An MOS transistor = poly crossing diffusion:

• the poly-over-diffusion overlap region is the gate/channel,
• the diffusion on each side = source and drain,
• the underlying well ⇒ NMOS vs PMOS.

The gate width $W$ = length of the poly–diffusion crossing edge; the length $L$ = the poly dimension along current flow. So parameters come straight from geometry:

$W = \text{(edge length of channel)}, \qquad L = \text{(poly width across channel)}.$

The output of Stage 1 is the layout netlist: devices + extracted nets + $W/L$.

Stage 2 — Reference netlist

The schematic is compiled (or a SPICE netlist is given) into the same graph form. No extraction needed — connectivity is already named.

Stage 3 — Graph matching (the comparison)

The trick: coloring / partition refinement (Weisfeiler–Leman idea).

1. Give every node an initial color from local invariants it cannot fake: for a net, e.g. (#transistor gates on it, #sources, #drains, #passives). For a device, its type and parameters.
2. Refine: recolor each node using the multiset of neighbor colors. Repeat.
3. After refinement, colors partition nodes into classes. Match classes across the two graphs.
4. If both graphs converge to identical color histograms and each class has a unique pairing ⇒ LVS clean. Any leftover ambiguity/mismatch ⇒ report a discrepancy.

Refinement runs a small number of rounds $k$ (until stable), each round $O(V+E)$, so practically

$T_{\text{match}} \approx O\big(k\,(V+E)\big),$

near-linear on well-structured chips (hierarchy helps hugely — you match a cell once and reuse it).

Typical LVS error classes (and how they show up)

Worked examples

Common mistakes (steel-manned)

80/20 — the 20% that gives 80%

1. LVS = extract-layout-netlist → graph-compare with schematic.
2. It checks devices + connectivity + parameters, by isomorphism, not by name.
3. Main errors: short, open, missing/extra device, param mismatch.
4. DRC≠LVS≠ERC; LVS clean ≠ correct schematic.

Connections

• Design Rule Check (DRC) — sibling physical-verification check (manufacturability).
• Electrical Rule Check (ERC) — floating gates, over-driven nets.
• Parasitic Extraction (PEX) — extends extraction to R/C for timing.
• Netlist and SPICE — the reference-netlist format.
• CMOS Inverter Layout — the canonical LVS example.
• Union-Find (Disjoint Set) — the connectivity engine.
• Graph Isomorphism — the theoretical core of matching.
• Physical Design Flow / Tape-out — where LVS sits in sign-off.

Concept Map

Hinglish (regional understanding)