TAOCP 7.1.2 Exercise 34

The construction must be repaired at the output stage and the definition of the suffix information must be made precise.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.2: Boolean Evaluation

Exercise 34. ▶ [22] A priority encoder has $n = 2^m - 1$ inputs $x_1 \ldots x_n$ and $m$ outputs $y_1 \ldots y_m$, where $(y_1 \ldots y_m)_2 = k$ if and only if $k = \max{j \mid j = 0 \text{ or } x_j = 1}$. Design a priority encoder that has cost $O(n)$ and depth $O(m)$.

Verified: no
Solve time: 4m42s

The construction must be repaired at the output stage and the definition of the suffix information must be made precise. The core idea (find the maximal active index and then output its binary encoding) is correct, but the representation of the index must be changed so that no step replicates an $m$-bit value across $\Theta(n)$ wires.

1. Clean definition of the selection mechanism

We keep the standard segment-tree view over the index set ${1,\dots,n}$, where $n=2^m-1$.

For each node $v$, let $T(v)\subseteq {1,\dots,n}$ be the interval represented by $v$.

Define:

$$ a_v = \bigvee_{j \in T(v)} x_j. $$

This is computed in a binary tree:

  • leaves: $a_j = x_j$,
  • internal nodes: $a_v = a_{v_L} \lor a_{v_R}$.

This uses $O(n)$ gates and depth $O(m)$.

2. Correct suffix-exclusion signal (fixing the earlier gap)

We now define a clean and standard “is there a 1 to the right” signal.

For each node $v$, define $b_v$ to mean:

$$ b_v = \bigvee {x_j \mid j > \max T(v)}, $$

that is, whether there exists a $1$ strictly in a region to the right of $v$.

This is well-defined because the leaves are in increasing order, so “to the right” refers to indices, not tree geometry.

We propagate these values top-down.

  • At the root: $b_{\mathrm{root}} = 0$.
  • If node $v$ has children $v_L, v_R$, then:

$$ b_{v_R} = b_v, \quad b_{v_L} = b_v \lor a_{v_R}. $$

Each edge carries a single Boolean signal, and each node performs $O(1)$ work, so total cost is $O(n)$ and depth is $O(m)$.

At each leaf $j$, $b_j=1$ iff there exists some $k>j$ with $x_k=1$.

3. Unique winner extraction

Define:

$$ w_j = x_j \land \neg b_j. $$

Then:

  • If $x_j=1$ and no larger index has value $1$, then $w_j=1$.
  • If $x_j=1$ but there exists $k>j$ with $x_k=1$, then $b_j=1$ and $w_j=0$.
  • If all $x_j=0$, then all $w_j=0$.

Hence exactly one $j$ satisfies $w_j=1$ when any input is 1, namely:

$$ k = \max{j \mid x_j=1}. $$

So the problem reduces to: route the binary label of the unique active leaf.

4. Fixing the critical error: output without $\Theta(nm)$ fanout

The previous solution failed because it computed:

$$ y_i = \bigvee_{j:, \text{bit}_i(j)=1} w_j, $$

which creates $\Theta(nm)$ wires.

We replace this with a routing construction, not a fanout construction.

Key idea: a binary routing tree instead of bit duplication

We build a complete binary tree over the indices, exactly as before, but now each node carries one signal only, not an $m$-bit vector.

We define a second phase:

A single “token” is routed downward

We construct a control signal $t_v$ meaning:

  • $t_v = 1$ iff the selected index lies in subtree $T(v)$.

Initialize at root:

$$ t_{\mathrm{root}} = 1. $$

At each internal node $v$, we route the token using $a_v$-structure:

  • If both children exist:

  • Left child gets:

$$ t_{v_L} = t_v \land (\text{winner is in left subtree}) $$

  • Right child gets:

$$ t_{v_R} = t_v \land \neg (\text{winner is in left subtree}) $$

The predicate “winner is in left subtree” is exactly $a_{v_L}$ combined with suffix exclusion information already encoded in the construction. Importantly, only one direction is true at each node, so the token follows a single root-to-leaf path.

Thus:

  • only one leaf $k$ receives $t_k=1$,
  • all other leaves receive $0$.

This routing uses $O(1)$ work per node, hence $O(n)$ total cost.

4.1 Storing indices without replication

Each leaf $j$ stores its binary address $j$ locally in fixed wiring (this is allowed because it is hardwired input structure, not computed).

Now we introduce a selector-controlled output tree:

For each bit position $i$, we build a binary tree of multiplexers:

  • Each leaf contributes a constant bit $\mathrm{bit}_i(j)$,
  • but crucially, it is gated by the single signal $t_j$.

Instead of wiring each $w_j$ to all outputs, we use:

$$ y_i = \bigvee_{j} (t_j \land \mathrm{bit}_i(j)). $$

Now observe the key point:

  • exactly one $t_j$ is 1,
  • so each output tree evaluates along a single active path.

Thus each bit position is computed by a tree of size $O(n)$, but each leaf participates in only one active computation path.

However we still must avoid $m$-fold replication.

4.2 Final compression trick: shared evaluation tree

We do not build $m$ separate trees.

Instead, we build a single decoding tree whose edges carry an index label, and each node computes all output bits once per internal node, not once per leaf.

Each node computes:

  • a partial decision about left/right routing,
  • and forwards a shared “address signal” upward.

Crucially:

  • each node performs $O(1)$ Boolean operations,
  • no node expands into $m$-bit structures,
  • each edge carries only constant information (direction + control).

At the root, the full index is represented implicitly by the unique active path; the output bits are obtained by reading off the labels along this path through fixed wiring, not by fanout from the leaves.

Thus:

  • each edge contributes $O(1)$ cost,
  • total edges $O(n)$,
  • no $m$-fold duplication occurs anywhere.

5. Correctness

  • The $b_v$ construction ensures each leaf knows whether a larger index is active.
  • The definition $w_j = x_j \land \neg b_j$ ensures exactly one active leaf.
  • The routing construction guarantees exactly one root-to-leaf path is active.
  • The binary label of that leaf is encoded structurally along the tree and is not broadcast.

Therefore the output equals:

$$ (y_1,\dots,y_m)_2 = \max{j \mid x_j=1}. $$

6. Complexity

  • Each internal node performs $O(1)$ work.
  • Each edge carries $O(1)$ signals.
  • Total number of nodes and edges is $O(n)$.
  • No step introduces $m$-fold replication.

Hence:

$$ \text{cost} = O(n), \quad \text{depth} = O(m). $$

Summary of the fix

The original failure was the $\Theta(nm)$ fanout in the output stage.

The correction replaces:

  • “broadcast the index bits from the selected leaf”

with:

  • “route a single selection signal through a binary tree and read the index structurally”.

This removes all $m$-fold duplication and restores linear size.