Information Technology Reference
In-Depth Information
every minterm generated by a circuit for
f
(
n/
2
)
decode
on the variables
x
n/
2
−
1
,
...
,
x
0
with every
minterm generated by a circuit for
f
(
n/
2
)
decode
on the variables
x
n−
1
,
...
,
x
n/
2
, as suggested in
Fig.
2.12
.
The new circuit for
f
(
n
)
decode
has a size that is at most twice that of a circuit for
f
(
n/
2
)
decode
plus 2
n
for the
AND
gates that combine minterms. It has a depth that is at most 1 more than
the depth of a circuit for
f
(
n/
2
)
decode
.Thus,when
n
is even we have the following bounds on the
circuit size and depth of
f
(
n
)
decode
:
C
Ω
0
f
(
n
)
decode
2
C
Ω
0
f
(
n/
2
)
decode
+
2
n
≤
D
Ω
0
f
(
n
)
decode
D
Ω
0
f
(
n/
2
)
decode
+
1
≤
Specializing the first bounds given above on the size and depth of a decoder circuit to one on
n/
2 inputs, we have the bound in Lemma
2.5.4
. Furthermore, since the output functions are
all different,
C
Ω
0
f
(
n
)
decode
is at least 2
n
.
LEMMA
2.5.4
For
n
even the decoder function
f
(
n
)
decode
has the following circuit size and depth
bounds:
C
Ω
0
f
(
n
)
decode
2
n
2
n
+(
2
n
2
)
2
n/
2
≤
≤
−
D
Ω
0
f
(
n
)
decode
≤
log
2
n
+
1
The circuit size bound is linear in the number of outputs. Also, for
n
≥
12, the exact value of
C
Ω
0
f
(
n
)
decode
is known to within 25
%
. Since each output depends on
n
inputs, we will see
in Chapter
9
that the upper bound on depth is exactly the depth of the smallest depth circuit
for the decoder function.
2.5.5 Multiplexer
The
multiplexer function
f
(
n
)
2
n
+
n
has two vector inputs,
z
=(
z
2
n
−
1
,
...
,
z
1
,
z
0
)
and
x
=(
x
n−
1
,
...
,
x
1
,
x
0
)
,where
x
is treated as an address. The output of
f
(
n
)
mux
:
B
→B
mux
is
v
=
z
j
,where
j
=
is the integer represented by the binary number
x
.Thisfunctionis
also known as the
storage access function
because it simulates the access to storage made by a
random-access memory with one-bit words. (See Section
3.5
.)
The similarity between this function and the decoder function should be apparent. The
decoder function has
n
inputs,
x
=(
x
n−
1
,
...
,
x
1
,
x
0
)
,and2
n
outputs,
y
=(
y
2
n
−
1
,
...
,
y
1
,
y
0
)
,where
y
j
=
1if
j
=
|
x
|
|
x
|
and
y
j
=
0 otherwise. Thus, we can form
v
=
z
j
as
v
=(
z
2
n
−
1
∧
y
2
n
−
1
)
∨···∨
(
z
1
∧
y
1
)
∨
(
z
0
∧
y
0
)
This circuit uses a circuit for the decoder function
f
(
n
)
decode
plus 2
n
AND
gates and 2
n
1
OR
gates. It adds a depth of
n
+
1 to the depth of a decoder circuit. Lemma
2.5.5
follows
immediately from these observations.
−
Search WWH ::
Custom Search