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