Alright
ladies and gents, today we’ll be learning about the Karnaugh Map otherwise
known as the K-Map. The K-Map is an alternative method for simplifying a
Boolean expression. It is suitable for inputs of 2 to 4 variables. This method
is much simpler compared to using the Boolean algebra. There are 4 steps
involved when making a karnaugh map which are:
1. By referring to the truth table, fill in all of the 1’s
from the minterms in the truth table.
2. Group the 1’s following a simple set of rules. (We’ll get
more in depth about those rules later).
3. List the groups, analyze it and simptuylify.
4. The simplified expressions are add together (*ORed). * Read as OR in
past-tense form.
Let’s do some examples to help you get a clearer picture on
what I’m rambling on about.
Example 1:
Let’s say we are given 2 variables. Find the simplified
Boolean expression.
Step 1: Make a truth table and a K-Map.
A
|
B
|
F
|
Minterms
|
0
|
0
|
0
|
A’B’
|
0
|
1
|
1
|
A’B
|
1
|
0
|
1
|
AB’
|
1
|
1
|
1
|
AB
|
B
A
|
B’
(0)
|
B
(1)
|
A’
(0)
|
O
|
1
|
A
(1)
|
1
|
1
|
* In the Karnaugh Map, each cells is filled with
values that corresponds with the “F” column.
Step 2: Group the 1’s in the K-Map using a set of rules
stated below.
- Each groups can consists of only 1’s.
- Only adjacent cells are allowed to be grouped.
- The group must be as large as possible meaning that it can have 2, 4, 8 or 16 of 1’s in it.
- The least number of grouhgvps formed the better.
- All 1’s must belong to a group even if it’s a group of one.
- Wrap around is allowed.
- Overlapping groups are allowed.
B
A
|
B’
|
B
|
A’
|
o
|
1
|
A
|
1
|
1
|
- The first group is B as variable B is the only
variable that remains constant
B
A
|
B’
|
B
|
A’
|
o
|
1
|
A
|
1
|
1
|
- The second group is A
since A is the only variable that
remains constant.
Step 3: Skipping this step as we havjnkle already found the
simplest Boolean expression.
Step 4: Add together
the groups.
Answer
= B + A or A
+ B
Example 2: Given 3 variables. Find the simplified Boolean
expression.
Step 1: Build a truth
table and a K-Map.
A
|
B
|
C
|
F
|
Minterms
|
0
|
0
|
0
|
1
|
A’B’C’
|
0
|
0
|
1
|
1
|
A’B’C
|
0
|
1
|
0
|
1
|
A’BC’
|
0
|
1
|
1
|
1
|
A’BC
|
1
|
0
|
0
|
0
|
AB’C’
|
1
|
0
|
1
|
0
|
AB’C
|
1
|
1
|
0
|
1
|
ABC’
|
1
|
1
|
1
|
1
|
ABC
|
BC
A
|
B’C’
|
B’C
|
BC
|
BC’
|
A’
|
1
|
1
|
1
|
1
|
A
|
0
|
0
|
1
|
1
|
Step 2: Group the 1’s.
BC
A
|
B’C’
|
B’C
|
BC
|
BC’
|
A’
|
1
|
1
|
1
|
1
|
A
|
0
|
0
|
1
|
1
|
-
A’B’C’ - A’B’C
-
A’BC -A’BC’
BC
A
|
B’C’
|
B’C
|
BC
|
BC’
|
A’
|
1
|
1
|
1
|
1
|
A
|
0
|
0
|
1
|
1
|
-
A’BC - A’BC’
-
ABC - ABC’
Step 3: Analyze.
For same letters in a column they will be brought down. For
different letters in a column they will cancel each other out.
Group 1:
Group 2:
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
Step 4: Add the groups together.
Answer
= A’ + B or B
+ A’
Below are some links that i found to be very helpful when learning about K-Maps:
2 comments:
Great Tutorial easy to follow. Just one question, when you have done stage 3 'analyse' how to you know whether they are AND/OR gates etc?
Post a Comment