TAOCP 7.1.2 Exercise 44

Section 7.1.2: Boolean Evaluation

Exercise 44. ▶ [26] (R. E. Ladner and M. J. Fischer, 1980.) Show that the problem of binary addition (25) can be viewed as a finite state transduction. Describe the Boolean chain that results from the construction of exercise 43 when $n = 2^m$, and compare it to the conditional-sum adder of exercise 41.

Verified: yes
Solve time: 1m40s

---

Setup

Let inputs be $(x_1,\ldots,x_n)$ and $(y_1,\ldots,y_n)$, and define binary addition as in (25), producing sum bits $(z_1,\ldots,z_n)$ and carry bits $(c_1,\ldots,c_{n+1})$ with $c_1=0$.

A finite-state transducer for addition uses alphabet $A={0,1}^2$ and output alphabet $B={0,1}$. The internal state records the carry, so $Q={0,1}$.

Define the transition on input $(x,y)\in A$ and state $c\in Q$ by

$z = x \oplus y \oplus c,$

$c' = (x \wedge y)\ \vee\ (c \wedge (x \oplus y)).$

Exercise 7.1.2.43(b) constructs all states $q_j$ in parallel by treating, for each position $j$, the local transition as a function $\tau_j:Q\to Q$ and computing the sequence of composed functions

$\tau_1,\ \tau_2\circ\tau_1,\ \ldots,\ \tau_n\circ\cdots\circ\tau_1.$

Solution

For each position $j$, define the transition function

$\tau_j(c) = (x_j \wedge y_j)\ \vee\ (c \wedge (x_j \oplus y_j)).$

Since $c\in{0,1}$, each $\tau_j$ is determined by the pair

$(a_j,b_j) = \bigl(\tau_j(0),\tau_j(1)\bigr).$

Compute these values:

$\tau_j(0)=x_j\wedge y_j,$

$\tau_j(1)=(x_j\wedge y_j)\ \vee\ (x_j\oplus y_j)=x_j\vee y_j.$

Hence each $\tau_j$ corresponds to a Boolean pair $(a_j,b_j)$ with

$a_j=x_j\wedge y_j,\qquad b_j=x_j\vee y_j.$

Composition of state functions corresponds to composition of these pairs. If

$\sigma(c)=(a,b),\quad \tau(c)=(a',b'),$

then

$\tau\circ\sigma(0)=a'\vee(b'\wedge a),$

$\tau\circ\sigma(1)=a'\vee(b'\wedge b).$

Thus the set of state functions is closed under composition, and each position $j$ contributes one element of a finite algebra of size $4$ (all functions $Q\to Q$).

Exercise 7.1.2.43(b) applies Ladner–Fischer prefix construction to this associative composition. The sequence

$\tau_1,\ \tau_2,\ \ldots,\ \tau_n$

is evaluated into all prefixes

$\rho_j = \tau_j\circ\cdots\circ\tau_1$

using a balanced binary tree of composition.

Each composition node combines two already computed prefix functions, so the resulting Boolean chain has cost proportional to the number of nodes in the tree. A full binary tree over $n$ leaves has $n-1$ internal composition nodes, and each node corresponds to a constant number of Boolean operations implementing the composition formulas above. Hence the total cost is $O(n)$.

When $n=2^m$, the tree has height $m$, so the depth of the construction is $m$.

Once all carries are available, the sum bits are computed locally by

$z_j = x_j \oplus y_j \oplus c_j,$

which adds only constant additional cost per position and does not increase asymptotic depth beyond the prefix computation.

Therefore the Boolean chain produced by Exercise 43 yields a parallel prefix adder computing all carries in depth $m=\log_2 n$ and total size $O(n)$.

Verification

Each state function $\tau_j$ depends only on $(x_j,y_j)$ and the incoming carry, so it is correctly represented as a unary function on $Q={0,1}$. The formulas for $\tau_j(0)$ and $\tau_j(1)$ follow directly by substituting $c=0$ and $c=1$ into the carry recurrence.

Closure under composition is verified by evaluating $\tau(\sigma(c))$ separately at $c=0$ and $c=1$, yielding expressions depending only on $(a,b)$ and $(a',b')$, so the composed function is again a valid state function.

The Ladner–Fischer construction applies because composition is associative, since function composition is associative. The depth bound follows from the height of a balanced binary tree on $n$ inputs.

The cost bound follows because each internal node performs a fixed number of Boolean operations implementing the composition formulas, so the number of operations is proportional to the number of tree nodes.

Notes

The resulting construction is a prefix computation over the monoid of carry-transition functions on ${0,1}$. It is structurally identical to a parallel-prefix adder.

The conditional-sum adder of Exercise 7.1.2.41 achieves the same asymptotic depth $O(\log n)$ by recursively computing both possible carry outcomes and selecting with multiplexers. The present construction differs in representation: it encodes each stage as an element of a finite function monoid and computes all prefixes directly, rather than maintaining paired sums. Both methods yield balanced tree structure; both achieve linear size and logarithmic depth. ∎