G3.9.1 Count the BDD Nodes

MediumImplementIcarus · browser samples / server checksReview the topic

Build the reduced ordered BDD of f = (a xor b) c + d in two variable orders. Count the tests before and after each reduction rule.

Hardware context: A NOR-gate implementation checked against its specification through a miter, and the decision diagrams behind equivalence tools. Count the tests of a BDD in two variable orders.

A verification tool stores f = (a xor b) c + d as a binary decision diagram. Its size depends on the order in which the variables are tested. Your job is to count.

This is an Implement problem. Draw the decision tree of f in the order a b c d. Merge equal subgraphs, then delete redundant tests. Then build the ROBDD again in the order a c d b.

Write four whole numbers as constants. Count tests only: the nodes that test a variable. Do not count the terminals 0 and 1.

Signals in the Timeline

SignalWidthRole
check3input of each check
Full specification
ConstantWhat to count
NODES_ABCDTests in the reduced ordered BDD, with the order a, b, c, d (a at the top).
NODES_ACDBTests in the reduced ordered BDD, with the order a, c, d, b.
MERGED_ABCDOrder a, b, c, d: tests left after merging equal subgraphs only, before deleting redundant tests.
TREE_TESTSTests in the full decision tree, before any reduction.
RuleMeaning
MergeTwo tests of the same variable whose 0-edges reach the same node and whose 1-edges reach the same node become one test. The leaves merge into one 0 and one 1.
DeleteA test whose 0-edge and 1-edge reach the same node is removed. Its parent points past it.
The module (keep the names; change only the four numbers)
// answer: four counts for f = (a xor b) c + d. Count tests (decision nodes) only, not the two terminals.
module answer (
  output int nodes_abcd,
  output int nodes_acdb,
  output int merged_abcd,
  output int tree_tests
);
  localparam int NODES_ABCD  = 0;   // tests in the ROBDD, order a b c d
  localparam int NODES_ACDB  = 0;   // tests in the ROBDD, order a c d b
  localparam int MERGED_ABCD = 0;   // order a b c d: equal subgraphs merged, redundant tests kept
  localparam int TREE_TESTS  = 0;   // tests in the full decision tree
  assign nodes_abcd  = NODES_ABCD;
  assign nodes_acdb  = NODES_ACDB;
  assign merged_abcd = MERGED_ABCD;
  assign tree_tests  = TREE_TESTS;
endmodule

Each check compares one constant with the count made by the reference BDD code.

Examples

Example 1

The Full Tree
Input
TREE_TESTS
Output
tree_tests = 15

Before any reduction, the tree tests one variable at each node, level by level.

Example 2

Reduction Only Removes Tests
Input
NODES_ABCD and MERGED_ABCD
Output
consistent = 1

Deleting redundant tests can only shrink the merged graph of the same order.

Example 3

Merging Only Removes Tests
Input
MERGED_ABCD and TREE_TESTS
Output
consistent = 1

Merging equal subgraphs can only shrink the tree.

Constraints and Contract

  • Keep the module name answer and its four outputs.
  • Each constant is a whole number. Terminals are not counted.

Hints

Hint 1

The full tree tests a once, b twice, c four times and d eight times.

Hint 2

In the order a b c d, fix a and b in all four ways. Only two different functions of c and d are left. Count the distinct cofactors at each level.

Hint 3

In the order a c d b, the graph must remember a until it reaches b at the bottom. Variables that work together are best kept close in the order.

What the grader checks: Each check compares one constant with a count made in JavaScript by two independent BDD routines. The routines are checked against each other on every function of three variables and every order. The check does not read a drawing.

6 checks on Icarus · browser samples / server checks. Run the examples first, then check the full regression. Full checks use the server judge. Downloads contain public samples only. A passing result establishes the tested cases, not a proof for all possible inputs.

See all 2 steps and the final capstone

Report a problem with this page

Your code SystemVerilogSaved locally
Ln 1, Col 1Tab indents · Ctrl/⌘ + Enter runs samples
Not run yet

The Full Tree

Input
TREE_TESTS
Expected output
tree_tests = 15

Before any reduction, the tree tests one variable at each node, level by level.

Run samples executes all 3 public checks. Check all tests runs 6 checks on the server.

Icarus · browser samples / server checks