CF 103870Q - Food Poisoning
Let $H$ be an $m times n$ binary matrix and let $$f(x) = [Hx = 0],$$ where arithmetic is over $mathbb{F}2$. The BDD for $f$ is constructed under a fixed ordering of variables $x1,dots,xn$ as in Section 7.1.4.
Rating: -
Tags: -
Solve time: 31s
Verified: no
Solution
Solution
Let $H$ be an $m \times n$ binary matrix and let
$$f(x) = [Hx = 0],$$
where arithmetic is over $\mathbb{F}2$. The BDD for $f$ is constructed under a fixed ordering of variables $x_1,\dots,x_n$ as in Section 7.1.4. Each node at level $k$ corresponds to a subfunction obtained by fixing $x_1,\dots,x{k-1}$.
At level $k$, the remaining condition on the unfixed variables $x_k,\dots,x_n$ is determined by the residual linear system obtained by eliminating the first $k-1$ columns of $H$ using the fixed values.
For a partial assignment $x_1,\dots,x_{k-1}$, write the vector
$$u = \sum_{j=1}^{k-1} x_j H_j,$$
where $H_j$ is the $j$-th column of $H$. The constraint $Hx=0$ becomes
$$\sum_{j=k}^{n} x_j H_j = u,$$
or equivalently
$$H^{(k)} x^{(k)} = u,$$
where $H^{(k)}$ is the submatrix consisting of columns $k,\dots,n$, and $x^{(k)} = (x_k,\dots,x_n)^T$.
Thus each node in the BDD at level $k$ is uniquely determined by a reachable syndrome vector $u$ in the column span of the prefix matrix $H_{1..k-1}$, together with the remaining matrix $H^{(k)}$.
Two partial assignments yield the same BDD node at level $k$ if and only if they produce the same syndrome $u$, since the continuation condition depends only on $u$. Hence the nodes at level $k$ are in one-to-one correspondence with the image space
$$U_k = {u : u = \sum_{j=1}^{k-1} x_j H_j,\ x_j \in {0,1}}.$$
The mapping $x_1,\dots,x_{k-1} \mapsto u$ is linear over $\mathbb{F}_2$, so $U_k$ is a vector space generated by the first $k-1$ columns of $H$. Therefore
$$|U_k| = 2^{\operatorname{rank}(H_{1..k-1})}.$$
Each distinct syndrome $u \in U_k$ corresponds to exactly one BDD node at level $k$, since reduction identifies subfunctions with identical continuation systems, and ordering prevents reuse across different levels.
Thus the number of nodes at level $k$ equals $2^{r_k}$, where $r_k = \operatorname{rank}(H_{1..k-1})$. The total BDD size is
$$B(f) = 1 + 1 + \sum_{k=1}^{n} 2^{r_k},$$
where the two initial $1$ terms correspond to the sink nodes $\bot$ and $\top$, since both are present in the reduced BDD.
For the Hamming code, $n = 2^m - 1$, and $H$ is the $m \times n$ matrix whose columns are all nonzero vectors in $\mathbb{F}_2^m$. Any set of $t$ distinct columns is linearly independent if and only if it contains at most $m$ columns, since every dependency among nonzero vectors in $\mathbb{F}_2^m$ has size at least $m+1$. Hence for every prefix containing $k-1 < m$ columns,
$$r_k = k-1.$$
Once $k-1 \ge m$, the rank stabilizes at $m$, since all of $\mathbb{F}_2^m$ is spanned.
Therefore
$$r_k = \begin{cases} k-1 & k \le m+1,\ m & k \ge m+1. \end{cases}$$
Substituting into the size formula gives
$$B(f) = 2 + \sum_{k=1}^{m} 2^{k-1} + \sum_{k=m+1}^{2^m-1} 2^m.$$
The first sum evaluates to
$$\sum_{k=1}^{m} 2^{k-1} = 2^m - 1.$$
The second sum contains $2^m - 1 - m$ terms, each equal to $2^m$, hence equals
$$(2^m - 1 - m)2^m.$$
Combining terms,
$$B(f) = 2 + (2^m - 1) + (2^m - 1 - m)2^m.$$
Simplifying,
$$B(f) = 1 + 2^m + (2^m - 1 - m)2^m.$$
Expanding,
$$B(f) = 1 + 2^m + 2^{2m} - 2^m - m2^m.$$
Cancellation yields
$$B(f) = 1 + 2^{2m} - m2^m.$$
Thus for the Hamming code,
$$\boxed{B(f) = 2^{2m} - m2^m + 1}.$$
For maximum-likelihood decoding, the received word $y$ defines a likelihood weight for each candidate codeword $x$,
$$P(y \mid x) = \prod_{k=1}^n p_k^{[x_k = y_k]} (1-p_k)^{[x_k \ne y_k]}.$$
Maximizing this is equivalent to maximizing the log-likelihood
$$\sum_{k=1}^n \left( x_k \log \frac{p_k}{1-p_k} \cdot (2y_k-1) \right),$$
up to additive constants independent of $x$.
The BDD for $f(x) = [Hx=0]$ restricts the search space to codewords. Each root-to-$\top$ path corresponds to a codeword, since only satisfying assignments survive evaluation.
A dynamic evaluation on the BDD computes, at each node corresponding to subfunction $g$, the optimal likelihood of completing the partial assignment through the subtree. If a node has variable $x_k$, the recurrence is
$$L(g) = \max{ L(g_{x_k=0}) + w_k(0),\ L(g_{x_k=1}) + w_k(1)},$$
where $w_k(b)$ is the log-likelihood contribution of setting $x_k=b$.
Evaluating this recurrence bottom-up on the acyclic BDD yields the maximum-likelihood codeword, since each node aggregates optimal completions of all suffix constraints represented by that node. This completes the construction of decoding via BDD evaluation. ∎