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 inputsSize
Truth table64 rows
Decision tree63 tests
Reduced BDD, order a b c d e f6 tests
Reduced BDD, order a c e b d f14 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 farCofactor of f = ab + c
nothingab + c
a = 0c
a = 1b + c
a = 1, b = 0c
a = 1, b = 11

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).

  1. The tree

    7 tests for three variables, in a fixed order a, b, c.

  2. 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.

  3. 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.

After Merging Only: Five TestsEach box tests one variable; edges are labelled with its value. Two tests have both edges on the same node: they are redundant.
  • Control / FSM
  • Neutral
  • Control
After merging only: five testsEach box tests one variable; edges are labelled with its value. Two tests have both edges on the same node: they are redundant. control test a control test b reached when a = 0 control test b reached when a = 1 control test c f = c here control test c f = 1 here neutral terminal 0 neutral terminal 1 a = 0a = 1b = 0 or 1b = 0b = 1c = 0c = 1c = 0 or 1
  1. control test cf = c here
    • c = 0 → terminal 0
    • c = 1 → terminal 1
  2. control test cf = 1 here
    • c = 0 or 1 → terminal 1
  3. control test breached when a = 0
    • b = 0 or 1 → test c
  4. control test breached when a = 1
    • b = 0 → test c
    • b = 1 → test c
  5. control test a
    • a = 0 → test b
    • a = 1 → test b
  6. neutral terminal 0
  7. neutral terminal 1
  1. Merged

    Four tests of c in the tree became two: one for f = c and one for f = 1. The two tests of b stay, because their children differ.

  2. Redundant

    The test of b reached when a = 0 and the test of c reached when f = 1 decide 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.

The Reduced BDD of f = Ab + cEach box tests one variable. Follow the edge for its value; the terminal reached is the value of f.
  • Control / FSM
  • Neutral
  • Control
The reduced BDD of f = ab + cEach box tests one variable. Follow the edge for its value; the terminal reached is the value of f. control test c 0 → 0, 1 → 1 control test b 0 → test c, 1 → 1 control test a 0 → test c, 1 → testb neutral terminal 0 neutral terminal 1 c = 0c = 1b = 0b = 1a = 0a = 1
  1. control test a0 → test c, 1 → test b
    • a = 0 → test c
    • a = 1 → test b
  2. control test c0 → 0, 1 → 1
    • c = 0 → terminal 0
    • c = 1 → terminal 1
  3. control test b0 → test c, 1 → 1
    • b = 0 → test c
    • b = 1 → terminal 1
  4. neutral terminal 1
  5. neutral terminal 0
  1. a = 0

    With a = 0, f is just c. The edge skips the test of b.

  2. a = 1

    With a = 1, test b. If b = 1, f is 1 at once.

  3. Shared

    If b = 0, f is c again: the same node as the a = 0 path.

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.

ExpressionROBDD in order a, b, c
a(b + c)3 tests
ab + ac3 tests, the same graph
ab + c3 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.

A MiterArrows show signals. Both circuits get the same inputs; the XOR is 1 on any row where they disagree.
  • I/O
  • Design
  • Datapath
  • Data
A miterArrows show signals. Both circuits get the same inputs; the XOR is 1 on any row where they disagree. io Inputs the same to both design Circuit A specification design Circuit B implementation datapath XOR per output, then OR io diff constant 0 meansequal xxy_Ay_Bdiff
  1. io Inputsthe same to both
    • x → Circuit A
    • x → Circuit B
  2. design Circuit Aspecification
    • y_A → XOR
  3. design Circuit Bimplementation
    • y_B → XOR
  4. datapath XORper output, then OR
    • diff → diff
  5. io diffconstant 0 means equal
  1. Same inputs

    Drive both circuits from one set of inputs.

  2. Compare

    XOR each pair of outputs and OR the results.

  3. 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.

f = Ab + Cd + Ef, Pairs Kept TogetherEach box tests one variable. Follow the edge for its value; the terminal reached is the value of f.
  • Control / FSM
  • Neutral
  • Control
f = ab + cd + ef, pairs kept togetherEach box tests one variable. Follow the edge for its value; the terminal reached is the value of f. control test f 0 → 0, 1 → 1 control test e 0 → 0, 1 → test f control test d 0 → test e, 1 → 1 control test c 0 → test e, 1 → testd control test b 0 → test c, 1 → 1 control test a 0 → test c, 1 → testb neutral terminal 0 neutral terminal 1 f = 0f = 1e = 0e = 1d = 0d = 1c = 0c = 1b = 0b = 1a = 0a = 1
  1. control test a0 → test c, 1 → test b
    • a = 0 → test c
    • a = 1 → test b
  2. control test b0 → test c, 1 → 1
    • b = 0 → test c
    • b = 1 → terminal 1
  3. neutral terminal 1
  4. control test c0 → test e, 1 → test d
    • c = 0 → test e
    • c = 1 → test d
  5. control test d0 → test e, 1 → 1
    • d = 0 → test e
    • d = 1 → terminal 1
  6. control test e0 → 0, 1 → test f
    • e = 0 → terminal 0
    • e = 1 → test f
  7. control test f0 → 0, 1 → 1
    • f = 0 → terminal 0
    • f = 1 → terminal 1
  8. neutral terminal 0
  1. One pair at a time

    Test a, then b. If both are 1, f is 1. Otherwise move on to the next pair.

  2. 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 togetherAll first bits, then all second bits
12 tests2 tests
24 tests6 tests
36 tests14 tests
48 tests30 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 asGeneric gates after synthesisLevels
(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.

FunctionGeneric synthesisMapped to iCE40 LUT4 cells
The lab: (a + b)(c + d), 4 inputs3 generic gates1 LUT4
The lamp of G3.8: a(b + c + d + e), 5 inputs4 generic gates2 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
  1. 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.

  2. 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.

  3. 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.

RTLIcarus Verilog · in your browser · Lint: Verilator service · Synthesize: Yosys service
Edit the design, then Run, Lint or Synthesize
Expected: equal: 0 of 16 rows differ

Original 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

Predict the outputThe miter compares a(b + c) with ab + c and reports the first row where they differ. Predict the line.
module tb;
  logic a, b, c;
  wire diff = (a & (b | c)) ^ ((a & b) | c);    // a miter of two circuits
  initial begin
    logic found;
    found = 1'b0;
    for (int m = 0; m < 8; m++) begin
      {a, b, c} = m[2:0];
      #1 if (diff && !found) begin
        $display("first difference at abc = %b", {a, b, c});
        found = 1'b1;
      end
    end
  end
endmodule
Spot the bugEach option should equal f = ab + c. The bench compares it with f on all 8 rows. Which one fails?
ConceptTwo circuits have the same ROBDD in the order a, b, c. What can you conclude?
ConceptA miter of two 2-output circuits XORs output 0 of each and ignores output 1. What can it miss?
ConceptHow many tests does the full decision tree of a 5-variable function have before reduction?

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.

Practice

Report a problem with this page