Karnaugh Maps I Video Lecture | Analog and Digital Electronics - Electrical Engineering (EE)

this video is an introduction to Carnot
maps it assumes that you're already
familiar with logic gates like and or
and not and how these gates can be
combined to produce more complex
circuits you should know about truth
tables and how these can be used to
describe the behavior of logic circuits
in terms of inputs and outputs it's also
assumed that you're familiar with some
boolean algebra specifically how various
rules can be used to simplify boolean
expressions and therefore the role of
boolean algebra in circuit design so
what is a karnaugh map or a k-map as
they sometimes known it's a special form
of truth table which enables easier
pattern recognition than a truth table
dos it's a pictorial method of
simplifying boolean expressions good for
circuit designs with up to four
variables that's four inputs so let's
look at an example here's a simple truth
table with two inputs or shall we say
two variables you should recognize this
as the truth table of an or gate column
F contains the output value for each
combination of input values a and B
strictly speaking this is the truth
table for any combination of logic gates
that behave in the same way as an or
gate so we could say that this is the
truth table of an or function that's why
we've called the output column F to
construct the corresponding K map we
draw a grid with one square for each row
in the truth table the possible input
values for a are used as column headings
across the top and those for B as row
labels down the left-hand side these
input values will act like coordinates
for the output values now we can
populate the K map we can see from the
truth table that when a is 0 and B is 0
the output is 0 when
a 0 and B is 1 the output is 1 when a is
1 and B is 0 the output is 1 and when a
is 1 and B is 1 the output is 1 our K
map is ready for use
we'll see this particular one again
later now let's talk about how a K map
can be used to derive the simplest
possible boolean expression
here's another different truth table
again with two variables a and B but the
outputs in column F are different this
time the corresponding K map looks like
this to derive the simplest boolean
expression from the K map we're looking
for the largest possible grouping of
ones an expression can then be derived
by inspecting this group here we can see
that whenever there is a 1 in the group
the value of input a is 1 we can also
see that the topmost one in the group
corresponds to a value of 0 for input B
but the other one in the group
corresponds to a value of 1 for input B
this means that the output is
independent of the input value B which
makes big a redundant input this
grouping can therefore be expressed
simply as a the output of this function
is a here's another example with two
inputs we've seen this one before it's
the truth table for an or gate but let's
see how we can derive the boolean
expression by inspecting the K map
here's the corresponding K map a single
group cannot be l-shaped so what we have
here are two overlapping groups of ones
the ones in the vertical group always
match the input value a the vertical
grouping can therefore be expressed
simply as a the ones in the horizontal
group always match the
value B so the horizontal grouping can
be expressed as B hence this K map
represents the expression A or B it is
indeed the or function in this truth
table the output is always 1 regardless
of the inputs here's the K map which
matches this truth table we can create
one large group of ones here clearly the
output is independent of all of the
inputs it is always 1 so the boolean
expression for this circuit is simply 1
let's consider one more example with two
variables here's the K map which matches
this truth table we have two groups here
the ones in the vertical group are
always the opposite of input a so they
are related to it this group represents
not a the ones in the horizontal group
are always the opposite of input B so
this group represents not B hence this
particular K map represents the function
not a or not B you may have already
recognized that this is the truth table
of a NAND gate now let's look at some
karnaugh maps for functions which have
three variables this truth table has
three inputs or to put it another way
three variables to construct a three
variable karnaugh map we could start by
placing possible input values for one of
them in this example a in the column
headings like this now we can have one
row for each combination of values for
the inputs B and C starting with B
equals 0 and C equals 0 then B equals 0
and C equals 1 now B equals 1 and C
equals 1 and finally B equals 1 and
C equals zero we now have all of the
possible combinations of inputs B and C
included you can see that as you scan
down the row labels each pair of input
values for B and C differs from the next
or the previous pair by only one bit
these are not sequential binary numbers
this is quite deliberate indeed it's an
essential aspect of the construction of
a k-map with three or more variables
okay now we can transfer data from the
truth table to the k-map by using the
input values as coordinates for the
placement of output values the K map is
now fully populated and ready for use
when we look for the largest possible
groups of ones we can see two
overlapping groups here there are some
rules we must obey when it comes to
grouping one of these is that a group
must be a horizontal or a vertical
rectangle or a square more about these
rules later suffice to say for now we've
obeyed them upon inspection we can see
that the tall vertical block of ones
always matches the input value of a so
this expression includes a and if you
look carefully you can see that the
other block of one's always matches the
input value B hence this K map
represents the expression A or B we
could have constructed a different
looking K map from the same truth table
both of these K maps contain exactly the
same information but one of them is
turned through 90 degrees
we've also combined the input values
differently in the alternative version
this time the input values for a and B
are paired up and are now acting as row
headings again you can see that as you
scan across these row headings each pair
of input values differs from the next or
the previous pair by only one bit
looking for the largest possible group
of ones the uninitiated might decide
that this is a candidate but this breaks
one of the rules a group cannot contain
six ones it can only contain one two
four or eight ones or to put it more
generally two to the power n ones but we
can have two overlapping groups of four
this is correct upon inspection the ones
in the group on the left always match
the input value P and the ones in the
group on the right always match the
input value a so we arrive at B or a the
horizontally arranged version of the
same k-map that we saw before has given
us essentially the same result from the
vertically arranged version we arrived
at the expression A or B and in case you
were wondering if we had created two
groups like this we would still arrive
at the same conclusion that this K map
represents the expression B or a and two
groups like this would yield the same
result but it's always best to create
groups as large as possible here's a
different example let's see what we can
make of it we have two groups of ones
that obey the rules we've looked at so
far the ones in the long horizontal
group are always the opposite of C that
is they are not C and the ones in the
square block always match the value of
input a hence we have the expression not
C or a this example illustrates
something we haven't seen yet we have a
small group of ones here we can see that
these ones correspond to an input value
of 1 for a and they also correspond to
an input value of 1 for B so this K map
represents the function a and B
notice that when we're describing a
single group of one's that's dependent
on different input values we use the and
operator to describe the relationship
between the inputs on the other hand
we've already seen that we use the all
operator to describe the relationship
between different inputs in different
groups of ones this example illustrates
a new rule for grouping ones together we
have a single group of four ones that
wraps around the table
imagine the table is being rolled up
into a tube so that the top and bottom
rows are now adjacent to each other this
type of group is allowed we can see that
whether a one's sometimes they is 0 and
sometimes it's one so the output of the
circuit that this K map represents is
independent of a also whether a one's
sometimes be a zero and sometimes it's
one so the output of the circuit that
this K map represents is also
independent of being but whether a one's
the value of C is always zero the
opposite of the output so this K map
represents the function not C here's
another example here we have another
group of ones that wrap around the table
where there are ones a is always one and
where there are ones the value of C is
always zero but the output is
independent of B remember because of the
table wrapping rule there is only one
group of ones here so this K map
represents a and not C to finish then
here's a summary of the rules for
identifying groups in a k-map a group
must only contain ones no zeros a group
can only be horizontal or vertical not
diagonal a group must contain two to the
power n
one's for example one two four eight
each group should be as large as
possible groups can overlap and groups
can wrap around the table everyone must
be in at least one group and finally
there should be as few groups as
possible