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

The size bound follows immediately. The depth bound requires a more careful analysis.
ShowninFig. 2.21 (a) is a full adder together with notation showing the amount by
which the length of a path from one input to another is increased in passing through it
when the full-adder circuit used is that shown in Fig. 2.14 and described by Equation 2.6 .
From this it follows that
D Ω c ( l + 1 )

j + 1 =max D Ω c ( l + 1 )

+ 2, D Ω s ( l j + 3

j

D Ω s ( l + 1 )

=max D Ω c ( l + 1 ) + 1, D Ω s ( l j + 2

j j

1, where s ( l )
l− 1 = c ( l )

≤ l and 0 ≤ j ≤ l −

for 2

1 . It can be shown by induction that

D Ω c ( k )

= 2 ( k + j )

1, and D Ω s ( k )

= 2 ( k + j )

l−

− ≤ j ≤ k − − ≤ j ≤ k −

3, 1 2, 0 2,

j j

k . (See Problem 2.16 .) Thus, D Ω f ( n )

count = D Ω c ( k )

1 =( 4 k

≤ −

5 ) . both for 2

k −

We now use this bound to derive upper bounds on the size and depth of symmetric func-
tions in the class S n , m .
THEOREM 2.11.1 Every symmetric function f ( n ) : B

n m can be realized with the following

→B

where φ ( k )= 5 ( 2 k circuit size and depth over the basis Ω= {∧ , ∨ , ⊕} − k − 1 ) :

C Ω f ( n )

2 ) 2 ( n + 1 )

≤ m ( n + 1 ) / 2 + φ ( k )+ 2 ( n + 1 )+( 2 log 2 ( n + 1 ) −

D Ω f ( n ) ≤ log 2 ( n + 1 ) + log 2 log 2 ( n + 1 ) −

5 4

for k =

log 2 ( n + 1 )

even.
Proof Lemma 2.11.1 establishes bounds on the size and depth of the function f ( n )

for

count

n = 2 k

and fill out the 2 k

−

1. For other values of n ,let k =

log 2 ( n + 1 ) − − n

1

variables with 0's.
The elementary symmetric functions are obtained by applying the value of f ( n )

count as
argument to the decoder function. A circui t for this function has been constructed that has
size 2 ( n + 1 )+( 2

2 ) 2 ( n + 1 ) and depth

log 2 ( n + 1 ) − log 2 log 2 ( n + 1 ) + 1.

(See Lemma 2.5.4 .Weusethefactthat2 log 2 m ≤ 2 m .) Thus, all elementary symmetric

functions on n variables can be realized with the following circuit size and depth:
C Ω e ( n )
0

2 ) 2 ( n + 1 ) , e ( n )

1

, ... , e ( n )

≤ φ ( k )+ 2 ( n + 1 )+( 2 log 2 ( n + 1 ) −

n

D Ω e ( n )
0

, e ( n )
1

, ... , e ( n )
n

≤ 4 k − 5 + log 2 log 2 ( n + 1 ) + 1

The expansion of Equation ( 2.15 ) can be used to realize an arbitrary Boolean symmetric
function. Clearly, at most n OR gates and depth

suffice to realize each one of m
arbitrary Boolean symmetric functions. (Since the v t are fixed, no AND s are needed.) This
number of OR scanbereducedto ( n

log 2 n

− 1 ) / 2 as follows: if ( n + 1 ) / 2 or more elementary

functions are needed, use the complementary set (of at most ( n + 1 ) / 2 functions) and

take the complement of the result. Thus, no more than ( n + 1 ) / 2 − 1 OR s are needed per

symmetric function (plus possibly one NOT ), and depth at most log 2 (( n + 1 ) / 2 ) + 1

≤ log 2 ( n + 1 ) .