Generation of Multi-Output BDD

Question

I am using the CUDD package to generate the BDD, corresponding to an input benchmark file, in PLA format. For a benchmark function with 3 input pins (say) and, 5 output pins (say), I am getting 5 output BDDS corresponding to the 5 outputs. But, I want to generate a single Multi-Output BDD, for the entire benchmark function. Is it possible?....if so, how can I generate the Multi-Output BDD using the CUDD package. Please help.

Answer 1

This is possible. Let B1, B2, B3, B4, B5 be the BDDs over the set of input variables x1, x2, x3 (in your example). You allocate some additional variables y1, y2, y3, y4, y5 for the output and compute

!(B1 ^ y1) & !(B2 ^ y2) & !(B3 ^ y3) & !(B4 ^ y4) & !(B5 ^ y5)

to get a new BDD over the variables x1, ..., y5 that maps all variable valuations to true for which yi is the value of Bi on x1 to x3 for all i in {1,2,3,4,5}. This should be what you want.

Note that while !(B ^ y) looks weird, the idea encoded is that we should have that that the value of y is the value of B. But there is only the XOR operator available, and I'm negating the result (in constant time in CUDD) to simulate the equality requirement.