TAOCP 7.1.4 Exercise 59

Let $H$ denote the reduced ordered BDD for $h(x_1,\ldots,x_n)$.

taocpmathematicsalgorithmsvolume-4math-hard

Section 7.1.4: Binary Decision Diagrams

Exercise 59. ▶ [M28] [M28] Let h(x1, . . . , xn) be a Boolean function. Describe the melded BDD f ⋄g in terms of the BDD for h, when (a) f(x1, . . . , x2n) = h(x1, . . . , xn) and g(x1, . . . , x2n) = h(xn+1, . . . , x2n); (b) f(x1, x2, . . . , x2n) = h(x1, x3, . . . , x2n−1) and g(x1, x2, . . . , x2n) = h(x2, x4, . . . , x2n). [In both cases we obviously have B(f) = B(g) = B(h).]

Verified: yes
Solve time: 2m04s

Setup

Let $H$ denote the reduced ordered BDD for $h(x_1,\ldots,x_n)$. Write a node of $H$ as $u$, with variable index $V(u)$ and successors $\mathrm{LO}(u)$, $\mathrm{HI}(u)$, and let the sink nodes be $\bot$ and $\top$.

The melded diagram construction from recursive use of (37) defines a product-style BDD operation on two ordered BDDs with compatible variable orderings: a node of $f \diamond g$ is a pair $(u,v)$ of nodes from the operand diagrams, with transitions computed synchronously according to the next variable to be tested. The sink pairs $(\bot,\bot)$, $(\bot,\top)$, $(\top,\bot)$, $(\top,\top)$ are terminal states, and reduction merges identical subdiagrams as in Section 7.1.4.

The task is to express the melded BDD for $(f,g)$ in terms of $H$ in the two cases:

(a) $f(x_1,\ldots,x_{2n}) = h(x_1,\ldots,x_n)$ and $g(x_1,\ldots,x_{2n}) = h(x_{n+1},\ldots,x_{2n})$,

(b) $f(x_1,\ldots,x_{2n}) = h(x_1,x_3,\ldots,x_{2n-1})$ and $g(x_1,\ldots,x_{2n}) = h(x_2,x_4,\ldots,x_{2n})$.

Solution

The BDD for $f \diamond g$ is obtained by taking the synchronous product of two copies of $H$, with different interpretations of the variable schedule in each case.

For every pair of nodes $(u,v)$, the outgoing structure depends on which variable is queried next in the global ordering. The successor on input bit $x_k$ is

$$ (u,v)\xrightarrow{x_k=0}(u_0,v_0),\qquad (u,v)\xrightarrow{x_k=1}(u_1,v_1), $$

where $(u_0,u_1)$ is determined by $u$ if $V(u)=k$, and otherwise $(u_0,u_1)=(u,u)$, and similarly for $v$. Reduction identifies all pairs of identical behavior, so the resulting diagram is again a BDD.

(a) Disjoint variable blocks

In this case $f$ depends only on $x_1,\ldots,x_n$ and $g$ depends only on $x_{n+1},\ldots,x_{2n}$. The global variable order is $x_1<\cdots<x_{2n}$.

For $k\le n$, only the first component evolves:

$$ (u,v)\xrightarrow{x_k=b} (u_b, v), $$

since $g$ ignores $x_k$. For $k>n$, only the second component evolves:

$$ (u,v)\xrightarrow{x_k=b} (u, v_b), $$

since $f$ ignores $x_k$.

The initial node is $(r,r)$, where $r$ is the root of $H$. During the first $n$ levels, the second component remains frozen at $r$, so the subgraph reachable before level $n+1$ is isomorphic to $H$ in the first coordinate. Each terminal reached after processing $x_1,\ldots,x_n$ is a pair $(\bot,r)$ or $(\top,r)$.

From level $n+1$ onward, the first component is frozen and the second component evolves as an independent copy of $H$ over variables $x_{n+1},\ldots,x_{2n}$. Thus each terminal of the first stage is replaced by a full copy of $H$.

Consequently the melded BDD is a two-stage cascade: an $H$-structure on variables $x_1,\ldots,x_n$, whose leaves are not sinks but roots of a second independent copy of $H$ on variables $x_{n+1},\ldots,x_{2n}$. All internal structure in both stages is identical to $H$, and reduction identifies no cross-stage nodes because their variable dependencies differ.

(b) Alternating variables

Here the variable order is $x_1<x_2<\cdots<x_{2n}$, but $f$ uses $x_1,x_3,\ldots,x_{2n-1}$ and $g$ uses $x_2,x_4,\ldots,x_{2n}$.

At odd levels $k=2i-1$, only the first component evolves according to $H$:

$$ (u,v)\xrightarrow{x_{2i-1}=b} (u_b, v). $$

At even levels $k=2i$, only the second component evolves:

$$ (u,v)\xrightarrow{x_{2i}=b} (u, v_b). $$

Both components therefore advance through independent copies of $H$, but interleaved one step at a time. After processing $x_{2i-1}$, the first component is at the same state as $H$ would reach after $x_i$ of its own variables; after processing $x_{2i}$, the second component is similarly advanced.

Thus every reachable node of the melded BDD is a pair $(u,v)$ where both $u$ and $v$ are nodes of $H$, and the structure is exactly the synchronous product of two copies of $H$ under alternating variable updates. Reduction merges only identical pairs, so the node set is the set of all reachable pairs of nodes of $H$ under this alternating evolution.

Verification

In case (a), each variable $x_k$ affects exactly one component of $(f,g)$, so transitions preserve the other component unchanged, matching the stated decomposition into two independent copies of $H$ arranged in sequence. The reachable subgraphs before and after index $n$ depend on disjoint variable sets, so no edge can connect a node influenced by $x_1,\ldots,x_n$ with one influenced by $x_{n+1},\ldots,x_{2n}$ except through the terminal interface, which is correctly represented by replacing sinks with roots of a second copy.

In case (b), every level of the global ordering alternates between variables used by $f$ and variables used by $g$, so each step updates exactly one coordinate of the pair state $(u,v)$ according to $H$. This produces a well-defined product automaton whose projection onto each coordinate reproduces the original BDD of $h$ under the corresponding subsequence of variables, consistent with $B(f)=B(g)=B(h)$.

This completes the proof.

∎