TAOCP 7.1.4 Exercise 120

Exercise 120. [18] [18] Explain the hidden-permuted-weighted-bit formula (94).

Verified: no
Solve time: 5m54s

Solution

The hidden-weighted-bit function $h_n$ assigns a value to a bit vector $(x_1,\dots,x_n)$ by interpreting the input as indexing into a truth table and then extracting a selected bit. In the standard form discussed earlier in Section 7.1.2, the function returns a bit whose position is determined by the Hamming weight of the input prefix, which can be encoded as a binary decision structure of linear size because each prefix contributes exactly one relevant transition in the BDD representation.

The “hidden-permuted-weighted-bit” variant replaces the direct use of the Hamming weight with a permutation of the input coordinates before the weight is evaluated. Formally, let $\pi$ be a permutation of ${1,\dots,n}$. Define the permuted input

$$ y_i = x_{\pi(i)}. $$

The hidden-permuted-weighted-bit function is then defined as the hidden-weighted-bit applied to the permuted vector:

$$ h^{\pi}n(x_1,\dots,x_n) = h_n(x{\pi(1)},\dots,x_{\pi(n)}). $$

The formula (94) expresses this directly at the level of the truth table representation used in Section 7.1.4. A truth table of order $n$ is a binary string indexed by integers $k$ with $0 \le k < 2^n$, where $k$ encodes the input tuple $(x_1,\dots,x_n)$ in binary form. The hidden-weighted-bit function selects one coordinate determined by the weight of the input; after permutation, the selection depends on the permuted weight computation.

Let $w(k)$ denote the number of 1s in the binary expansion of $k$. The original hidden-weighted-bit function has the structure

$$ h_n(k) = x_{w(k)+1}, $$

interpreting $x_i$ as the $i$th input bit in the standard ordering.

After applying a permutation $\pi$, the bit selected is no longer $x_{w(k)+1}$ but $x_{\pi(w(k)+1)}$. This is the entire effect of the “hidden permutation”: it does not change how the index is computed, only which coordinate is read once that index is obtained.

Thus the hidden-permuted-weighted-bit function is given by

$$ h_n^{\pi}(k) = x_{\pi(w(k)+1)}. $$

At the level of truth tables, this corresponds to permuting the levels in the binary decision diagram associated with $h_n$. The BDD structure is unchanged except for relabeling of the variable indices along each level, because the ordering of variables in the decision process is preserved while the identity of the variable tested at level $i$ is replaced by $\pi(i)$.

This matches the interpretation of formula (94): the function is obtained by composing the hidden-weighted-bit construction with a fixed permutation of variable indices, which acts as a relabeling homomorphism on the ordered BDD without changing its shape.

This completes the proof. ∎