Information Technology Reference
In-Depth Information
Thus, efficient circuits for the elementary symmetric functions yield efficient circuits for gen-
eral symmetric functions.
An efficient circuit for the elementary symmetric functions can be obtained from a circuit
for counting the number of 1's among the variables x .Ths counting function f ( n )
count
:
n
→B log 2 ( n + 1 ) produces a
B
log 2 ( n + 1 )
-bit binary number representing the number of
1's among the n inputs x 1 , x 2 , ... , x n .
A recursive construction for the counting function is shown in Fig. 2.21 (b) when m =
2 l + 1
1. The m inputs are organized into three groups, the first 2 l
1 Boolean variables u ,
the second 2 l
1 variables v , and the last variable x m . The sum is represented by l “sum bits”
s ( l + 1 )
j
1, and the “carry bit” c ( l + 1 )
l−
j
l
,0
. This sum is formed by adding in a ripple
1
adder the outputs s ( l )
j
2, and c ( l + 1 )
l
,0
j
l
from the two counting circuits, each on
2 l
1inputs,andthe m th input x m . (We abuse notation and use the same variables for the
outputs of the different counting circuits.) The counting circuit on 2 2
1 = 3inputsisthe
full adder of Fig. 2.21 (a). From this construction we have the following theorem:
LEMMA 2.11.1 For n = 2 k
2 , the counting function f ( n )
n
→B log 2 ( n + 1 )
1 , k
count :
B
can be realized with the following circuit size and depth over the basis Ω=
{∧
⊕}
,
,
:
C Ω f ( n )
count
5 ( 2 k
k
1 )
D Ω f ( n )
count
4 k
5
Proof Let C ( k )= C Ω f ( n )
count and D ( k )= D Ω f ( n )
count when n = 2 k
1. Clearly,
C ( 2 )= 5and D ( 2 )= 3 since a full adder over Ω=
{∧
⊕}
,
,
hasfivegatesanddepth3.
The following inequality is immediate from the construction:
C ( k )
2 C ( k
1 )+ 5 ( k
1 )
s ( l + 1 )
l− 1
s ( l + 1 )
l− 2
s ( l + 1 )
j
s ( l + 1 )
0
s ( l + 1 )
j
c ( l + 1 )
l
c ( l + 1 )
l
c ( l + 1 )
j + 1
c ( l + 1 )
j
c ( l + 1 )
1
1
2
x m
FA
FA
FA
FA
1
c ( l + 1 )
j + 1
c ( l + 1 )
j
Full Adder
s ( l )
l−
s ( l )
j
s ( l )
0
s ( l )
l−
s ( l )
j
s ( l )
0
2
2
c ( l )
l−
c ( l )
l−
1
1
2
f (( m− 1 ) / 2 )
count
f (( m− 1 ) / 2 )
count
3
s ( l )
j
s ( l )
j
u
v
(a)
(b)
Figure 2.21 A recursive construction for the counting function f ( m )
count , m = 2 l + 1
1.
 
Search WWH ::




Custom Search