IMPLEMANTATION OF
BOOLEAN FUNCTION
F = A’BC’ + A’BC
+ ABC’[Sum Of Product (SOP)]
A
|
B
|
C
|
F
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
0
|
Table 1
Boolean function of three
variables
SOP Implementation of Table 1
The SOP
form expresses that
the output is
1 if any of the
input combinations that
produce 1 is
true. The output
is 1 if
none of the
input combinations that
produce 0 is
true.
F = (A’B’C’)’ •
(A’B’C)’ • (AB’C)’ • (A’B’C’)
By using
generalization of DeMorgan’s
Theorem,
(
X • Y • Z )’ = X’ + Y’ + Z’
F = ( A’’ + B’’ + C’’ ) • ( A’’ + B’’ + C’ ) • (
A’ + B’’ + C’’ ) • ( A’ + B’’ +C’ ) • ( A’ + B’ + C’ )
= ( A + B + C )
• ( A + B + C’) • ( A’ + B + C ) • ( A’ + B + C’ ) • ( A’ + B’ +C’ )
[Product Of
Sum(POS)]
POS Implementation of
Table 1
For clarity,
NOT gates are not shown.
Rather, it is assumed that each
input signal and
its complement are
available. This simplified
the logic diagram
and makes the inputs
to the gated are more
readily apparent.
Boolean function
can be realized
in either SOP or
POS form. At this
point, it would
depend on whether
the truth table
contains more 1s
or 0s for the
output functions. SOP
has one term
for each 1, and
the POS
has one term
for each 0.
However, there are
other considerations:
→ It is
generally possible to
derive a simpler
Boolean expression from
the truth table
than either SOP
or POS.
→ It may
preferable to implement
the function with
a single gate
type (NAND or NOR).
NgSweeYan
The
significant of the
first point is
that, with a
simpler Boolean expression,
fewer gates will be
needed to implement
the function. Two
methods can be
used to achive
simplification.
I. - Algebraic
Simplification
II. - Karnaugh Maps
I.
Algebraic
Simplification
This
involve the application
of identities to reduce Boolean
expression to one with
fewer elements.
Identities of
Boolean Algebra
Basic Postulates
|
||
A
• B = B • A
|
A
+ B = B + A
|
Commutative law
|
A
• ( B + C ) = ( A • B ) + ( A • C )
|
A
+ ( B • C ) = ( A + B ) • ( A + C )
|
Distributive law
|
1
• A = A
|
0
+ A = A
|
Identity elements
|
A
• A’ =0
|
A
+ A’ = 1
|
Inverse elements
|
Other identities
|
||
0
• A = A
|
1
+ A = 1
|
|
A
• A = A
|
A
+ A = A
|
|
A
• ( B • C ) = ( A • B ) • C
|
A
+ ( B + C ) = ( A + B ) + C
|
Associative law
|
(
A • B )’ = A’ + B’
|
(
A + B )’ = A’ • B’
|
DeMorgan’s Theorem
|
Simplified
Implementation of Table 1
Boolean function of three
variables
I.
Karnaugh Maps
A convenient
way of representing
a Boolean function
of a small number (up
to four to
six) of variables.
The maps is an array
of 2n squares,
representing the possible
combinations of values
of n binary
variables. It is
convenient for later
purposes to list
the combinations in the order
00, 01, 11,
10. Because the
squares corresponding to
the combination are
used to be
recording information, the
combinations are customarily
written above the
squares. For three
variables, the representation is
an arrangement of
eight squares. For
four variables, sixteen
squares are needed.
Each square corresponds
to a unique
product in the
SOP form, with
a 1 value
corresponding to the
NOT of that variable. Given
the truth table
of a Boolean
function, it is
an easy matter
to construct the
map. For each
combination of values
of variables that
produce a result
of 1 in
the truth table,
fill in the
corresponding square of
the map with 1.
Once the
map of a
function is created,
we can often
write a simple
algebraic expression for
it by noting
the arrangement of
the 1s on
the maps. The
principle is as
follows : Any two
squares that are
adjacent differ in
only one of
the variables. If
two adjacent squares
but have entry
of one, then
the corresponding product
terms differ in
only one variable.
Example: In
figure2. The use of
Karnaugh map (a),the
two adjacent squares
correspond to the
two terms A’BC’D and A’BCD. Thus,
the function expressed
is:
A’BC’D + A’BCD
= A’BD
Rules Of
Simplification:
a)
Among the
marked squares (Squares
with a 1), find
those that belong
to a unique
largest block of
ether 1, 2, 4, or
8 and circles
those blocks.
b)
Select additional
blocks of marked
squares that are
as large as
possible and as
few in number
as possible, but
include every marked
square at least
once. The results
may not be
unique in some
cases. For example,
if a marked
square combines with
exactly two others
squares, and there
is no fourth
marked square to complete a
larger group, then
there is a
choice to be
made as two groupings to
choose. When you
are circling groups,
you are allowed
to use the
same 1 more
than once.
c)
Continue to
draw loops around
single marked squares,
or pairs of
adjacent marked squares,
or groups of
four, eight, etc.
in such a
way that every
marked square belongs
to at least
one loop; then
use as few
of these blocks
as possible to include
all marked squares.
Written by,
Ng Swee Yan A/P Suresh Kumar
B031210103
No comments:
Post a Comment