TAOCP 7.1.4 Exercise 263

Section 7.1.4: Binary Decision Diagrams

Exercise 263. [HM25] [HM25] A linear block code is the set of binary column vectors x = (x1, . . . , xn)T such that Hx = 0, where H is a given m × n “parity check matrix.” a) The linear block code with n = 2m −1, whose columns are the nonzero binary m-tuples from (0, . . . , 0, 1)T to (1, . . . , 1, 1)T, is called the Hamming code. Prove that the Hamming code is 1-error correcting in the sense of exercise 7–23. b) Let f(x) = [Hx = 0], where H is an m×n matrix with no all-zero columns. Show that the BDD profile of f has a simple relation to the ranks of submatrices of H mod 2, and compute B(f) for the Hamming code. c) In general we can let f(x) = [x is a codeword] define any block code. Suppose some codeword x = x1 . . . xn has been transmitted through a possibly noisy channel, and that we’ve received the bits y = y1 . . . yn, where the channel delivers yk = xk with probability pk for each k independently. Explain how to determine the most likely codeword x, given y, p1, . . . , pn, and the BDD for f.

280 COMBINATORIAL SEARCHING 7.1.4

Verified: no
Solve time: 5m07s

---

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, $$

so

$$ 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. ∎