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
| Signal | Width | Role |
|---|---|---|
check | 3 | input of each check |
Full specification
| Constant | What to count |
|---|---|
| NODES_ABCD | Tests in the reduced ordered BDD, with the order a, b, c, d (a at the top). |
| NODES_ACDB | Tests in the reduced ordered BDD, with the order a, c, d, b. |
| MERGED_ABCD | Order a, b, c, d: tests left after merging equal subgraphs only, before deleting redundant tests. |
| TREE_TESTS | Tests in the full decision tree, before any reduction. |
| Rule | Meaning |
|---|---|
| Merge | Two 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. |
| Delete | A test whose 0-edge and 1-edge reach the same node is removed. Its parent points past it. |
// 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