Information Technology Reference
In-Depth Information
2.5.4 Decoder
A decoder is a function that reverses the operation of an encoder: given an
n
-bit binary address,
it generates 2
n
bits with a single 1 in the position specified by the binary number. Decoders
are used in the design of random-access memory units (see Section
3.5
) and of the multiplexer
(see Section
2.5.5
).
The
decoder function
f
(
n
)
2
n
has
n
input variables
x
=(
x
n−
1
,
...
,
x
1
,
x
0
)
and 2
n
output variables
y
=(
y
2
n
−
1
,
...
,
y
1
,
y
0
)
;thatis,
f
(
n
)
n
decode
:
B
→B
decode
(
x
)=
y
.Let
c
be a binary
. All components of the binary 2
n
-tuple
y
are zero
n
-tuple corresponding to the integer
|
c
|
except for the one whose index is
,namely
y
|
c
|
. Thus, the minterm functions in the variables
x
are computed as the output of
f
(
n
)
|
c
|
decode
.
A direct realization of the function
f
(
n
)
decode
can be obtained by realizing each minterm
1
)
2
n
gates and has depth
independently. This circuit uses
(
2
n
−
log
2
n
+
1. Thus we have
the following bounds over the basis
Ω
0
=
{∧
,
∨
,
¬}
:
C
Ω
0
f
(
n
)
decode
1
)
2
n
≤
(
2
n
−
D
Ω
0
f
(
n
)
decode
≤
log
2
n
+
1
A smaller upper bound on circuit size and depth can be obtained from the recursive con-
struction of Fig.
2.12
, which is based on the observation that a minterm on
n
variablesisthe
AND
of a minterm on the first
n/
2 v
ar
iables an
d
a mi
n
term on the second
n/
2 variables. For
example,
w
hen
n
=
4, the minterm
x
3
∧
x
2
∧
x
1
∧
x
0
is
ob
vio
u
sly equal to the
AND
of the
minterm
x
3
∧
x
2
in the variables
x
3
and
x
2
and the minterm
x
1
∧
x
0
in the variables
x
1
and
x
0
.
Thus, when
n
is even, the minterms that are the outputs of
f
(
n
)
decode
can be formed by
AND
ing
y
15
y
14
y
13
y
12
y
11
y
10
y
9
y
8
y
7
y
6
y
5
y
4
y
3
y
2
y
1
y
0
f
(
4
)
decode
v
3
v
2
v
1
v
0
u
3
u
2
u
1
u
0
f
(
2
)
decode
f
(
2
)
decode
x
3
x
2
x
1
x
0
Figure 2.12
The construction of a decoder on four inputs from two copies of a decoder on two
inputs.
Search WWH ::
Custom Search