Transcript Transistors, Logic Gates and Karnaugh Maps

Karnaugh Maps
References:
Chapters 4 and 5 in Digital Principles (Tokheim)
Chapter 3 in Introduction to Digital Systems (Palmer
and Perlman)
1
Expressing truth tables



Every truth table can be expressed in terms
of the basic Boolean operators AND, OR and
NOT operators.
The circuits corresponding to those truth
tables can be build using AND, OR and NOT
gates, which can be made out of transistors.
The input in each line of a truth table can be
expressed in terms of AND’s and NOT’s
2
Line by Line
Inputs
A
Expression
B
0
0
(Not A) AND
(NOT B)
0
1
(Not A) AND B
1
0
A AND (NOT
B)
1
1
A AND B
A´B´
A´B´ is true for the first line
and false for the rest
A´B
A´B is true for the second line
and false for the rest
AB´
AB´ is true for the third line
and false for the rest
AB
A´B´ is true for the fourth line
and false for the rest
This is not yet a truth table. It has no outputs.
3
It’s true; it’s true



To express a truth table, take the input
lines that correspond to true (high, 1)
outputs.
Write the expressions for each of those
input lines (as shown on the previous
slide).
Then feed all of those expressions into
an OR gate.
4
Example 1
A
0
0
B
0
0
C
0
1
Out
1
0
0
0
1
1
1
1
0
0
0
1
0
1
1
0
0
1
1
1
1
1
0
1
0
1
5
Example 1 (Cont.)


A’B’C’ + A’BC’ + AB’C + ABC
The expression one arrives at in this
way is known as the sum of products.


You take the product (the AND operation)
first to represent a given line.
Then you sum (the OR operation) together
those expressions.
6
Example 2
A
0
0
B
0
0
C
0
1
Out
0
1
0
0
1
1
1
1
0
0
0
1
0
1
1
1
1
1
1
1
1
1
0
1
1
1
7
Example 2 (Cont.)



A’B’C + A’BC’ + A’BC + AB’C’ + AB’C +
ABC’ + ABC
But isn’t that just the truth table for
A+B+C ?
There is another way to write the
expression for truth tables.
8
Example 2 (Cont.)
A
0
0
B
0
0
C
0
1
Out
0
1
0
0
1
1
1
1
0
0
0
1
0
1
1
1
1
1
1
1
1
1
0
1
1
1
In this
approach,
one looks at
the 0’s
instead of the
1’s.
9
Example 2 (Cont.)



One writes expressions for the lines
which are 1 everywhere except the line.
Then one ANDs those expressions
together.
The expression obtained this way is
known as the product of sums.
10
Expressions
A
0
0
0
B
0
0
1
C
0
1
0
Expression
A+B+C
A + B + C’
A + B’ + C
0
1
1
1
0
0
1
0
1
A + B’ + C’
A’ + B + C
A’ + B + C’
1
1
1
1
0
1
A’ + B’ + C
A’ + B’ + C’
11
Return to Example 1
A
0
0
B
0
0
C
0
1
Out
1
0
0
0
1
1
1
1
0
0
0
1
0
1
1
0
0
1
1
1
1
1
0
1
0
1
12
Return to Example 1 (Cont.)

The product of sums expression is
(A+B+C’)(A+B’+C’)(A’+B+C)(A’+B’+C)
13
Algebra  Gate

A’ means NOT A
high
Red probe
indicator
high
input
low
low
output
14
Algebra  Gates

AB means A AND B
15
Algebra  Gates

A+B means A OR B
16
Simplifying Boolean algebra
expressions



Recall that (A’B’C + A’BC’ + A’BC + AB’C’ +
AB’C + ABC’ + ABC) and (A+B+C)
correspond to the same truth table.
Before building a circuit that realizes a
Boolean expression, we would like to simplify
that expression as much as possible.
Fewer gates means




Fewer transistors
Less space required
Less power required
More money made
17
A few fundamental theorems




A+1=1
A+0=A
A·1 = A
A·0= 0




A+A=A
A·A = A
A + A’ = 1
A·A’ = 0
18
A Trivial Example
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
Out
0
0
1
1
0
0
1
1
A’BC’
A’BC
ABC’
ABC
19
Simplifying a trivial example





A´BC´ + A´BC + ABC´ + ABC
A´B (C´ + C) + AB (C´ + C)
A´B + AB
(A´ + A) B
B
C+C’ means C OR (NOT C)
In other words, we don’t care about C
20
Majority Rules Example
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
Majority
0
0
0
1
0
1
1
1
21
Row Expressions
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
Row expressions
A’B’C’
A’B’C
A’BC’
A’BC
AB’C’
AB’C
ABC’
ABC
22
Majority rules (sum of products)
without simplification

A´BC + AB´C + ABC´ + ABC
NOTs
OR
ANDs
23
Majority Rules Simplification





A´BC + AB´C + ABC´ + ABC
A´BC+AB´C+ABC´+ABC+ABC+ABC
A´BC+ABC+AB´C+ABC+ABC´+ABC
(A´+A)BC+A(B´+B)C+AB(C´+C)
BC+AC+AB
24
Majority rules without
simplification
25
Majority Rules Comparison
26
Simplifying made easy



