TAOCP 7.1.1 Exercise 90
Let a CI-net module computing $\oplus$ be available, with two inputs $a,b$ and output $a \oplus b$, where $\oplus$ is associative by equation (4) and satisfies $x \oplus 0 = x$ by equation (5).
Exercise 90. [21] [21] Construct a CI-net with input bits $x_1 \ldots x_s$ and output bits $y_1 \ldots y_t$, where $y_1 = \cdots = y_{t-1} = 0$ and $y_t = x_1 \oplus \cdots \oplus x_s$. Try for only $O(\log t)$ levels of delay.
Verified: yes
Solve time: 1m15s
Solution
Let a CI-net module computing $\oplus$ be available, with two inputs $a,b$ and output $a \oplus b$, where $\oplus$ is associative by equation (4) and satisfies $x \oplus 0 = x$ by equation (5).
Construct a full binary tree with $t$ leaves and with $\lceil \log_2 t \rceil$ levels. Label the leaves $L_1,\ldots,L_t$. Assign
$$ L_i = x_i \quad (1 \le i \le s), $$
and for all remaining indices $i > s$, set
$$ L_i = 0. $$
Since $x \oplus 0 = x$, replacing any missing input by $0$ does not change the value of the total $\oplus$ of all leaves.
Place a $\oplus$-module at every internal node of the tree. Each internal node computes the exclusive-or of its two children. By associativity of $\oplus$, the value computed at the root is
$$ x_1 \oplus \cdots \oplus x_s \oplus 0 \oplus \cdots \oplus 0 ;=; x_1 \oplus \cdots \oplus x_s. $$
Define the output wires by setting
$$ y_t = \text{(value at the root)}, \qquad y_1 = \cdots = y_{t-1} = 0. $$
The outputs $y_1,\ldots,y_{t-1}$ are realized by constant-0 sources.
Each level of the binary tree corresponds to one layer of $\oplus$-operations, so the signal from any leaf to the root passes through exactly $\lceil \log_2 t \rceil$ modules. The output wiring from the root to $y_t$ adds no additional $\oplus$-depth, and the constant outputs introduce no additional delay. Hence the CI-net has at most $O(\log t)$ levels of delay.
This completes the construction. ∎