Find an order of a 4-bit adder's inputs under which its carry out has at most 12 nodes, down from 31.
For some functions the order does not matter: parity has the same size under every order. For others every order is large, such as the middle bit of a product. Between them are functions for which some orders are small and others large. For those, an order is small when the diagram has little to remember on each level.
Take e = (x1 ~^ y1) & (x0 ~^ y0), which is 1 when the 2-bit numbers x1 x0 and y1 y0 are equal. ~^ is exclusive-nor, 1 when its operands are equal.
e = (x1 ~^ y1) & (x0 ~^ y0)
x1 x0
y1 y0
~^
Under the order x1 x0 y1 y0, the diagram reads both bits of x before any bit of y, so it must remember both: level y1 has 4 nodes, one for each value of x1 x0. In all, e has 9 nodes with complement edges.
x1 x0 y1 y0
x
y
y1
e
Under the order x1 y1 x0 y0, it compares each bit as soon as it reads it, and only has to remember whether the bits so far were equal: 6 nodes.
x1 y1 x0 y0
The same function needs 9 nodes under one order and 6 under the other.
Given: order: a0 a1 a2 a3 b0 b1 b2 b3; cout = a3 & b3 | (a3 ^ b3) & (a2 & b2 | (a2 ^ b2) & (a1 & b1 | (a1 ^ b1) & (a0 & b0)));
order: a0 a1 a2 a3 b0 b1 b2 b3; cout = a3 & b3 | (a3 ^ b3) & (a2 & b2 | (a2 ^ b2) & (a1 & b1 | (a1 ^ b1) & (a0 & b0)));
cout is the carry out of the 4-bit addition a3..a0 + b3..b0. Under the order a0 a1 a2 a3 b0 b1 b2 b3, with every a above every b, its BDD has 31 nodes with complement edges.
cout
a3..a0 + b3..b0
a0 a1 a2 a3 b0 b1 b2 b3
a
b
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 a0 to a3 and b0 to b3 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, for a level in the middle of your order, what the diagram must remember about the variables above it to finish the addition.
Compare the node count on each level of the diagram with that answer: a level with many nodes remembers more than it needs.
Kata 4.2 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.