Information Technology Reference
In-Depth Information
x
4
01010101
x
5
00110011
x
6
00001111
x
1
x
2
x
3
00001000100
00101100111
A
1
01010010001
01110110010
10000001001
A
2
10111011000
11010110110
11101000010
A
3
Figure 2.22
The rectangular representation of the defining table of a Boolean function used in
its
(
k
,
s
)
-Lupanov representation.
which
v
is the tuple of values of
f
i
when
a
∈
A
i
. (Note that the non-empty sets
B
i
,
v
for
different values of
v
are disjoint.) Let
f
(
c
)
n−k
i
,
v
(
b
):
B
→B
be defined as
i
,
v
(
b
)=
1if
b
B
i
,
v
0 t rwi .
∈
f
(
c
)
Finally, we let
f
(
r
)
i
,
v
(
a
):
B
k
→B
be the function that has value
v
j
,the
j
th component of
v
,
when
a
is the
j
th
k
-tuple in
A
i
:
i
,
v
(
a
)=
1if
a
is the
j
th element of
A
i
and
v
j
=
1
0 t rwi .
It follows that
f
i
(
x
)=
v
f
(
r
)
f
(
r
)
i
,
v
(
a
)
f
(
c
)
i
,
v
(
b
)
. Given these definitions,
f
can be expanded in
(
k
,
s
)
the following
-Lupanov representation
:
p
f
(
r
)
f
(
c
)
f
(
x
)=
i
,
v
(
a
)
∧
i
,
v
(
b
)
(2.19)
v
i
=
1
n
We now bound the number of logic elements needed to realize an arbitrary function
f
:
B
→
B
in this representation.
Consider the functions
f
(
r
)
i
,
v
(
a
)
for a fixed value of
v
. We construct a decoder circuit for
the minterms in
a
that has size at most 2
k
+(
k
2
)
2
k/
2
.Eachofthefunctions
f
(
r
)
−
can be
i
,
v
1and
s
minterms otherwise. Thus,
realized as the
OR
of
s
minterms in
a
for 1
≤
i
≤
p
−
2
k
two-input
OR
's suffice for all values of
i
and a fixed value of
v
.
Hence, for each value of
v
the functions
f
(
r
)
1
)+(
s
−
(
p
−
1
)(
s
−
1
)
≤
can be realized by a circuit of size
O
(
2
k
)
.Since
i
,
v
there are at most 2
s
choices for
v
,all
f
(
r
)
can be realized by a circuit of size
O
(
2
k
+
s
)
.
i
,
v
Consider next the functions
f
(
c
)
i
,
v
(
b
)
. We construct a decoder circuit for the minterms of
b
thathassizeatmost2
n−k
+(
n
2
)
2
(
n−k
)
/
2
.Sinceforeach
i
,1
−
k
−
≤
i
≤
p
,thesets
Search WWH ::
Custom Search