Find an order of a 4-bit comparator's inputs under which its BDD has at most 12 nodes, down from 42.
The BDDs of a circuit's outputs depend on the order of its input bits as much as any function's do. A good order puts first the inputs that decide how the others are used, and keeps together the inputs the circuit combines. Then, on each level, the diagram has little to remember about the inputs above it.
Take a 4-to-1 multiplexer: y = s1 ? (s0 ? d3 : d2) : (s0 ? d1 : d0). The select bits s1 and s0 choose which data bit y is.
y = s1 ? (s0 ? d3 : d2) : (s0 ? d1 : d0)
s1
s0
y
Under the order s1 s0 d0 d1 d2 d3, the select comes first: each path reads s1 and s0, then only the one data bit they choose. The diagram has 8 nodes with complement edges.
s1 s0 d0 d1 d2 d3
Under the order d0 d1 d2 d3 s1 s0, the diagram reads all four data bits before it knows which one matters, and must remember them all: 23 nodes.
d0 d1 d2 d3 s1 s0
Reading first the inputs that decide what matters took the multiplexer from 23 nodes to 8.
Given: order: a3 a2 a1 a0 b3 b2 b1 b0; gt = a3 & ~b3 | (a3 ~^ b3) & (a2 & ~b2 | (a2 ~^ b2) & (a1 & ~b1 | (a1 ~^ b1) & a0 & ~b0));
order: a3 a2 a1 a0 b3 b2 b1 b0; gt = a3 & ~b3 | (a3 ~^ b3) & (a2 & ~b2 | (a2 ~^ b2) & (a1 & ~b1 | (a1 ~^ b1) & a0 & ~b0));
gt is 1 when the 4-bit number a3..a0 is greater than b3..b0. Under the order a3 a2 a1 a0 b3 b2 b1 b0, its BDD has 42 nodes with complement edges.
gt
a3..a0
b3..b0
a3 a2 a1 a0 b3 b2 b1 b0
Find an order of the eight variables under which it has at most 12.
An order of all the variables, top to bottom, in the list: drag a row by its handle, or select it and move it with its arrows or with Alt and an arrow key. The list starts in the order the task gives. For example, an order of other variables might read w y x z.
w y x z
Each of a3 to a0 and b3 to b0 exactly once.
At most 12 nodes, with complement edges.
Watch the conditions: they show that your order holds each variable once, and its node count with complement edges, as you change it.
Ask how you would compare two numbers by hand, one bit at a time: which bits do you read together, and what must you remember between them?
Read the diagram level by level, as in the example: a level with many nodes remembers more than the comparison needs.
Kata 6.4 of Binary Decision Diagrams with CUDD on formal.org. The site checks the answer when you press Check answer; sign in to keep your progress.