Mapping starts from a Boolean network of simple gates such as AND, OR, and inverters. Call it the subject graph: nodes are gates and edges are wires.
The library offers cells such as NAND2, AOI21, and MUX2. Each cell is a pattern: a small gate shape with an area cost.
A cover assigns every subject node to exactly one cell. The cover is valid only when each cell input connects to a primary input or to another cell output.
Every node belongs to exactly one cell, including inverters.
A cell matches only where its function fits the gates it covers.
The cover cost is the sum of its cell areas in library area units.
Take f = NOT ((a AND b) OR c) with course library areas. Three covers compete, and the calc block adds each one.
Cover | Cells | Area (area units) |
|---|---|---|
A | AND2 + NOR2 | 5 |
B | NAND2 + INV + NAND2 + INV | 6 |
C | AOI21 | 3 |
f = NOT ((a AND b) OR c); areas in teaching-library area units
cover A = AND2 (3) + NOR2 (2) = 5
cover B = NAND2 (2) + INV (1) + NAND2 (2) + INV (1) = 6
cover C = AOI21 (3) = 3
cheapest of the three = cover C at 3 area unitsCover C wins because one AOI21 cell absorbs the AND, the OR, and the output inversion. Fewer, better-fitting cells beat more generic ones.
Cover B really implements f: with n1 = NAND2(a, b), nc = INV(c), m = NAND2(n1, nc), and y = INV(m), the output column matches f on every input row.
a b c | f | cover B y |
|---|---|---|
000 | 1 | 1 |
001 | 0 | 0 |
010 | 1 | 1 |
011 | 0 | 0 |
100 | 1 | 1 |
101 | 0 | 0 |
110 | 0 | 0 |
111 | 0 | 0 |
Cover C, a single AOI21 at 3 area units.
No. Every node needs a cell, including inverters. The unassigned node is logic the netlist does not implement.