TAOCP 7.1.4 Exercise 8

Exercise 8. [22] [22] Solve exercise 7 with xk−1 ⊕xk in place of xk−1∨xk.

Verified: no
Solve time: 5m16s

Solution

Let $f(x_1,\ldots,x_n)$ be given and let

$$ g_k(x_1,\ldots,x_n)=f(x_1,\ldots,x_{k-2},,x_{k-1}\oplus x_k,,x_{k+1},\ldots,x_n). $$

Define $z = x_{k-1}\oplus x_k$. Then $z=0$ holds exactly on $(x_{k-1},x_k)\in{00,11}$ and $z=1$ holds exactly on $(01,10)$. Thus the substitution identifies the two cosets of ${0,1}^2$ determined by parity.

Truth tables

Fix all variables except $x_{k-1},x_k$. For every assignment $\alpha$ of the remaining variables, the restriction of $f$ to these two variables is a truth table

$$ \tau_\alpha(u,v)=f(\alpha_1,\ldots,\alpha_{k-2},u,v,\alpha_{k+1},\ldots,\alpha_n). $$

The corresponding restriction of $g_k$ is

$$ \sigma_\alpha(u,v)=\tau_\alpha(u\oplus v). $$

Hence $\sigma_\alpha$ depends only on the parity class of $(u,v)$. Writing the $4$ values of $\tau_\alpha$ in lexicographic order,

$$ (\tau_\alpha(0,0),\tau_\alpha(0,1),\tau_\alpha(1,0),\tau_\alpha(1,1)), $$

the induced restriction of $g_k$ collapses these into two values:

$$ g_k(\alpha, z=0)=\tau_\alpha(0,0)=\tau_\alpha(1,1), \quad g_k(\alpha, z=1)=\tau_\alpha(0,1)=\tau_\alpha(1,0). $$

Thus every 2-variable subtable of $f$ at positions $(k-1,k)$ is replaced in $g_k$ by its parity-coalesced projection, identifying the pairs ${00,11}$ and ${01,10}$.

Equivalently, if a subtable of $f$ at level $k$ is written as $\tau_0\tau_1$ with respect to $x_{k-1}$, then refining with respect to $x_k$ gives four subtables

$$ \tau_{00},\tau_{01},\tau_{10},\tau_{11}, $$

and the corresponding values of $g_k$ are determined by the identifications

$$ \tau_{00}\equiv\tau_{11}, \quad \tau_{01}\equiv\tau_{10}, $$

so the induced truth table of $g_k$ is obtained by merging these equal-parity classes.

BDD transformation

Let the BDD of $f$ contain the substructure rooted at the $x_{k-1}$-nodes, whose LO and HI branches compute the subtables corresponding to $x_{k-1}=0$ and $x_{k-1}=1$. In $g_k$, the variable $x_{k-1}$ no longer directly determines branching; instead the decision is mediated by the parity variable $z=x_{k-1}\oplus x_k$.

A BDD for $z$ is given by a single $x_{k-1}$-node whose HI branch leads to a $x_k$-node, and whose LO branch leads to a $x_k$-node with swapped edges, implementing XOR in ordered form. Concretely, the sub-BDD computing $z$ has the structure

$$ z = \begin{cases} 0 & (x_{k-1},x_k)\in{00,11},\ 1 & (x_{k-1},x_k)\in{01,10}. \end{cases} $$

To obtain the BDD of $g_k$, replace every occurrence in the $x_{k-1}$, $x_k$ layers of the BDD of $f$ by this XOR-gadget: each edge that would previously propagate the value of $x_{k-1}$ into the $k$-th decision is rerouted so that the pair $(x_{k-1},x_k)$ is evaluated through the XOR sub-BDD, and its output is fed into the original position of variable $x_{k-1}$ in the remaining structure of $f$.

After this replacement, reduction merges identical nodes created by symmetry of XOR, since the two parity classes induce identical sub-BDD roots wherever $f$ depends only on $x_{k-1}\oplus x_k$.

Final relation

The truth table of $g_k$ is obtained from that of $f$ by replacing every 2-bit block indexed by $(x_{k-1},x_k)$ with its parity projection, identifying $00\sim 11$ and $01\sim 10$.

The BDD of $g_k$ is obtained from the BDD of $f$ by substituting the local decision on $x_{k-1}$ and $x_k$ with a canonical XOR sub-BDD computing $x_{k-1}\oplus x_k$, then applying reduction to merge isomorphic subgraphs.

This completes the solution. ∎