CSC: 345
Computer Architecture
Jane Huang
Lecture 2
Digital Logic (Appendix A)
Todays Overview
Complete discussion on Instruction Cycle.
Homework questions and discussion.
Appendix A
Digital Logic
Boolean Algebra
Gates
Combination Circuits
Sequential Circuits
Discuss Small group presentations
Digital Logic
Digital circuitry designed and analysed using Boolean
algebra.
George Boole, English Mathematician, proposed basic
principles of boolean algebra in his
1854 treatise on An Investigation
of the Laws of Thought on Which
to Found the Mathematical Theories
of Logic and Probabilities
Boolean algebra is used for:
Analysis: Describe the function of
digital circuitry.
Design: To develop a simplified
implementation of a given
functionality.
Boolean Algebra
Variables (True = 1, False = 0)
Operations: AND , OR + , NOT .
A AND B
A OR B
NOT A
= A B (Also can be represented as AB)
= A+ B
= A
We can represent these operations using truth tables:
P
NOT P
P AND Q
P OR Q
P XOR Q P NAND Q
P NOR Q
In the absence of parentheses, AND takes precedence over OR.
Watch out for this distributive law:
A + (B C) = (A + B) (A + C)
DeMorgans theorem will be very helpful to us!
Examples
Construct a truth table for ABC + AB
A
ABC
AB
ABC + AB
Gates
Logical functions are implemented by the
interconnection of gates.
A gate is an electronic circuit that produces an output
signal as a simple boolean operation on its input
signals.
Gates include:
AND Gate
AND
X Y
OR
0 0
NOT
0 1
NAND
1 0
AND Gate
NOR
1 1
F=XY
F = XY
F
0
0
0
1
Gates
OR Gate
F = X+Y
NOT Gate
X Y
X Y
X Y
X Y
NAND Gate
F = (XY)
NOR Gate
F = (X+Y)
F=X
XOR Gate
F = (XY)+(XY)
Functionally Complete Sets
Design and fabrication are simpler if only one or two
types of gates are used.
We need to identify functionally complete sets of gates:
AND, OR, NOT
(Obvious why this is complete!)
AND, NOT
Synthesize OR from DeMorgans theorem.
OR, NOT
Synthesize AND from DeMorgans theorem.
NAND
NOR
Not so intuitive!!
DeMorgans Theorem:
AB = A + B
Use of NAND gates to create a functional
complete set of gates.
A
A
B
AB
AB
A
A+B
Combinational Circuits
An interconnected set of gates.
Output at any time is a function of the input at that
time.
Appearance of input followed almost immediately
by appearance of output.
For any given function there are a number of
alternative circuits that can be used.
Example:
F = ABC + ABC + ABC
Sum of Products
An Alternate Form:
F = ABC + ABC + ABC
(Sum of Products)
An equivalent representation is
given as:
F = (ABC) (ABC) (ABC) (ABC) (ABC)
(ie none of the input combinations that produce 0 is true)
Apply DeMorgans theorem
(X Y Z) = X + Y + Z
Convert to Product of Sums
An Alternate Form:
F = (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
C
A
B
C
Product of Sums
Algebraic Simplification
Need to reduce an algebraic expression to one with
fewer elements.
Simpler (smaller, cheaper, faster) implementation
F = ABC + ABC + ABC
is equivalent to:
F = AB + BC
or
A
F = B(A + C)
C
F
B
Simplification Methods
Apply algebraic identities to simplify:
Try simplifying F = ABC + ABC + ABC
We need a simpler approach!!
Karnaugh Maps
Represents a boolean function of up to 6 variables.
Array of 2n squares representing the possible
combinations of n binary variables.
Functions of 2 variables are represented respectively
as:
Karnaugh maps borrowed from: http://www.maxmon.com/kmaps1.htm
Karnaugh Maps
Using Karnaugh Maps
C
CD
00 01 11 10
AB
00
01
A
11
10
D
Any two adjacent squares
differ in only one of the
variables.
If two adjacent squares both
have a 1 in them then the
corresponding terms only
differ in one variable.
The two terms can be merged
by eliminating that variable.
In this example:
F = ABCD + ABCD can be simplified to ABD
Duplication Rules
Adjacency rules can be extended in several ways:
Wrapping around the edge of the map is allowed.
(ie top square is adjacent to bottom square, and
LHS to RHS).
Instead of grouping just 2 squares we can group
2n squares. (ie 2, 4, 8 etc)
Amongst the marked squares (ie with 1s), circle the
largest possible blocks (1,2,4,8)
Make sure that each marked square is in at least one
block. (i.e some squares might appear in more than
one circle if for examle there are three 1s in a row).
CD
AB
00 01 11 10
00
00
11
F = BCD
01
A
00 01 11 10
00
10
F = AB
AB
11
CD
00 01 11 10
10
00 1
11
F = ABD
CD
AB
01 1
10
00 01 11 10
AB
01
A
CD
01
11
10
F = BC
CD
AB
00 01 11 10
00
01
11
10
CD
00 01 11 10
AB
00
01
B
A
11
10
1
D
CD
AB
CD
00 01 11 10
AB
00 01 11 10
00 1
00
01 1
01
11
10
11
B
A
10
D
Overlapping Groups
Any group of 1s that is completely overlapped by other
groups can be eliminated.
C
CD
AB
00 01 11 10
AB
00
CD
00 01 11 10
00
01
11
10
1
D
B
A
01
11
10
1
D
In some cases, certain combinations of variables never occur,
and therefore we just dont care about whether they are set to 1
or 0.
These are marked as d on the K-Maps and may be included or
excluded from groupings.
An Example
Develop the boolean expressions for a circuit that adds 1 to
a packed decimal digit.
In a packed decimal digit, each digit is represented by a 4bit code.
For example: 8 1000
729 0111 0010 1001
Method:
Develop a truth table showing inputs and outputs.
Plot the function onto a karnaugh map.
Simplify the karnaugh map.
Construct the circuit.
Number
Input
B
Output
W
Dont Care
Number
CD
AB
00 01 11 10
00 01 11 10
AB
00
00
01
11 d
CD
10 1
01
B
A
11 d
10
D
C
00 01 11 10
AB
00 01 11 10
00
01
11 d
CD
00
CD
AB
10
D
01
B
A
11 d
10
D
CD
AB
Start with the first output variable
Mark the dont cares.
00 01 11 10
00
01
A
11
10
Mark a 1 in the correct square to
represent 1s in the output variables
column from the truth table.
Create groupings.
W = AD + BCD
CD
AB
00 01 11 10
00
AB
00 01 11 10
00
01
A
CD
11
10
01
B
A
11
10
A Small Group Activity
Work in groups to design a circuit capable of performing a
right circular shift on the binary representation of numbers
0 to 7.
For example 5 = 0101.
If we circular shift the bits right one
position then:
Create a truth table for the
0 1 0 1
input and output variables.
Create a karnaugh-map for
0 1 0
1
each output variable.
Reduce the map.
Draw the circuit.
1 0 1 0
Multiplexers
Connects multiple inputs to a single output.
At any one time ONE of the inputs is selected and passed
to the output.
D0
D1
4-to-1
MUX
D2
D3
S2
S1
S2
S1
D0
D1
D2
D3
Multiplexer Implementation
S2
S1
D0
D1
F
D2
D3
S2
S1
D0
D1
D2
D3
Used in digital circuits
to control signal and
data routing.
Loading of the PC in
which the value may
come from:
Binary counter
IR
Output of ALU
Multiplexer Input to Program Counter
C0
IR0 ALU0
S2
C1
IR1 ALU1
S2
4-to-1 MUX
S1
4-to-1 MUX
S1
PC0
PC2
Decoders
A
A combinatorial circuit
with a number of output
B
lines.
Only one output line is
C
asserted at any time.
The asserted output line is
selected by the inputs.
A decoder has n inputs and
2n outputs.
000
D0
001
D1
010
D2
011
D3
100
D4
101
D5
110
111
D6
D7
Decoder Usage
Many uses for example address decoding.
IK-byte memory using four 256 X 8-bit RAM chips
Single unified address space broken down as:
0000-00FF Chip 0
0100-01FF Chip 1
0200-02FF Chip 2
0300-03FF Chip 4
Each chip requires 8 address lines supplied by lower 8 bits of the address.
(Why 8 lines?)
The higher order 2 bits are used to select one of the four RAM chips.
A 2-to-4 decoder is used whose output enables one of the four chips.
Address Decoding
A0
A7
256 X 8
RAM
Enable
A8
A9
2X4
Decoder
256 X 8
RAM
Enable
256 X 8
RAM
Enable
256 X 8
RAM
Enable
Sequential Circuits
Normally combinational circuits provide no memory or state
information.
In a sequential circuit, the output depends on:
Current input
Current state
Simplest form of a sequential circuit is the flip-flop.
S-R Latch
Clocked S-R Flip-Flop
D Flip-Flop
J-K Flip-Flop
A flip-flop is a bi-stable device existing in one of two states
(1 or 0). It only changes state if new input appears.
The flip-flop has two outputs usually labeled Q and Q. These
are the complements of each other.
S-R Latch
R
10
NOR Gate
F = (X+Y)
R S
Bistable:
R=S=0, Q=0
R=S=0, Q=1
Therefore 1 bit memory
with Q representing the
value of the bit.
S and R write values 1
and 0 respectively.
Time delay occurs
(asynchronous operation)
S-R Latch
10
Characteristic Table
Current
Inputs
Current
State
Next
State
SR
Qn
Qn+1
00
00
01
01
10
10
Simplified
Characteristic Table
S
Qn+1
Qn
11
---
11
---
---
Clocked S-R Latch
In a digital computer, events are often synchronized with a clock
pulse:
The output can only be reset on the clock pulse.
R
Q
Clock
D Flip-Flop
Q
Clock
Qn+1
D Flip-flop solves the
problem of non-allowable
inputs.
Implementing an 8-bit parallel register
Conclusions
Next week Chapter 3 I/O Interconnection
Structures
Please check the website for additional helpful
readings.
Groups sign-up for a small group before you
leave tonight.
Homework is posted on the website.
Any additional questions?
