Karnaugh Maps – Introduction

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