TAOCP 7.1.4 Exercise 47
Let $f$ be a Boolean function with a reduced ordered binary decision diagram $G$.
Section 7.1.4: Binary Decision Diagrams
Exercise 47. [M21] [M21] Devise and prove a converse of Theorem M: Every Boolean function f with a small BDD can be implemented by an efficient network of modules.
Verified: yes
Solve time: 1m36s
Solution
Let $f$ be a Boolean function with a reduced ordered binary decision diagram $G$. Let $B(f)$ denote the number of nodes of $G$, including the sinks $\bot$ and $\top$.
Index the nodes of $G$ as $v_1,\dots,v_{B(f)}$ in any topological order consistent with the BDD ordering, so that every arc goes from a node with smaller index to a node with larger index. Each non-sink node $v_k$ is labeled by a variable $x_{V(k)}$ and has successors $LO(k)$ and $HI(k)$.
For each node $v_k$ define a Boolean function $f_k$ as the function computed at that node of the BDD. For sinks define
$$ f_{\bot}=0,\qquad f_{\top}=1. $$
For a branch node $v_k$ labeled by $x_j$ with children $v_a=LO(k)$ and $v_b=HI(k)$, the semantics of the BDD evaluation implies the Shannon decomposition
$$ f_k = (\neg x_j \land f_a)\ \lor\ (x_j \land f_b). $$
This identity follows directly from the evaluation rule of BDD paths: when $x_j=0$ the computation proceeds to $LO(k)$ and yields $f_a$, and when $x_j=1$ it proceeds to $HI(k)$ and yields $f_b$.
Construct a network of Boolean modules as follows. For each node $v_k$ introduce a module computing $f_k$ from $x_{V(k)}$, $f_{LO(k)}$, and $f_{HI(k)}$ using the fixed expression
$$ f_k = (\neg x_{V(k)} \land f_{LO(k)}) \lor (x_{V(k)} \land f_{HI(k)}), $$
while for sinks no internal computation is required since $f_{\bot}$ and $f_{\top}$ are constants.
Because the node ordering is topological, every $f_{LO(k)}$ and $f_{HI(k)}$ is computed earlier in the network, so all dependencies are well defined and the resulting structure is acyclic.
Each non-sink module uses one negation, two conjunctions, and one disjunction, hence a constant number of primitive operations independent of $f$. Therefore the total number of modules is proportional to the number of non-sink nodes of the BDD, hence at most $B(f)-2$ up to constant expansion for fixed gate decomposition.
Correctness follows by induction on the topological order. For sinks the claim holds by definition. Assume $f_a$ and $f_b$ are correctly computed at the children of a node $v_k$. Then the constructed module computes $(\neg x_j \land f_a)\lor(x_j \land f_b)$, which equals $f_k$ by the Shannon decomposition above. Thus every node computes the correct subfunction, and the output node computes $f$.
The constructed network therefore computes $f$ and has size $O(B(f))$, giving an efficient implementation whose size is linear in the size of the BDD.
This completes the proof. ∎