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