TAOCP 7.1.4 Exercise 54

Exercise 54. [17] [17] Construct the BDD of f(x1, . . . , xn) from f’s truth table, in O(2n) steps.

Verified: no
Solve time: 6m24s

Solution

Let the truth table of $f(x_1,\ldots,x_n)$ be a binary string $\tau$ of length $2^n$, indexed so that the left half $\tau_0$ represents $f(0,x_2,\ldots,x_n)$ and the right half $\tau_1$ represents $f(1,x_2,\ldots,x_n)$, as in Section 7.1.4.

The BDD is determined by recursively decomposing each subtable $\tau$ into its two halves until sinks $\bot$ and $\top$ are reached, while merging identical subtables so that each distinct subtable corresponds to exactly one node.

Represent every subtable by a pair $(i,k)$, where $i$ is the starting index in $\tau$ and $k$ is the order, meaning the subtable has length $2^k$. The subtable represented by $(i,k)$ is the segment

$$ \tau[i,..,i+2^k-1]. $$

The decomposition rule is that $(i,k)$ corresponds to a branch node when $k>0$, with

$$ \text{LO}(i,k) = (i, k-1), \qquad \text{HI}(i,k) = (i+2^{k-1}, k-1), $$

and it corresponds to a sink when $k=0$, with value $\bot$ or $\top$ according to the bit $\tau[i]$.

To enforce reduction, all nodes are memoized: whenever a pair $(i,k)$ is first encountered, its node is created; whenever it is encountered again, the previously created node is reused. Since equality of subtables is equality of their represented strings, memoization by $(i,k)$ suffices.

The construction proceeds by a depth-first creation of nodes starting from $(0,n)$. The recursion defines a node for each distinct subtable reachable from $\tau$ by repeated halving.

Correctness follows from the structural definition of BDDs in Section 7.1.4. Each node $(i,k)$ represents exactly the truth table of a subfunction $f(c_1,\ldots,c_{n-k},x_{n-k+1},\ldots,x_n)$, and its LO and HI children correspond to fixing $x_{n-k+1}=0$ and $x_{n-k+1}=1$. Ordering holds because each step reduces $k$ by one, so indices strictly increase along any path in variable order. Reduction holds because identical subtables share the same $(i,k)$ representation, so no two nodes have identical $(V,LO,HI)$ triples.

Complexity is determined by the number of distinct states $(i,k)$ and the cost of processing each once. There are at most $2^k$ distinct indices $i$ for each level $k$, so the total number of pairs is bounded by

$$ \sum_{k=0}^n 2^k = 2^{n+1}-1. $$

Each pair is processed in constant time, since computing child indices and performing memoized lookup requires $O(1)$ work under standard hashing or direct addressing on $(i,k)$. Hence the total time is $O(2^n)$.

The resulting graph contains exactly one node per distinct subtable, including the two sinks at $k=0$, so it is a valid reduced ordered BDD as defined in Section 7.1.4.

This completes the proof. ∎