Binary Decision Diagrams, Synthesis and Equivalence
Turn a function into a decision diagram, shrink it to a canonical graph, and see why the variable order matters. Then prove two circuits equal with a miter.
You Will Be Able To
- Build a decision tree from Shannon expansion and reduce it to an ROBDD.
- Explain why an ROBDD is canonical for a fixed variable order.
- Show how the variable order changes the size of the graph.
- Check two circuits for equivalence with a miter.
- Lesson
- G3.9
- Time
- 35 min
- Runs on
- Your browser
- Check
- 5 questions
A truth table doubles with every input. A decision diagram often does not. Equivalence checkers and synthesis tools rely on that.
| f = ab + cd + ef, six inputs | Size |
|---|---|
| Truth table | 64 rows |
| Decision tree | 63 tests |
| Reduced BDD, order a b c d e f | 6 tests |
| Reduced BDD, order a c e b d f | 14 tests |
Counted by the BDD code of this lesson, two independent ways.
Shannon Expansion Is a Decision Tree
Pick a variable, say a. Then f = a' f(a = 0) + a f(a = 1). Each half is a smaller function, called a cofactor. Expand each cofactor on the next variable, and so on.
| Fixed so far | Cofactor of f = ab + c |
|---|---|
| nothing | ab + c |
| a = 0 | c |
| a = 1 | b + c |
| a = 1, b = 0 | c |
| a = 1, b = 1 | 1 |
The cofactors on the path a = 1. A constant cofactor ends the path.
Drawn out in full, the expansion is a tree. Three variables give 7 tests and 8 leaves. That is one leaf per row of the truth table, so the tree is no smaller than the table.
Reduce: Merge and Delete
Two rules shrink the tree. Apply them until neither applies, and the result is a reduced ordered BDD (ROBDD).
The tree
7 tests for three variables, in a fixed order a, b, c.
Merge equal subgraphs
Two nodes that test the same variable and lead to the same children become one. Leaves merge into a single 0 and a single 1. The tree drops to 5 tests.
Delete redundant tests
A test whose two edges lead to the same node decides nothing. Remove it and point its parent past it. 3 tests remain.
- Control / FSM
- Neutral
- Control
- Merged
Four tests of c in the tree became two: one for
f = cand one forf = 1. The two tests of b stay, because their children differ. - Redundant
The test of b reached when
a = 0and the test of c reached whenf = 1decide nothing. Deleting them leaves the three tests below.
Read the diagram as text
- test a
- test b: reached when a = 0
- test b: reached when a = 1
- test c: f = c here
- test c: f = 1 here
- terminal 0
- terminal 1
- test a → test b: a = 0
- test a → test b: a = 1
- test b → test c: b = 0 or 1
- test b → test c: b = 0
- test b → test c: b = 1
- test c → terminal 0: c = 0
- test c → terminal 1: c = 1
- test c → terminal 1: c = 0 or 1
The full tree has 7 tests and 8 leaves, too many boxes for one figure. The table above follows one path through it.
- Control / FSM
- Neutral
- Control
- a = 0
With
a = 0, f is justc. The edge skips the test of b. - a = 1
With
a = 1, test b. Ifb = 1, f is 1 at once. - Shared
If
b = 0, f iscagain: the same node as thea = 0path.
Read the diagram as text
- test c: 0 → 0, 1 → 1
- test b: 0 → test c, 1 → 1
- test a: 0 → test c, 1 → test b
- terminal 0
- terminal 1
- test c → terminal 0: c = 0
- test c → terminal 1: c = 1
- test b → test c: b = 0
- test b → terminal 1: b = 1
- test a → test c: a = 0
- test a → test b: a = 1
Three tests and two terminals. The test of c is shared by two paths.
One Graph per Function
Fix the variable order. Then every function has exactly one ROBDD. This is the property that makes BDDs useful.
| Expression | ROBDD in order a, b, c |
|---|---|
a(b + c) | 3 tests |
ab + ac | 3 tests, the same graph |
ab + c | 3 tests, a different graph |
The first two expressions are one function, so the code builds identical graphs for them.
So two circuits are equivalent exactly when their ROBDDs are the same graph. In a program with a unique table, that is one pointer compare.
An equivalence test uses a miter: XOR the two outputs. The circuits are equal when the miter is the constant 0. Its ROBDD is then just the 0 terminal.
- I/O
- Design
- Datapath
- Data
- Same inputs
Drive both circuits from one set of inputs.
- Compare
XOR each pair of outputs and OR the results.
- Decide
Simulation tries every row. A BDD or SAT tool proves diff can never be 1.
Read the diagram as text
- Inputs: the same to both
- Circuit A: specification
- Circuit B: implementation
- XOR: per output, then OR
- diff: constant 0 means equal
- Inputs → Circuit A: x
- Inputs → Circuit B: x
- Circuit A → XOR: y_A
- Circuit B → XOR: y_B
- XOR → diff: diff
The lab builds this miter in SystemVerilog and tries all 16 rows.
The Order Decides the Size
The same function can have a small or a huge ROBDD, depending only on the order of the variables.
- Control / FSM
- Neutral
- Control
- One pair at a time
Test a, then b. If both are 1, f is 1. Otherwise move on to the next pair.
- Nothing to remember
Leaving a pair, the graph only needs to know that this pair failed. So each pair costs two nodes.
Read the diagram as text
- test f: 0 → 0, 1 → 1
- test e: 0 → 0, 1 → test f
- test d: 0 → test e, 1 → 1
- test c: 0 → test e, 1 → test d
- test b: 0 → test c, 1 → 1
- test a: 0 → test c, 1 → test b
- terminal 0
- terminal 1
- test f → terminal 0: f = 0
- test f → terminal 1: f = 1
- test e → terminal 0: e = 0
- test e → test f: e = 1
- test d → test e: d = 0
- test d → terminal 1: d = 1
- test c → test e: c = 0
- test c → test d: c = 1
- test b → test c: b = 0
- test b → terminal 1: b = 1
- test a → test c: a = 0
- test a → test b: a = 1
6 tests in the good order. With the order a, c, e, b, d, f the same function needs 14.
| Pairs k (f = sum of k ANDed pairs) | Pairs together | All first bits, then all second bits |
|---|---|---|
| 1 | 2 tests | 2 tests |
| 2 | 4 tests | 6 tests |
| 3 | 6 tests | 14 tests |
| 4 | 8 tests | 30 tests |
Together the size grows as 2k. Apart it grows as 2 to the power k + 1, minus 2: the graph must remember every first bit.
Finding the best order is itself hard, so tools use heuristics and reorder as they go. Some functions have large BDDs in every order: Bryant proved it in 1991 for the middle output bits of a multiplier. Equivalence tools then turn to SAT solvers.
What Synthesis and Equivalence Tools Do
A synthesis tool reads your code and turns it into a network of simple gates. It optimizes that network, often as an AND-inverter graph: two-input ANDs and inverters only. The lab's Synthesize button shows this step.
| Source written as | Generic gates after synthesis | Levels |
|---|---|---|
(a & b) | (a & c) | (a & d) | (a & e) | 4 (1 AND, 1 NAND, 2 NOR) | 3 |
a & (b | c | d | e) | 4 (1 AND, 1 NAND, 2 NOR) | 3 |
Measured with the site's pinned flow (Yosys with ABC). These are the tool's generic gates, before any cell library. Flat and factored source give the same netlist.
Technology mapping is the last step. It covers the generic network with the cells a target really has. On an FPGA the cell is a lookup table: a LUT4 holds any function of four inputs.
| Function | Generic synthesis | Mapped to iCE40 LUT4 cells |
|---|---|---|
The lab: (a + b)(c + d), 4 inputs | 3 generic gates | 1 LUT4 |
The lamp of G3.8: a(b + c + d + e), 5 inputs | 4 generic gates | 2 LUT4 |
| A 7-input AND | - | 3 LUT4 (2 would be enough) |
| A 16-input AND | - | 5 LUT4 |
Measured with the pinned iCE40 flow (synth_ice40). A tree of LUT4s could do the 7-input AND in 2; the mapper chose 3. Tools are fast, not always optimal. Module G13 fits logic into LUTs.
After synthesis, an equivalence checker proves the netlist equals the RTL. It builds a miter and asks a BDD or SAT engine whether the difference can ever be 1. The RTL Design track shows synthesis on real code, and the Formal track runs equivalence checks.
Asked in interviews
What is a BDD, and why does variable order matter?
A graph that decides a function one variable at a time. Reduced and ordered, it is unique for each function. A poor order can make it exponentially larger.
How do you check two combinational circuits for equivalence?
Build a miter: XOR each output pair and OR the results. Prove the miter is always 0, with a BDD, a SAT solver or, for few inputs, simulation of every row.
What does a synthesis tool do to your logic?
It converts the code to a gate network and optimizes it, often as an AND-inverter graph. Then it maps the network onto library cells while meeting timing.
Try It
main.sv holds an implementation of (a + b)(c + d) from three NOR gates. The bench in tb.sv holds the specification, XORs the two outputs and tries all 16 rows.
Run it. The bench prints equal: 0 of 16 rows differ: for four inputs, trying every row is a proof.
Now press Synthesize. The Gates tab shows 3 generic cells (1 AND, 2 OR) in 2 levels. The tool rebuilt the NOR gates as the AND of two ORs.
Replace the three NOR gates with assign y = (a & c) | (a & d) | (b & c) | (b & d);. Run still prints equal, and Synthesize gives the same 3 cells.
Then break the implementation: make the last gate nand g3 (y, n1, n2);. The bench prints different: 6 of 16 rows differ, first at abcd = 0001.
Synthesize the design to measure its cells and inspect the mapped gates.
equal: 0 of 16 rows differOriginal design · 3 cells · 0 flip-flops · 0 latches · 2 logic levels. Synthesis uses Yosys; counts depend on the toolchain.
Read included file: tb.sv
// tb.sv (read-only): the specification and an exhaustive miter.
module spec (input logic a, b, c, d, output logic y);
assign y = (a | b) & (c | d); // the specification
endmodule
module tb;
logic a, b, c, d;
wire ys, yi, diff;
spec s (.a(a), .b(b), .c(c), .d(d), .y(ys));
impl i (.a(a), .b(b), .c(c), .d(d), .y(yi));
assign diff = ys ^ yi; // the miter: 1 on any row where they disagree
initial begin
int bad;
logic [3:0] first;
bad = 0;
first = '0;
for (int m = 0; m < 16; m++) begin
{a, b, c, d} = m[3:0];
#1;
if (diff) begin
if (bad == 0) first = m[3:0];
bad++;
end
end
if (bad == 0) $display("equal: 0 of 16 rows differ");
else $display("different: %0d of 16 rows differ, first at abcd = %b", bad, first);
end
endmodule
Check Yourself
Common Mistakes
Wrong Compare two BDDs built with different variable orders.
The graph is unique only for one order. The same function has different graphs in different orders.
Fix Build both BDDs with the same order. Then equal functions give the same graph.
Wrong Pick the variable order without thinking about the function.
A bad order can make the graph grow exponentially, as 6 nodes became 14 here.
Fix Keep variables that interact close together in the order, such as the two bits of each pair.
Wrong Compare only one output of a multi-output circuit in a miter.
A bug on another output is never seen.
Fix XOR every output pair and OR the results into one difference signal.
Remember
- Shannon expansion, applied variable by variable, is a decision tree with one leaf per row.
- Merging equal subgraphs and deleting redundant tests gives the ROBDD, unique for a fixed order.
- The order can change the size from linear to exponential; keep interacting variables together.
- A miter XORs the outputs of two circuits; they are equal when it is always 0.