Simplifying Boolean expressions is not
always easy.
So we introduce next a method (a
Karnaugh or K map) that is supposed
to make simplification more visual.
The first step is to rearrange the inputs
in what is called “gray code” order.
27
Frank Gray in Wikipedia
PHY 201 (Blum)
28
PHY 201 (Blum)
29
Gray code



In addition to binary numbers, there is
another way of representing numbers
using 1’s and 0’s.
It is not useful for doing arithmetic, but
has other purposes.
In gray code the numbers are ordered
such that consecutive numbers differ by
one bit only.
30
Gray code (Cont.)
0
0
0
0
1
1
1
1
0
0
1
1
1
1
0
0
0
1
1
0
0
1
1
0
Each
row
different
by one
bit only
31
Constructing Gray code
0
1
32
Reflect lower bits and 0’s then
1’s in front
Lower bits
Add 0’s
Add 1’s
0
0
1
1
0
1
1
0
Reflect
lower bits
through
red line
33
Reflect lower bits and 0’s then
1’s in front (again)
Add
0’s
Add
1’s
0
0
0
0
1
1
1
1
0
0
1
1
1
1
0
0
0
1
1
0
0
1
1
0
Reflect
lower
bits
through
red line
34
An important property


In gray-code order, two consecutive
rows of a truth table differ by one bit
only.
Thus if a truth table is put in gray code
order and if two consecutive rows
contain a 1, then a simplification of the
Boolean expression is possible.

A term like X + X’ can be factored out.
35
Trivial Example in Gray code
A
0
0
0
0
1
1
1
1
B
0
0
1
1
1
1
0
0
C
0
1
1
0
0
1
1
0
Out
0
0
1
1
1
1
0
0
36
Improving



Some combinations that differ only by a
single bit are not in consecutive rows.
Thus we might miss such a
simplification.
So we put some of the inputs in as
columns.
37
Two rows that differ by one
bit but are not consecutive
A
0
0
0
0
1
1
1
1
B
0
0
1
1
1
1
0
0
C
0
1
1
0
0
1
1
0
Out
0
0
1
1
1
1
0
0
38
A row-column version
Place the C inputs across the top.
All inputs are filled in with light blue.
A
0
B\C
0
0
0
1
0
0
1
1
1
1
1
1
1
1
0
0
0
In this
version,
more inputs
differing by
one bit only
are in
adjacent
positions.
39
Karnaugh-map

This way of arranging truth tables
combined with the rules for simplifying
Boolean expressions goes by the name
Karnaugh map or K map.
40
Maurice Karnaugh
PHY 201 (Blum)
41
The rules





Put the truth table into a form with inputs in
gray code order.
Then one identifies output “blocks” (as large
as possible).
A block must be a rectangle containing 1’s
and only 1’s.
The simplification rules require that the
number of 1’s in a block should be a power of
2 (1, 2, 4, 8, …).
However, a given output 1 can belong to
more than one block.
42
Wrapping



There are still cases in which inputs
differing by only one bit are not
adjacent (e.g. the first and last row).
Imagine that the rows wrap around, so
for instance, a block can include the top
and bottom rows (without intermediate
rows).
Similarly for columns.
43
W
X
Y
Z
Output
0
0
0
0
1
0
0
0
1
0
0
0
1
0
0
0
0
1
1
0
0
1
0
0
1
0
1
0
1
1
0
1
1
0
1
0
1
1
1
0
1
0
0
0
1
1
0
0
1
0
1
0
1
0
0
1
0
1
1
0
1
1
0
0
1
1
1
0
1
1
1
1
1
0
1
1
1
1
1
0
Karnaugh Example
44
Karnaugh Example (Unsimplified
Boolean algebra expression)

WXY’Z
WX’Y’Z’
WXYZ’
W’XY’Z’
+
+
+
+
W’XY’Z +
W’X’Y’Z’ +
WXY’Z’ +
W’XYZ’
45
Example in Karnaugh (identifying
block in gray code truth table)
Z
W
0
0
1
1
0
X\Y 0
0
1
1
0
0
0
1
1
0
1
W’XY’Z’
W’XY’Z
1
1
WXY’Z’
WXY’Z
1
0
0
1
W’X’Y’Z’
0
1
1
1
1
0
WX’Y’Z’
W’XYZ’
0
1
WXYZ’
0
0
46
Result




Y’Z’ + XY’ + X Z’
A block of size two eliminates one Boolean
variable; a block of four eliminates two Boolean
variables; and so on.
To find the expression for a block, identify the
inputs for that block that don’t change, AND
them together, that’s your expression for the
block.
Obtain an expression for each block and OR
them together. Every 1 must belong to at least
one block (even if it is a block onto itself).
47
Online References




http://www.facstaff.bucknell.edu/masta
scu/eLessonsHTML/Logic/Logic3.html
http://www.cs.usm.maine.edu/~welty/k
arnaugh.htm
http://en.wikipedia.org/wiki/Frank_Gray
_(researcher)
http://en.wikipedia.org/wiki/Maurice_Ka
rnaugh
PHY 201 (Blum)
48