Logic Circuits - Models of Computation: Exploring the Power of Computing - page 52

y 2 y 1 y 0

f ( 3 )
encode

f ( 2 )
encode

x 7 x 6 x 5 x 4 x 3 x 2 x 1 x 0

Figure 2.11 The recursive construction of an encoder circuit on eight inputs.

( y 1 , y 0 )=( 0, 1 ) ,whereasif x =( 0, 0, 1, 0, 0, 0, 0, 0 ) ,then y 2 = 1and ( y 1 , y 0 )=( 0, 1 ) .
Thus, after computing y n− 1 as the OR of the 2 n− 1 high-order inputs, the remaining output
bits can be obtained by supplying to an encoder on 2 n− 1 inputs the 2 n− 1 low-order bits if
y n− 1 = 0orthe2 n− 1 high-order bits if y n− 1 = 1. It follows that in both cases we can
supply the vector δ =( x 2 n − 1

x 0 ) of 2 ( n− 1 ) ∨ x 2 ( n − 1 ) − 1 , x 2 n − 2 ∨ x 2 ( n − 1 ) − 2 , ... , x 2 ( n − 1 ) ∨

components to the encoder on 2 ( n− 1 ) inputs. This is illustrated in Fig. 2.11 .
Let's now derive upper bounds on the size and depth of the optimal circuit for f ( n )

encode .

Clearly C Ω 0 f ( 1 )

encode = 0, since no gates are needed in this case.
From the construction described above and illustrated in Fig. 2.11 , we see that we can construct
a circuit for f ( n )

encode = 0and D Ω 0 f ( 1 )

encode in a two-step process. First, we form y n− 1 as the OR of the 2 n− 1 high-
order variables in a balanced OR tree of depth n using 2 n− 1 1 OR 's . Second , we form

the vector δ with a circuit of depth 1 using 2 n− 1 OR 's and supply it to a copy of a circuit
for f ( n− 1 )

−

encode . This provides the following recurrences for the circuit size and depth of f ( n ) encode

because the depth of this circuit is no more than the maximum of the depth of the OR tree and
1 more than the depth of a circuit for f ( n− 1 )

encode :

C Ω 0 f ( n )

encode

1 + C Ω 0 ( f ( n− 1 )

2 n

≤ −

encode )

(2.4)

D Ω 0 f ( n )

encode

1, D Ω 0 ( f ( n− 1 )

≤ max( n −

encode )+ 1 )

(2.5)

The solutions to these recurrences are stated as the following lemma, as the reader can show.
(See Problem 2.14 .)

LEMMA 2.5.3 The encoder function f ( n )

encode has the following circuit size and depth bounds:
C Ω 0 f ( n )

encode

2 n + 1

≤ − ( n + 3 )

D Ω 0 f ( n )

encode

≤ n −

1