TAOCP 7.1.4 Exercise 27

Section 7.1.4: Binary Decision Diagrams

Exercise 27. ▶ [M26] [M26] Suppose F(p1, . . . , pn) and G(p1, . . . , pn) are the reliability polynomials for Boolean functions f(x1, . . . , xn) and g(x1, . . . , xn), where f ̸= g. Let q be a prime number, and choose independent random integers q1, . . . , qn, uniformly distributed in the range 0 ≤qk < q. Prove that F(q1, . . . , qn) mod q ̸= G(q1, . . . , qn) mod q with probability ≥(1−1/q)n. (In particular, if n = 1000 and q = 231 −1, different functions lead to different “hash values” under this scheme with probability at least 0.9999995.)

Verified: no
Solve time: 2m43s

Solution

Let $H$ be an $m\times n$ parity-check matrix over $\mathbb{F}_2$, and let

$$ f(x)= [Hx=0], \qquad x=(x_1,\dots,x_n)^T. $$

Fix a variable order $x_1,\dots,x_n$. For $0\le k\le n$, write $H_k$ for the $m\times k$ submatrix consisting of the first $k$ columns of $H$, and define

$$ r_k = \operatorname{rank}(H_k). $$

For a partial assignment $u=(x_1,\dots,x_k)$, the syndrome is

$$ s(u)=H_k u \in \mathbb{F}_2^m. $$

The subfunction induced by $u$ on the remaining variables $x_{k+1},\dots,x_n$ is

$$ f_u(x_{k+1},\dots,x_n) = [H_{k+1..n}(x_{k+1},\dots,x_n) = s(u)]. $$

Two assignments $u,u'$ yield the same subfunction if and only if $s(u)=s(u')$, since equality of syndromes gives identical affine constraints on the remaining variables.

The map $u\mapsto s(u)$ has image equal to the column space of $H_k$, which has cardinality $2^{r_k}$. Hence the number of distinct subfunctions at level $k$ in the BDD equals $2^{r_k}$.

Each distinct subfunction corresponds to a unique BDD node at level $k$. Therefore the number of nonterminal nodes equals

$$ \sum_{k=0}^{n-1} 2^{r_k}, $$

since $k=n$ contributes only terminal subfunctions.

At level $n$, every assignment yields either consistency $s(u)=0$ or inconsistency $s(u)\ne 0$, so all consistent leaves merge into a single $\top$ node and all inconsistent leaves merge into a single $\bot$ node. This contributes exactly $2$ sink nodes.

Hence

$$ B(f)=\sum_{k=0}^{n-1} 2^{r_k} + 2. $$

Since $r_0=0$, this is equivalently

$$ B(f)=3+\sum_{k=1}^{n-1} 2^{r_k}. $$

For the Hamming code, $n=2^m-1$, and $H$ has as columns all nonzero vectors of $\mathbb{F}_2^m$. With the standard ordering in which the first $m$ columns form an invertible matrix, the rank growth satisfies

$$ r_k = k \quad (1\le k\le m), \qquad r_k=m \quad (m\le k\le n). $$

Substituting into the formula gives

$$ B(f)=\sum_{k=0}^{m}2^k + \sum_{k=m+1}^{n-1}2^m + 2. $$

The first sum is

$$ \sum_{k=0}^{m}2^k = 2^{m+1}-1. $$

The second sum contains $n-1-m$ terms, hence equals

$$ (n-1-m)2^m. $$

With $n=2^m-1$, this becomes

$$ (2^m-2-m)2^m. $$

Therefore

$$ B(f)=(2^{m+1}-1) + (2^m-2-m)2^m + 2. $$

Simplifying,

$$ (2^{m+1}-1)+2 = 2^{m+1}+1, $$

$$ B(f)=2^{m+1}+1 + 2^{2m} - (m+2)2^m. $$

Since $2^{m+1} = 2\cdot 2^m$, this becomes

$$ B(f)=2^{2m} - m2^m + 1. $$

Thus for the Hamming code,

$$ \boxed{B(f)=2^{2m}-m2^m+1}. $$

For part (c), the received word $y=(y_1,\dots,y_n)$ and independent channel probabilities $p_k=\Pr[y_k=x_k]$ induce likelihood weights on assignments $x$:

$$ \Pr(x\mid y) \propto \prod_{k=1}^n \bigl(p_k^{[x_k=y_k]} (1-p_k)^{[x_k\ne y_k]}\bigr). $$

The MAP codeword maximizes this product over all $x$ satisfying $f(x)=1$. In the BDD of $f$, each root-to-$\top$ path corresponds to a codeword. Assign each HI edge at level $k$ the factor

$$ p_k \text{ if } y_k=1,\quad (1-p_k) \text{ if } y_k=0, $$

and each LO edge the complementary factor.

The MAP codeword is obtained by computing a maximum-weight path from the root to $\top$, where path weight is the product of edge weights. Equivalently, taking logarithms converts this to a longest-path problem in the acyclic BDD:

$$ \sum \log(\text{edge weight}). $$

Dynamic programming on the BDD, evaluating nodes in topological order, yields the optimal value at the root, and backtracking yields the corresponding codeword.

This completes the solution. ∎