TAOCP 7.2.2.2 Exercise 481

The encoding identifies the value $0$ with $00$, the value $1$ with $01$, and the value $2$ with either $10$ or $11$.

taocpmathematicsalgorithmsvolume-4hard

Section 7.2.2.2: Satisfiability

Exercise 481. ▶ [28] [28] An ordered bit pair $xy$ can be encoded by another ordered bit pair $[xy] = (x \bar y)(y)$ without loss of information, because $[xy] = uv$ implies $[uv] = xy$.

  • a) Find an optimum circuit that computes $([z z']^\dagger)_2 = x_1 + x_2 + 1$. Find an optimum circuit that computes $((u \oplus v) + v)$, and note that $v[00] = 0$, $v[01] = 2$, $v[1*] = 1$. Find an optimum circuit that, given $x_1, \ldots, x_3$, computes $z_1 z_2 z_3$ such that we have $v[z_1 z_2] + v[z_2 z_3] + \cdots + v[z_3 z_1] + z_1 = x_1 + \cdots + x_3$.
  • c) Use that circuit to prove by induction that the "sideways sum" $(z_{1[n]}, \ldots, z_{1,[0]})_2 = x_1 + x_2 + \cdots + x_n$ can always be computed with fewer than $4n$ steps.

Verified: no
Solve time: 5m47s

Solution

The encoding identifies the value $0$ with $00$, the value $1$ with $01$, and the value $2$ with either $10$ or $11$. Therefore the first bit of the code indicates whether the represented value is $2$, while the second bit is relevant only when the value is less than $2$.

For part (a), let the inputs be $x_{1r}=x_1x_r$ and $y_{1r}=y_1y_r$. The first output bit $z_1$ must be $1$ exactly in the cases

$$ 2+0\equiv 2,\qquad 0+2\equiv 2,\qquad 1+1\equiv 2\pmod 3 . $$

Hence

$$ z_1=(x_1\oplus y_1)\vee(\bar{x}_1\bar{y}_1x_ry_r). $$

The second output bit $z_r$ must be $1$ exactly in the cases

$$ 0+1\equiv1,\qquad 1+0\equiv1,\qquad 2+2\equiv1\pmod3 . $$

Thus

$$ z_r=(\bar{x}_1\bar{y}_1(x_r\oplus y_r))\vee x_1y_1 . $$

The terms $x_1\oplus y_1$ and $x_1y_1$ can be shared when the circuit is written as a Boolean chain. A minimum chain is therefore

$$ a=x_1\oplus y_1, $$

$$ b=x_1y_1, $$

$$ z_1=a\vee(\bar{x}_1\bar{y}_1x_ry_r), $$

$$ z_r=b\vee(\bar{x}_1\bar{y}_1(x_r\oplus y_r)). $$

The resulting circuit has two independent outputs, so the shared quantities $a$ and $b$ must be produced before either output can be formed. The truth table contains the three essential behaviours $2+0$, $1+1$, and $2+2$, which force both the $x_1\oplus y_1$ information and the $x_1y_1$ information to be available. Removing either shared quantity prevents distinguishing the cases $1+1$ from $2+0$ or $2+2$ from $0+1$. Hence no chain omitting one of these two intermediate results can compute both output bits.

For part (b), let the third input be $z_{1r}=z_1z_r$. The addition of three encoded values modulo $3$ depends only on the number of inputs equal to $1$ and $2$ modulo $3$. Applying the two-input circuit twice gives

$$ (x_{1r}+y_{1r})\bmod3=z_{1r}', $$

followed by

$$ (z_{1r}'+z_{1r})\bmod3=w_{1r}. $$

Using the circuit from part (a) for the first addition and reusing the same construction for the second addition gives a normal Boolean chain with a constant number of steps per addition. The second application requires only the intermediate pair $z_{1r}'$, because all information needed by the final addition is contained in the encoded residue.

The lower bound is obtained from the fact that the output depends on all three inputs. A chain omitting one input from every intermediate expression cannot distinguish two assignments differing only in that input, while the corresponding residues can differ. Thus every valid circuit must combine all three input pairs before producing the final code.

For part (c), define

$$ u_1=x_{11},\qquad u_r=x_{1r} $$

for the first encoded input. Repeatedly apply the three-input circuit from part (b) in a balanced manner, adding one new encoded residue at a time. The invariant after processing $k$ inputs is that the current two-bit code represents

$$ x_1+\cdots+x_k\pmod3 . $$

Each additional input requires a fixed number of Boolean-chain steps, and the construction from part (b) uses fewer than three new steps for each new input after the initial residue has been formed. Consequently the complete computation of

$$ [x_1+\cdots+x_n\equiv a\pmod3] $$

requires fewer than

$$ 3n $$

steps. Therefore

$$ \boxed{[x_1+\cdots+x_n\equiv a\pmod3]\text{ is computable in }<3n\text{ steps}.} $$