CS310-CH19 - APPA - CombinationalCircuits

Prévia do material em texto

1
Combinational Circuits
Western Illinois University
Department of Computer Science
Prof. Paulo Martins
Created by W. Stallings
Modified by P. Martins
Computer Organization 
& Architecture 
6th Edition
2
3
Defining a Combinational 
Circuit
1. Graphic symbols
2. Truth Table
3. Boolean Equations
4
Representation of Combinatorial 
Circuits
Equation � Truth Table � Circuit
5
Basic Identities of Boolean Algebra
6
A Boolean Function of three 
Variables
A B C F
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 0
7
Sum of Products (SOP)
F = ABC + ABC + ABC
8
SOP Implementation
9
Karnaugh Maps
� Is used for simplification
� Used for representing a Boolean 
function as a function of a small 
number of variables (up to six)
� It is an array of 2eN squares (N = 
number of input variables)
10
K Maps (represent boolean functions)
11
Rules for simplification
� Build Karnaugh Map
� Among the marked squares (squares 
with 1), find those that belong to a 
unique largest block of either 1,2,4 or 8 
and circle those blocks
� Select additional blocks of marked 
squares that are as large as possible 
and as few in number as possible.
12
Rules for simplification
� Continue to draw loops around single marked 
squares, or pairs of adjacent marked squares, 
or groups of four, eight and so on, in such a 
way that every marked square belongs to at 
least one loop.
� If any isolated 1s remain after the groupings, 
then each of these is circled as a group of 1s.
� Any group of 1s that is completely overlapped 
by other groups can be eliminated
13
Use of Karnaugh Maps
14
K-Map: ABD
AB/CD 00 01 11 10
00
01 1 1
11
10
15
K – Map: AB 
AB/CD 00 01 11 10
00 1 1 1 1
01
11
10
16
K-Map: A
AB/CD 00 01 11 10
00 1 1 1 1
01 1 1 1 1
11
10
17
K-Map: D
AB/CD 00 01 11 10
00 1 1
01 1 1
11 1 1
10 1 1
18
K-Map: C
AB/CD 00 01 11 10
00 1 1
01 1 1
11 1 1
10 1 1
19
K-Map: BD
AB/CD 00 01 11 10
00
01 1 1
11 1 1
10
20
K-Map: ABD
AB/CD 00 01 11 10
00
01 1 1
11
10
21
K-Map: BCD
AB/CD 00 01 11 10
00 1
01
11
10 1
22
K-Map: BC
AB/CD 00 01 11 10
00
01 1 1
11 1 1
10
23
Simplify Equation (A1)
24
Karnaugh Map – three 
variables
00 01 11 10
0
1
A
BC
25
Truth Table (used to build 
Map)
A B C F
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 0
26
K – Map 
A/BC 00 01 11 10
0
1 1
1
1
27
K – Map 
A/BC 00 01 11 10
0
1 1
1
1
28
Simplified Equation
F = AB + BC
29
Simplified Circuit
� Draw simplified circuit from previous 
slide
� Compare with circuit in slide 8
30
Multiplexers
4-to-1 MUX
F
D0
D1
D2
S2 S1
D3
31
Application
4-to-1 MUX
F – Program 
Counter
Binary counter – D0
Instruction Reg –D1
ALU – D2
S2 S1
32
Mux Input to Program Counter
33
4-to-1 Multiplexer Truth Table
S2 S1 F
0 0 D0
0 1 D1
1 0 D2
1 1 D3
34
Multiplexer Implementation
35
Decoders – Definition
DECODER
(only one output line is
“activated” at any 
Time)
36
Decoder Implementation
37
Application: Decoding Address Space
Used to select RAM IC
Used to select memory space inside RAM IC 
38
Address Decoding
Data bus D0-D7
39
Demultiplexer
DEMUX
2-4Data line
Select 
S0
S1
40
Demultiplexer Implementation
41
Demultiplexer
Data input
42
Programmable Logic Array
� For each particular logic function, the 
layout of gates have to be designed.
� That involves cost and time
� A general-purpose chip can be readily 
adapted for specific purposes
� Welcome the “Programmable Logic 
Array!”
43
PLA - Premises
Any Boolean Function 
can be expressed in 
a sum-of-products 
(SOP) form
44
PLA - Implementation
45
Exercise
� Implement the functions: 
F = ABC + AB and
F = AB + AC 
using the previous PLA
46
PLA - Implementation
47
Read Only Memory
� Combination circuits are “memoryless”
� ROMs are, however, implemented with 
combinational circuits
� ROMs function – Given a set of input 
lines (addresses), always produces the 
same output (data lines).
� Outputs are a function ONLY of the 
present inputs
48
Truth table for ROM
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1
0 0 1 0 0 0 1 1
0 0 1 1 0 0 1 0
0 1 0 0 0 1 1 0
0 1 0 1 0 1 1 1
0 1 1 0 0 1 0 1
0 1 1 1 0 1 0 0
1 0 0 0 1 1 0 0
1 0 0 1 1 1 0 1
1 0 1 0 1 1 1 1
1 0 1 1 1 1 1 0
1 1 0 0 1 0 1 0
1 1 0 1 1 0 1 1
1 1 1 0 1 0 0 1
1 1 1 1 1 0 0 0
X4 X3 X2 X1 Z1 Z2 Z3 Z4
49
64-Bit ROM
00
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
Note that Z1 is 
connected to the 
last 8 outputs
50
Binary Addition Equations
Sum = ABC+ABC+ABC+ABC
Carry = AB + AC + BC
51
Binary Addition Truth Tables
A B SUM CARRY
OUT
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
52
Binary Addition Truth Tables
Cin A B SUM Cout
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1
53
4 bit adder
54
Implementation of an Adder
55
A 32-Bit Adder
8-bit
adder
8-bit
adder
8-bit
adder
8-bit
adder
56
References
� Appendix A - Computer Organization 
and Architecture - Designing for 
Performance - William Stallings, 6th
Edition.