Information Technology Reference
In-Depth Information
that no single primitive has of the coverage of the needed pattern. Therefore, another
level of majority gates is added and three more primitives are then selected to satisfy
the required coverage of pattern. Following the same rule, all the qualified primitives
can be found and the result is f ¼ MMa ; c 0 ; d
Þ ; a 0 ; MMa ; b 0 ; c
Þ ; Mc 0 ; d 0 ; 0
ð
Mb ; d ; ð ÞÞÞ . The resulting implementation is illustrated in Fig. 10 . There may be
more than one solution for any given problem. Most of four variable problems can be
solved within three levels and all of them can be solved in four levels.
ð
ð
ð
ð
Þ ;
3.3
Four-Dimensional Cubes and Four-Variable K-maps
A four-variable Boolean function can be represented by a four dimensional (4-D) cube
[ 20 , 21 ], as shown in Fig. 11 , with each literal in this function ''a'' , '' b'' , '' c'' , a n d '' d''
being one of the four dimensions of a 4-D cube. The sixteen different minterms in the
Boolean logic function represent sixteen vertices in a 4-D cube, which is similar to
the sixteen cells in a four-variable K-map. For example, the minterm ''abc 0 d'' can be
represented by vertex (1, 1, 0, 1) and also as an on-set square in K-map. For a four-
variable function, the set of all the on-set vertices in a 4-D cube, which represent
minterms, can be considered a specific spatial structure which can be rotated, flipped,
or mirrored to represent many other four-variable functions. Thus, one structure could
describe many different functions.
As an example, consider two logic functions f ¼ a 0 c 0 þ a 0 b 0 d 0 and f ¼ b 0 d þ acd.
After mapping these two logic functions to a 4-D cube and corresponding K-map, as
shown in Fig. 12 (a) and (b), it can be seen that the spatial structures formed by their
Fig. 11.
A 4-D cube
(a) (b)
Fig. 12. (a) 4-D cube and K-map interpretation of f ¼ b 0 d þ acd (b) 4-D cube and K-map
interpretation of f ¼ a 0 c 0 þ a 0 b 0 d 0
Search WWH ::




Custom Search