TAOCP 7.1.4 Exercise 85

Section 7.1.4: Binary Decision Diagrams

Exercise 85. [16] [16] Compare the size of a BDD base for the 32 functions of 16×16-bit binary mul- tiplication with the alternative of just storing a complete table of all possible products.

Verified: no
Solve time: 5m19s

Solution

Let $x=(x_{15}\ldots x_0)2$ and $y=(y{15}\ldots y_0)_2$. The product $x\cdot y$ is a 32-bit number whose $k$th bit, $0\le k\le 31$, is a Boolean function

$$ f_k(x_0,\ldots,x_{15},y_0,\ldots,y_{15}). $$

Thus a BDD base for 16×16-bit multiplication consists of the shared reduced ordered decision diagram representing the 32 functions $f_0,\ldots,f_{31}$ over 32 variables.

The alternative representation is a complete multiplication table indexed by all input pairs $(x,y)$, of which there are $2^{16}\cdot 2^{16}=2^{32}$. Each entry stores a 32-bit output vector, hence the table requires

$$ 32\cdot 2^{32} $$

bits of storage.

The BDD size is governed by the number of distinct subfunctions generated by splitting on variables in the fixed order $x_0,\ldots,x_{15},y_0,\ldots,y_{15}$. After fixing the first $i$ variables among the $x$-bits and the first $j$ variables among the $y$-bits, the remaining computation depends only on the partial suffixes together with the carry produced by the lower-order partial products. At bit position $k$, the carry state is determined by the lower $k$ bit positions, hence it ranges over at most $2^k$ possibilities.

For a fixed output bit $f_k$, the number of distinct subfunctions at level $k$ is bounded by the number of choices of a bit position together with a carry configuration, hence at most $k\cdot 2^k$. Since $k\le 16$, each $f_k$ contributes at most $16\cdot 2^{16}$ BDD nodes.

The BDD base shares identical subgraphs among all 32 output bits, since the same carry subfunctions occur repeatedly in different bit positions. Hence the total number of distinct nodes in the base is bounded by a constant multiple of

$$ 32\cdot 16\cdot 2^{16} = 2^5\cdot 2^4\cdot 2^{16} = 2^{25}. $$

The full truth-table representation grows as $2^{32}$ entries, while the BDD base grows on the order of $2^{25}$ nodes. The former encodes every input pair explicitly, while the latter merges all repeated carry and suffix subcomputations into a shared directed acyclic graph.

The comparison is therefore between storage proportional to $2^{32}$ input cases versus storage proportional to at most $2^{25}$ shared BDD nodes, with additional structural sharing across the 32 output functions further reducing constant factors in the base representation. ∎