ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
1
DIGITAL ELECTRONICS AND
MICROPROCESSORS
ELM3111 Digital Electronics and
Microprocessors
Some of the contents are adopted from
M. Morris Mano, Michael D Ciletti.Digital Design, 4nd edition, Pearson & Prentice Hall, 2007.
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
Contents
› Karnaugh Diagrams (Examples)
4- Combinational Design Procedure
2
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
Karnaugh Diagrams (Examples)
3
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
4
Rules for K-Maps
 We can reduce functions by circling 1’s in the K-map
 Each circle represents minterm reduction
 Following circling, we can deduce minimized and-or form.
Rules to consider
Every cell containing a 1 must be included at least once.
The largest possible “power of 2 rectangle” must be enclosed.
The 1’s must be enclosed in the smallest possible number of rectangles.
5
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
K-Maps
Possible reductions on K-Map
AB
CD
00
00
0
1
4
01
11
10
AB
CD
12
00
1
01
1
10
0
4
12
1
8
11
1
5
1
13
1
8
1
00
11
01
9
01
1
1
3
15
1
11
11
1
5
7
1
3
1
7
13
15
9
11
1
AB
10
2
1
6
1
14
1
10
1
10
CD
00
00
0
1
10
AB
CD
11
1
1
10
3
1
2
1
4
5
7
6
12
13
15
14
01
11
01
8
1
00
9
1
01
1
11
11
1
10
10
2
00
1
0
1
3
1
2
6
01
1
4
5
7
1
6
14
11
1
12
13
15
1
14
10
10
1
8
9
11
1
10
1
1
1
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
6
K-Maps
Example
Minimize the function F(A,B,C,D) = Σ(1,2,4,5,7,6,8,10,13,15) using K-maps
representation.
AB
CD
For 15 the circle (5-7-13-15) is the largest one.
5,7,13 is covered
00
0
00
01
11
10
1
4
12
1
8
01
1
1
11
1
5
13
1
9
3
1
7
10
1
1
2
6
15
14
11
10
1
For 4 the circle (4-5-7-6) is the largest one.
6 is covered.
For 8 the circle (8-10) is the largest one.
10 is covered
For 1 the circle (1-5) is the largest one.
1
For 2 the circle (2-6) is the largest one.
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
7
K-Maps
AB
CD
A’C’D
00
A’B
01
11
10
00
0
1
4
12
1
8
01
1
1
11
1
5
13
1
9
3
1
7
15
1
11
10
1
1
2
A’CD’
6
14
BC
10
1
AB’D’
F(A,B,C,D) =A’B+BC+A’C’D+A’CD’+AB’D’
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
8
K-Maps
Example
Minimize the function F(A,B,C,D) = Σ(0,2,3,5,7,8,9,10,11,13,15) using K-maps
representation.
AB
CD
00
For 0 the circle (0-2-8-10) is the largest one.
2,8,10 is covered
00
01
0
1
1
4
01
11
10
12
1
8
1
5
13
1
1
9
11
1
3
10
1
2
7
6
15
14
11
10
1
1
1
1
For 3 either the circle (3-7-11-15) or (3-2-11-10)
is the largest one. 7-11-15 is covered.
For 5 the circle (5-7-13-15) is the largest one.
13 is covered
For 9 either the the circle (8-9-11-10) or (9-11-13-15) is
the largest one.
9
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
K-Maps
AB
CD
00
BD
00
01
0
1
4
5
1
01
11
10
12
1
8
1
13
1
1
9
B’D’
11
1
3
10
1
2
7
6
15
14
1
1
11
1
CD
F(A,B,C,D) =AB’+BD+B’D’+CD
10
1
One other candidate is
F(A,B,C,D) =AD+BD+B’D’+CD
13
AB’
1
1
9
15
1
11
1
AD
10
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
Karnaugh maps: Don’t cares
In some cases, outputs are undefined
We “don’t care” if the logic produces a 0 or a 1
This knowledge can be used to simplify functions.
•
•
•
AB
CD
00
00
0
01
1
11
1
10
0
01
0
4
12
8
0
1
1
X
11
1
5
13
9
X
X
0
0
10
3
7
15
11
0
1
0
0
2
6
14
10
- Treat X’s like either 1’s or 0’s
- Very useful
- OK to leave some X’s uncovered
A
B
C
D
F
0
0
0
0
0
0
0
0
1
1
0
0
1
0
0
0
0
1
1
1
0
1
0
0
0
0
1
0
1
1
0
1
1
0
X
0
1
1
1
1
1
0
0
0
0
1
0
0
1
1
1
0
1
0
0
1
0
1
1
0
1
1
0
0
X
1
1
0
1
X
1
1
1
0
0
1
1
1
1
0
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
11
Don’t Care Conditions
•
Sometimes we don’t care about the value of a function for certain
combinations of the variables.
• these combinations may be impossible in certain contexts
• or the value of the function may not matter in when the combinations
occur
•
In such situations we say the function is incompletely specified and there are
multiple (completely specified) logic functions that can be used in the design.
• so we can select a function that gives the simplest circuit
•
When constructing the terms in the simplification procedure, we can choose
to either cover or not cover the don’t care conditions.
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
Don’t Care Conditions
AB
B’C’
CD
00
00
0
01
1
11
1
10
0
01
0
4
12
8
0
1
1
X
11
1
5
13
9
X
X
0
0
10
3
7
15
11
AB’
0
1
0
0
2
6
14
10
F(A,B,C,D) =AB’+B’C’
12
13
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
Don’t Care Conditions
AB
CD
00
00
0
01
X
11
1
10
X
01
0
4
12
8
1
X
1
0
11
1
5
13
9
0
X
1
1
AB
10
3
7
15
11
0
1
X
1
2
6
14
10
CD
00
00
0
01
0
11
1
10
X
01
0
4
12
8
0
1
1
0
11
1
5
13
9
X
X
1
1
10
3
7
15
11
0
1
X
1
2
6
14
10
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
4- Combinational Design Procedure
14
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
Overview
• 4- Combinational Design Procedure
• Design digital circuit from specification
• Digital inputs and outputs known
• Need to determine logic that can transform data
• Start in truth table form
• Create K-map for each output based on function of inputs
• Determine minimized sum-of-product representation
• Draw circuit diagram
15
16
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
Design Procedure
Design a circuit from a specification.
1.
Determine number of required inputs and outputs.
2.
Derive truth table
3.
Obtain simplified Boolean functions
A
B
C
R
S
4.
Draw logic diagram and verify correctness
0
0
0
0
0
0
0
1
0
1
0
1
0
0
1
0
1
1
0
1
1
0
0
0
1
1
0
1
0
1
1
1
0
0
1
1
1
1
1
1
S=A+B+C
R = ABC
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
17
Previously, we have learned…
•
Boolean algebra can be used to simplify expressions, but not obvious:
• how to proceed at each step, or
• if solution reached is minimal.
•
Have seen five ways to represent a function:
• Boolean expressions | minterms/maxterms
• Truth table | Karnaugh map
• logic circuit
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
Combinational logic design
• Use multiple representations of logic functions
• Use graphical representation to assist in simplification of function.
• Use concept of “don’t care” conditions.
• Example - encoding BCD to seven segment display.
• Similar to approach used by designers in the field.
18
19
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
BCD to Seven Segment Display
• Used to display binary coded decimal (BCD) numbers using seven
illuminated segments.
• BCD uses 0’s and 1’s to represent decimal digits 0 - 9. Need four bits to
represent required 10 digits.
• Binary coded decimal (BCD) represents each decimal digit with four bits
Input
Output
N
A B
C D a,b,c,d,e,f,g
0
0
0
0
0
1
0
0
0
1
2
0
0
1
0
3
0
0
1
1
4
0
1
0
0
5
0
1
0
1
6
0
1
1
0
7
0
1
1
1
8
1
0
0
0
9
1
0
0
1
a
f
?
g
e
b
c
d
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
20
BCD to Seven segment display
• List the segments that should be illuminated for each digit.
0
1
2
3
4
5
6
7
8
9
a, b, c, d, e, f
b, c
a, b, d, e, g
a, b, c, d, g
b, c, f, g
a, c, d, f, g
a, c, d, e, f, g
a, b, c
a, b, c, d, e, f, g
a, b, c, d, f, g
here b+c means they should be lit together for 1
21
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
BCD to seven segment display
• Derive the truth table for the circuit.
• Each output column in one circuit.
Input
a
Output
N
A
B
C
D
a b c d e f
g
0
0
0
0
0
1 1 1 1 1 1
0
1
0
0
0
1
0 1 1 0 0 0
0
2
0
0
1
0
1 1 0 1 1 0
1
3
0
0
1
1
1 1 1 1 0 0
1
4
0
1
0
0
0 1 1 0 0 1
1
5
0
1
0
1
1 0 1 1 0 1
1
6
0
1
1
0
1 0 1 1 1 1
1
7
0
1
1
1
1 1 1 0 0 0
0
8
1
0
0
0
1 1 1 1 1 1
1
9
1
0
0
1
1 1 1 1 0 1
1
f
g
e
b
c
d
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
22
BCD to seven segment display
For a(A,B,C,D) function
Without ‘don’t care conditions’
AB
CD
00
1
01
0
11
B’CD’
00
10
0
4
12
1
8
01
0
1
1
5
11
1
1
3
7
10
1
1
2
6
13
15
14
9
11
10
1
Only filled in ten squares the others are not
given
A’C
A’BD
B’D’
a(A,B,C,D) =A’C+B’D’+AB’C+B’CD’
AB’C
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
BCD to seven segment display
For a(A,B,C,D) function
With ‘don’t care conditions’
AB
CD
00
00
1
01
0
11
X
10
1
0
4
12
8
01
0
1
1
5
13
X
1
9
11
1
1
3
7
15
X
11
X
10
1
1
2
6
C
BD
14
X
A
10
X
B’D’
a(A,B,C,D) =A+C+BD+B’D’
23
24
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
BCD to seven segment display
• Find also,
ABCD
• b(A,B,C,D) function
• c(A,B,C,D) function
• d(A,B,C,D) function
• e(A,B,C,D) function
• f(A,B,C,D) function
• g(A,B,C,D) function
Logic circuit
for ‘a’
a
Logic circuit
for ‘b’
b
Logic circuit
for ‘c’
c
Logic circuit
for ‘d’
d
Logic circuit
for ‘e’
e
Logic circuit
for ‘f’
f
Logic circuit
for ‘g’
g
Download

ELM3111 Digital Electronics and Microprocessors Combinational