Description
One function, two variable orders, two very different BDDs. Count the nodes of each.
Write a three-product function as RTL. Then count the nodes of its reduced ordered BDD under two variable orders. One order keeps each pair together. The other reads all a variables first. Count decision nodes and both terminals.
Pinned interface
| Port | Direction | Bits |
|---|---|---|
| clk | input | 1 |
| a1 | input | 1 |
| b1 | input | 1 |
| a2 | input | 1 |
| b2 | input | 1 |
| a3 | input | 1 |
| b3 | input | 1 |
| f | output | 1 |
Full specification
The function is f = (a1 & b1) | (a2 & b2) | (a3 & b3). A reduced ordered BDD tests the variables in one fixed order from the root down. Two nodes with the same test and the same two children are merged. A node whose two children are the same is removed.
Complete the module so that f is this function. Then enter two node counts. The first is for the order a1, b1, a2, b2, a3, b3. The second is for the order a1, a2, a3, b1, b2, b3. Count every decision node and the two terminals, 0 and 1.
The judge proves your module against the function and compares both counts with the exact sizes.
| Order | What the BDD must remember |
|---|---|
| a1, b1, a2, b2, a3, b3 | after each pair: whether any product so far is 1 |
| a1, a2, a3, b1, b2, b3 | after the a variables: every one of their values |
| Execution rule | Meaning |
|---|---|
| Interface | Use the pinned port names, directions and bit widths shown above. Observed state and tracker outputs are not environment inputs. |
| Sampling | One positive edge of clk; binary values. Non-overlapping implication observes the next sample. Reset and initialization follow the source and contract above. |
| Submission | Submit RTL using the starter’s format. The checks apply to this stated model and scope. |
| How this is graded | The reference obligations, independent reachability checks and fault checks must all succeed. An unresolved proof or resource limit is inconclusive and is never a rated miss. |
Measured Counterexample
FAIL · bmc · depth 2 · smtbmc yices · 1137 ms
This measured failing run uses the published interface. Follow the sampled violation back to the preceding inputs and state. The worked solution below explains the required behaviour and the failure mechanisms.
Samples from the measured run. Free input lanes are shaded; the terminal VCD record is omitted.
Sample 0: a3=1, b3=1, f=0. The third product is 1, so f must be 1. This version leaves that product out. In the BDD this is the last pair of nodes on the path where the first two products are 0.
Examples
One Product
f = a1 & b1, order a1, b1.
2 decision nodes and 2 terminals: 4.
The node for a1 goes to 0 or to the node for b1. The node for b1 goes to 0 or to 1.
Requirements
- Use the published ports and widths. The checker and the DUT variants are owned by the judge.
- Do not add assumptions unless the statement explicitly asks for one. A passing assertion without a reachable trigger is insufficient.
Hints
Hint 1
Draw the first order pair by pair. After a pair is done, how many different situations are left?
Hint 2
In the second order, ask how many different subfunctions of the b variables exist after all a variables are read.
Hint 3
Use the node-count table of the BDD section in F2.6.
Single clock, binary values, synchronous reset. The judge checks the pinned interface, reachability and the declared proof or bound. UNKNOWN, resource limits and timeouts remain inconclusive.
INCONCLUSIVE never counts as acceptance or a rated miss. Run previews the same checks that Submit uses.
More problems on this topic