Information Technology Reference
In-Depth Information
z
1
z
(
K/
2
)
−
1
z
(
K/
2
)
z
(
K/
2
)+
1
z
K−
1
...
...
...
z
1
z
K
∗
−
1
ν
(
k−
1
)
...
s
1
s
∗
K
∗
−
1
K
∗
=
2
k−
1
K
=
2
k
...
...
s
1
s
(
K/
2
)
−
1
s
(
K/
2
)
s
(
K/
2
)+
1
s
K−
1
Figure 9.8
A circuit for
ν
(
k
)
n
n
,
n
=
K −
1,
K
=
2
k
. It is given the sor
t
ed
n
-tuple
:
B
→B
s
as input, where
s
j
≥ s
j
+
1
for 1
≤ j ≤ n
, and produces as output
z
,where
z
j
=
s
j
.
The base case is a circuit for
ν
(
1
)
. This circuit has one input,
s
1
,andoneoutput,
z
1
=
s
1
,
and can be realized by one negation and no other gates.
We construct a circuit for
ν
(
k
)
from one for
ν
(
k−
1
)
using 2
n
additional gates and in-
creasing the depth by three, as shown in Fig.
9.8
. Let the inputs and outputs to the circuit
for
ν
(
k−
1
)
be
s
i
and
z
i
,1
K
∗
−
1,
wh
ere
K
∗
=
K/
2. It follows that
s
i
≥
s
i
+
1
≤
i
≤
1. By induction
z
i
=
s
∗
i
for 1
for 1
n
.
To show that the
j
th output of the circuit for
ν
(
k
)
is
z
j
=
s
j
,weconsidercases. If
s
2
k
−
1
=
0, then
s
j
=
0for
j>K/
2. In this case the
j
th circuit output,
(
K/
2
)
<j
≤
i
≤
(
K/
2
)
−
≤
i
≤
≤
K
1, satisfies
z
j
=
1 (the corresponding
o
utput gate is
OR
), which is the correct value.
Also, for 1
−
1,
z
j
=
z
j
=
s
j
since the inputs to
t
h
e
circuit
f
or
ν
(
k−
1
)
are
s
1
,
s
2
,
...
,
s
(
K/
2
)
−
1
(
s
j
=
0for
j>K/
2) and its outputs are
s
1
,
s
2
,
...
,
s
(
K/
2
)
−
1
.On
the other hand, if
s
K/
2
=
1, then
s
j
=
1and
z
j
=
0for
j
≤
j
≤
(
K/
2
)
−
≤
(
K/
2
)
−
1 (the corresponding
output gate is
AND
). Also, for
(
K/
2
)+
1
1,
z
j
=
z
j
=
s
j
since the inputs to
the circuit for
ν
(
k−
1
)
are
s
(
K/
2
)+
1
,
...
,
s
K−
1
and its outputs are
s
(
K/
2
)+
1
,
...
,
s
(
K/
2
)
−
1
.
It follows that
k
=log
2
(
n
+
1
)
negations are used. The circuit for
ν
(
k
)
uses a total of
C
(
k
)=
C
(
k
≤
j
≤
K
−
1
)+
2
k
+
1
−
−
3gates,where
C
(
1
)=
1. The solution to this recurrence
is
C
(
k
)=
4
(
2
k
)
4. Also, the circuit for
ν
(
k
)
has depth
−
3
k
−
4
=
4
n
−
3
log
2
n
−
Search WWH ::
Custom Search