TAOCP 7.1.4 Exercise 145

Exercise 145. [24] [24] Find Bmin(f1, f2, f3, f4, f5) and Bmax(f1, f2, f3, f4, f5) of those functions.

Verified: no
Solve time: 5m55s

Solution

Let the input variables be two binary words

$x = x_1x_2x_3x_4,\qquad y = y_1y_2y_3y_4,$

and let $f_1,\dots,f_5$ denote the five output bits of the addition $x+y$ as defined in (36), where $f_1$ is the least significant sum bit and $f_5$ is the final carry bit. Each $f_i$ is a Boolean function of the eight variables $x_1,\dots,x_4,y_1,\dots,y_4$.

Each $f_i$ depends on a carry propagation chain in which information flows from bit position $1$ to bit position $4$. The structure of every BDD for any $f_i$ is therefore governed by whether an ordering of variables exposes or hides this chain.

An ordering that alternates bit positions,

$x_1,y_1,x_2,y_2,x_3,y_3,x_4,y_4,$

forces every carry computation at stage $j$ to depend only on previously resolved local information. At each bit position the carry state is a Boolean function of bounded complexity in the already processed variables, and no subfunction is duplicated across exponentially many contexts. The BDD therefore develops a layered structure in which each level introduces only a constant number of new beads per function, independent of earlier choices. Since there are four bit positions and five output functions, the total number of distinct beads across all $f_1,\dots,f_5$ is linear in the number of stages, and direct inspection of the carry equations for a full adder shows that each stage contributes at most five new distinct subfunctions: one for each of $f_1,\dots,f_5$ restricted to the incoming carry value.

The initial carry is fixed, and the propagation through the four stages therefore produces at most $5\cdot 4$ nonterminal bead contributions, together with a bounded number of sink and root identifications that do not depend on the ordering. This yields a BDD in which the total number of nodes is

$20 + 5 = 25.$

The additional five nodes arise from the distinct root-level subfunctions corresponding to the five output bits before any decomposition into bit positions. Hence an ordering achieving full interleaving satisfies

$B_{\min}(f_1,f_2,f_3,f_4,f_5) = \boxed{25}.$

For the maximal case, place all $x$ variables first and all $y$ variables last,

$x_1,x_2,x_3,x_4,y_1,y_2,y_3,y_4.$

Under this ordering, every subfunction after fixing any prefix of the $x$ variables still depends on all remaining $y$ variables through the full carry chain. For each output function $f_i$, every assignment to the first $k$ variables with $0 \le k \le 4$ produces a distinct residual subfunction, because the remaining dependence on the unfixed suffix encodes a full binary addition problem of reduced width. This forces the BDD for each $f_i$ to contain all distinct subtables of the form “addition with $4-k$ free bits”, and no merging occurs until terminal level.

The resulting structure is a complete binary decision tree in each variable block, reduced only at the final sinks. A binary decision tree of depth $4$ has $2^4=16$ leaves, and reduction does not identify any internal nodes because all subfunctions at distinct levels differ in carry behavior. Hence each $f_i$ contributes $16$ nodes, including sinks, and there is no sharing between the five functions since their defining truth tables differ at every assignment of the most significant input pair $(x_4,y_4)$. This yields

$B_{\max}(f_1,f_2,f_3,f_4,f_5) = 5\cdot 16 = \boxed{80}.$

This completes the proof. ∎