F2.6.2 Order the BDD

MediumImplement20 minSymbiYosys · serverReview the topic

Problem

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
PortDirectionBits
clkinput1
a1input1
b1input1
a2input1
b2input1
a3input1
b3input1
foutput1
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.

OrderWhat the BDD must remember
a1, b1, a2, b2, a3, b3after each pair: whether any product so far is 1
a1, a2, a3, b1, b2, b3after the a variables: every one of their values
Execution ruleMeaning
InterfaceUse the pinned port names, directions and bit widths shown above. Observed state and tracker outputs are not environment inputs.
SamplingOne positive edge of clk; binary values. Non-overlapping implication observes the next sample. Reset and initialization follow the source and contract above.
SubmissionSubmit RTL using the starter’s format. The checks apply to this stated model and scope.
How this is gradedThe 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.

Recorded solver trace
01clkfreea1freeb1freea2freeb2freea3freeb3fsampled violation
Scroll horizontally ↔

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

Report a problem with this page

Worked solution

Opening the solution ends an unsolved rated attempt. Solving it first costs nothing.

Your Design

SymbiYosys · server

Recent Submissions