Transcript minimal sum

Lecture 5
Karnaugh Maps
One of the easiest ways to simplify a Boolean expression is through
the use of a Karnaugh map. Let us recall the OR gate (again!)
A
0
0
1
1
B
0
1
0
1
Y
0
1
1
1
The Boolean minterm is A B + A B + A B
The general form of a 2 input Karnaugh map is below. Note that
each square differs from its neighbouring square by changing only 1
of the numbers- this is more important for 3 and greater Karnaugh
maps
B
A
A
B
00
01
10
11
A logic function with n
variables will require 2n
squares
68
To produce a simplified Boolean expression using a K-map
(1)
produce the Boolean minterm
(2) plot the 1s for the ANDed variables in the appropriate square
(3) loop adjacent (horizontal or vertical groups of 8, 4, or 2 1s
together
(4) eliminate variable/complements pairs
(5) OR the remaining variables
Lets use the OR function as an example.
1. The Boolean minterm is
2
B
AB+AB+AB
B
A
A
69
3. Loop adjacent 1s
B
A
A
1
B
1
1
Loop 1
Loop 2
4. Eliminate variable/complements pairs
From loop 1: A B and A B, since A and A are variable and complement
they are eliminated. This leaves only B.
From loop 2, A B and A B, since B and B are variable and complement
they are eliminated. This leaves only A.
5. OR the remaining variables Y = A + B
70
Note
1. You may only loop horizontally or vertically. This is
because you are changing just one variable at a time.
You cannot loop diagonally.
2. Start with the highest number of squares 8, then 4
then 2.
3. If you have a group of 4, it is the same as looping 4
groups of 2. (Can you see where the 4 doublets are?)
4. You can loop the same 1 more than once – in fact you
can do this often.
71
Consider the case of a 3 input K map. In this case we have A, B and C
which are grouped into the 4 possible AB combinations x 2 possible C
combinations. Therefore the K map will have 8 squares
A B
AB
AB
AB
C
C
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
Y
0
1
1
1
0
1
0
1
Consider the truth table.
Step 1. Minterm
Y=
72
Step 2. Mark 1s in the appropriate squares
A B
AB
AB
AB
C
C
Step 3. Loop 8, 4 or 2, adjacent 1s.
Step 4. Eliminate variable/complements pairs
Step 5. OR remaining variables
73
Check 1:
Do we always get a 1 when C = 1
Do we always get a 1 when A B = 1
74
Check 2:
Can we simplify the original minterm expression to get the
same answer.
Y =ABC +ABC+ABC+ABC+ABC
75
As the number of variables increases K maps become very useful.
Consider the case of a 4 variable input (A,B,C and D). There are 4
possible AB combinations x 4 possible CD combinations so the K map
will have 16 squares. Fill in the possible arrangements
CD
AB
Pick any square and
going vertically or
horizontally we only
change one variable at
a time.
76
A B
AB
AB
AB
CD
CD
CD
CD
Note the pattern 0 0  0 1  1 1  1 0
We are changing one bit at a time. This single variable change is called
adjacency.
The bit in the sequence is 0 0 - which is the same as the first bit.
This is important when considering special looping arrangements
77
Exercise 5.1 Use this 4 input truth table.
A
B
C
D
Y
A
B
C
D
Y
0
0
0
0
0
1
0
0
0
0
0
0
0
1
1
1
0
0
1
1
0
0
1
0
0
1
0
1
0
0
0
0
1
1
1
1
0
1
1
1
0
1
0
0
0
1
1
0
0
0
0
1
0
1
1
1
1
0
1
1
0
1
1
0
1
1
1
1
0
0
0
1
1
1
1
1
1
1
1
1
Step 1. Write out the unsimplified Boolean minterm
78
Step 2. Mark 1s in the appropriate squares
Step 3. Loop 8, 4 or 2 adjacent 1s.
Step 4. Eliminate variable/complements pairs
Step 5. OR remaining variables
79
Check:
Do you get a ‘1’ when D = 1 or when A B C = 1
80
Lecture 6
K maps can have some unusual looping arrangements.
You should prove to yourself that the K map for the expression
Y = A B C D + A B C D + A B C D + A B C D + A B C D is
given below
A B
C D
1
AB
AB
AB
1
C D
C D
C D
1
1
1
81
A B
C D
1
AB
AB
AB
Loop 1
1
C D
B and B - eliminate
C D
C D
1
1
A, C, D - keep
1
Loop 2
B and B - eliminate
A, C, D - keep
Is loop 3 permitted????
NO
82
Why can we not loop on a diagonal or a group of 3??
83
So the original expression can be simplified to
Y=A C D +A C D +ABCD
But we can combine the first 2 terms here to give
Y=A C D +A C D +ABCD
= A (C + C ) D + A B C D
= AD +ABCD
Is this the case could we not have done this using the K-map.
Answer – we can if we look for ‘unusual’ looping arrangements.
84
A B
C D
1
AB
AB
AB
1
C D
C D
C D
1
1
This grouping is
equivalent to
1
A B
1
C D
1
C D
AB
1
1
Eliminate B and B
also C and C which
just leaves
A and D
85
Other interesting looping arrangements are
A B
C
AB
1
AB
1
C
No change
1
A B
AB
C
C
AB
AB
AB
1
1
1
Eliminate A and A
gives B and C
Y=ABC +BC
86
A B
C D
AB
AB
AB
1
1
1
1
C D
C D
C D
Y=BD
87
You should prove that looping (i) vertically and (ii) horizontally
gives the same result.
A B
C D
AB
AB
AB
1
1
1
1
C D
C D
C D
88
We can come to some conclusions about the structure of K maps. For
a 3 variable K map
1. a 1 cell group yields a 3 variable product term
2. a 2 cell group yields a 2 variable product term
3. a 4 cell group yields a 1 variable product term
4. a 8 cell group yields a value of 1 for the expression
Example. What logic expression do we get from these K maps?
A B
AB
C
1
1
C
1
1
A B
C
C
1
AB
1
AB
AB
AB
AB
1
1
89
This allows us to regard different parts of the K map to be
associated with different variables.
A
A B
A
AB
AB
AB
C
C
B
B
B
90
For a 4 variable K map
1.
2.
3.
4.
5.
a 1 cell group yields a 4 variable product term
a 2 cell group yields a 3 variable product term
a 4 cell group yields a 2 variable product term
a 8 cell group yields a 1 variable product term
a 16 cell group yields a value of 1 for the expression
A B
AB
AB
AB
C D
C D
C D
C D
91
Similar to a 3 variable to a map we can regard different parts of the K
map to be associated with different variables.
A B
AB
AB
AB
C D
C D
C D
C D
92
Some formal definitions
A literal is a variable either complemented or not complemented.
Example A, B and D
Normal product term is a product of terms in which no variable
appears more than once. Example AB or ACD. An example of a nonnormal product term would be ACC
93
1.
An implicant is a normal product term that implies Y = 1. For
example if Y= AB + BC, the implicants are AB and BC.
2. A prime implicant (PI) is one that is not a subset of another
implicant.
In a K map a PI is the largest possible grouping allowed.
E.g a group of 4 will be a PI whereas the two groups of 2
will only be implicants.
3. A distinguished 1-cell is a cell that is covered by only one PI.
In a K-map, such cells are 1s that are circled once.
4. An essential prime implicant is a PI if it includes a 1 that is not
included in any other prime implicant.
For a K map the EPIs must include the PIs associated with
a distinguished 1 cells.
94
5. A minimal sum is a SOP expression such that no SOP expression
of Y has fewer product terms.
It will include the EPIs but MUST also include whatever
number of other terms to make sure that all the 1s have been
covered.
95
The best way to examine these terms is by means of an example.
Using the information in the K-map to determine
(i) the number and list of PIs,
(ii) The distinguished 1-cells,
(iii) the EPIs and
(iv) the minimal sum.
A B
AB
AB
AB
1
1
C D
C D
C D
C D
1
1
1
1
96
So we can write Y as
Y=
This SOP expression contains 5 terms – these are the 5 implicants.
What we want to see is if it is possible to write out another
expression for Y but which has fewer terms.
97
(i) the PIs,
(ii) The distinguished 1-cells,
(iii) the EPIs and
(iv) the minimal sum.
98
Recall that
Y=
Now Ymin = A C D + A C D + other terms????
The key point was the distinguished 1-cells are also EPI and the EPI
will form part of the minimal sum.
We must check whether using the EPIs alone is sufficient so that all
the 1s are covered.
Answer – NO we must add an extra term/s – but which one??
Add BCD to the EPIs to give the minimal sum
99
Exercise 6.1. Here is a slight variation from the previous example.
Using the information in the K-map to determine
(i) the number and list of PIs,
(ii) The distinguished 1-cells,
(iii) the EPIs and
(iv) the minimal sum.
A B
AB
AB
C D
1
C D
1
C D
C D
AB
1
1
1
1
1
100
(i) the PIs,
(ii) The distinguished 1-cells,
(iii) the EPIs and
(iv) the minimal sum.
101
1
1
1
1
1
1
1
They are the PIs associated with a
distinguished 1 cell.
So the minimal sum will include
these two terms.
1
1
1
1
1
1
1
In each of the 3 maps the location
of the EPI have been circled
How do we know that theses are
EPIs?
1
1
1
1
1
1
1
How many ways is it possible to
group together the other 1s
present using as small a number of
groups as possible??
102
So the minimal sum will include these two terms.
Do these two terms cover all the 1s present?
If YES then the the minimal sum is just the EPIs
If NO then we need to add the minimal number of extra
terms
How many ways is it possible to group together the other 1s
present using as small a number ofgroups as possible??
103
The previous example showed that that there are 3 ways
to ensure that all the 1s are covered so there are three
possible ways to write out the the minimal sum
Ymin = A B C + A C D +
Ymin = A B C + A C D +
Ymin = A B C + A C D +
Each of these uses 4 terms. The original expression used 6.
This means that there exist expressions with 5 PI but they do
not form a minimal sum.
104
Exercise 6.2 Using the information in the K-map to determine
(i) the number and lists of PIs,
(ii) The distinguished 1-cells,
(iii) the EPIs and
(iv) the minimal sum.
A B
AB
C D
1
1
C D
1
1
C D
1
1
C D
1
AB
AB
1
1
105
(i) the PIs,
(ii) The distinguished 1-cells,
(iii) the EPIs and
(iv) the minimal sum.
106
We can write the minterm as Y = A B C + A B C
Lecture 7
Since it consist of terms from rows 4 and 7 it can also
be written as S A,B,C (4,7)= S (4,7).
This is known as the canonical sum of the logic function
and the elements within the sum make up the minterm
list and mans ‘the sum of the minterms 4 and 7 with
variables A,B and C’.
Remember this is the ‘sum-of-products’.
In the case of 3 input K map the cell numbers are
0
2
6
4
1
3
7
5
107
What are the cell numbers associated with the 4 variable K map.
A B
AB
AB
AB
C D
C D
C D
C D
108
0000
0100
1100
1000
0001
0101
1101
1001
0011
0111
1111
1011
0010
0110
1110
1010
0
4
12
8
1
5
13
9
3
7
15
11
2
6
14
10
109
Exercise 7.1. Look at the K map below. Write
out an canonical sum for Y?
A B
AB
AB
AB
1
1
C D
C D
C D
C D
1
1
1
1
110
Exercise 7.2
This system has four inputs and one outputs. The first
two inputs A and B represent a 2-bit binary number in the
range of 0 to 3. A second binary number (in the same
range) is represented by the other two outputs, C and D.
The output F is to be 1 if and only if the second number is
larger than the first number.
1. Show a truth table for F and write down the unsimplifed
Boolean expression.
2. Show F on a Karnaugh map and find a simplified expression
for F.
111
112
D
8s
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
C
4s
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
B
2s
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
A
1s
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
Decimal
0
1
2
3
4
5
6
7
8
9
10 Not used
11 Not used
12 Not used
13 Not used
14 Not used
15 Not used
The final aspect of K maps
is the ‘don’t care’ condition.
To produce a decimal signal
for the numbers 0-9 we
need to know the binary
equivalents.
113
From the truth table binary numbers 0000 to 1001 represent 0 to 9.
(This is a 4 bit weighted code and is correctly known as the 8421 BCD
code – binary coded decimal).
The truth table shows that possible values such as 1010 etc are
possible but these would not lie in the range 0-9.
These six combinations are called ‘Don’t cares’ when plotted on a
Karnaugh map using an X
We may allow the Xs to be 1 or 0 depending on our needs.
In the example above, suppose to prevent using these 6 additional
number we wish to stop when the BCD count reaches 9. The Boolean
expression for this is
D C B A (remember that A B = B A).
114
The 6 don’t cares are marked with an X which could me that they
could be 0 or 1.
A B
AB
AB
AB
C D
X
C D
X
1
C D
X
X
C D
X
X
We can then loop around, 8, 4 or 2 adjacent 1s and since the Xs
could be 1s we loop around them and then proceed as normally.
So the simplified expression is Y = D A
115
An interesting question. Why do we not loop like this as well.
A B
AB
AB
AB
C D
X
C D
X
1
C D
X
X
C D
X
X
Answer. Firstly it does not cover a 1 and secondly it would add an
extra term AB
116
Exercise 7.3: Simplify the logic function given by
f= S (1, 3, 7, 8, 9, 10, 12, 13, 14, 15)
How would your answer change if the function to be minimised had
don’t care conditions D = (4, 5, 11).
117
118