Computer Science Timing Diagram of Latch and Flip Flop Questions

Guidelines:
● Looking up, paraphrasing, or copying answers from the Internet or other sources is not
allowed.
doing so is a violation of academic honesty. You must cite any sources you use, e.g.,
reference books, Wikipedia, etc.
● Provide more details in your responses! Otherwise, you will lose points.
Warning: any submissions not following the above guidelines will receive a score of zero.
Q1
Q2
Q3
Q4
Total
10
20
20
20
70
Question 1
[10 points]
Timing Diagram of Latch and Flip-Flop: Given the input waveforms shown below, sketch the
output D-Latch of the latch and the output D-FF of the flip-flop.
Question 2
Convert the following Mealy machine into the equivalent Moore machine.
[20 points]
a. Complete the transition table for the above Mealy machine.
[5 points]
b. Draw the transition table for the Moore machine.
[5 points]
c. Draw the transition diagram for the Moore machine
[10 points]
Question 3
[20 points]
Given a state machine has one input x(t) and two-bit state (Q1 (t), Q0 (t)). The machine is
described by the following state equations.
Q1(t + 1) = x(t)Q′0(t) + Q1(t),
Q0(t + 1) = x(t)Q′1(t)Q0(t) + x′(t)Q1(t).
Use two D flip-flops and a minimal sum-of-products network to implement the machine.
a. Write the state table of the system.
[5 points]
b. Describe the design using a logic diagram. Show your derivation using K maps. [15 points]
Question 4
[20 points]
A sequential network has one binary input x(t) and one binary output y(t). The network
produces y = 1, whenever input pattern x(t − 3, t)= 0010 or 0111. Other- wise, the output y = 0.
a. Draw the state diagram.
b. Write the state table.
[10 points]
[10 points]
The Design Procedure
§ Specification
§ Formulation – Obtain a state diagram or state table
§ State Assignment – Assign binary codes to the states
§ Flip-Flop Input Equation Determination – Select flip-flop
types and derive flip-flop equations from next state entries in the
table (Text book pp. 210 Section 4-4)
§ Output Equation Determination – Derive output equations
from output entries in the table
§ Optimization – Optimize the equations
§ Technology Mapping – Find circuit from equations and map to
flip-flops and gate technology
§ Verification – Verify correctness of final design
Chapter 5 – Part 2 3
Specification
§ Component Forms of Specification
• Written description
• Mathematical description
• Hardware description language*
• Tabular description*
• Equation description*
• Diagram describing operation (not just structure)*
§ Relation to Formulation
• If a specification is rigorous at the binary level
(marked with * above), then all or part of
formulation may be completed
Chapter 5 – Part 2 4
Formulation: Finding a State Diagram
§ A state is an abstraction of the history of the past
applied inputs to the circuit (including power-up reset
or system reset).
• The interpretation of “past inputs” is tied to the synchronous
operation of the circuit. E. g., an input value (other than an
asynchronous reset) is measured only during the setup-hold
time interval for an edge-triggered flip-flop.
§ Examples:
• State A represents the fact that a 1 input has occurred among
the past inputs.
• State B represents the fact that a 0 followed by a 1 have
occurred as the most recent past two inputs.
Chapter 5 – Part 2 5
Formulation: Finding a State Diagram
§ In specifying a circuit, we use states to remember
meaningful properties of past input sequences that are
essential to predicting future output values.
§ A sequence recognizer is a sequential circuit that
produces a distinct output value whenever a prescribed
pattern of input symbols occur in sequence, i.e,
recognizes an input sequence occurence.
§ We will develop a procedure specific to sequence
recognizers to convert a problem statement into a state
diagram.
§ Next, the state diagram, will be converted to a state
table from which the circuit will be designed.
Chapter 5 – Part 2 6
Sequence Recognizer Procedure
§ To develop a sequence recognizer state diagram:
• Begin in an initial state in which NONE of the initial portion of
the sequence has occurred (typically “reset” state).
• Add a state that recognizes that the first symbol has occurred.
• Add states that recognize each successive symbol occurring.
• The final state represents the input sequence occurrence.
• Add state transition arcs which specify what happens when a
symbol not in the proper sequence has occurred.
• Add other arcs on non-sequence inputs which transition to
states that represent the input subsequence that has occurred.
§ The last step is required because the circuit must recognize the
input sequence regardless of where it occurs within the overall
sequence applied since “reset.”.
Chapter 5 – Part 2 7
State Assignment
§ Each of the m states must be assigned a
unique code
§ Minimum number of bits required is n
such that
n ≥ log2 m
where x is the smallest integer ≥ x
§ There are useful state assignments that
use more than the minimum number of
bits
§ There are 2n – m unused states
Chapter 5 – Part 2 8
Sequence Recognizer Example
§ Example: Recognize the sequence 1101
• Note that the sequence 1111101 contains 1101 and “11” is a
proper sub-sequence of the sequence.
§ Thus, the sequential machine must remember that the
first two one’s have occurred as it receives another
symbol.
§ Also, the sequence 1101101 contains 1101 as both an
initial subsequence and a final subsequence with some
overlap, i. e., 1101101 or 1101101.
§ And, the 1 in the middle, 1101101, is in both
subsequences.
§ The sequence 1101 must be recognized each time it
occurs in the input sequence.
Chapter 5 – Part 2 9
Example: Recognize 1101
§ Define states for the sequence to be recognized:
• assuming it starts with first symbol,
• continues through each symbol in the sequence to be
recognized, and
• uses output 1 to mean the full sequence has occurred,
• with output 0 otherwise.
§ Starting in the initial state (Arbitrarily named
“A”):
1/0
• Add a state that
A
B
recognizes the first “1.”
• State “A” is the initial state, and state “B” is the state which
represents the fact that the “first” one in the input
subsequence has occurred. The output symbol “0” means
that the full recognized sequence has not yet occurred.
Chapter 5 – Part 2 10
Example: Recognize 1101 (continued)
§ After one more 1, we have:
• C is the state obtained
when the input sequence
has two “1”s.
A
1/0
B
1/0
C
§ Finally, after 110 and a 1, we have:
A
1/0
B
1/0
C
0/0
D
1/1
• Transition arcs are used to denote the output function (Mealy Model)
• Output 1 on the arc from D means the sequence has been recognized
• To what state should the arc from state D go? Remember: 1101101 ?
• Note that D is the last state but the output 1 occurs for the input
applied in D. This is the case when a Mealy model is assumed.
Chapter 5 – Part 2 11
Example: Recognize 1101 (continued)
A
1/0
B
1/0
C
0/0
D
1/1
§ Clearly the final 1 in the recognized sequence
1101 is a sub-sequence of 1101. It follows a 0
which is not a sub-sequence of 1101. Thus it
should represent the same state reached from the
initial state after a first 1 is observed. We obtain:
A
1/0
B
1/0
C
0/0
D
1/1
Chapter 5 – Part 2 12
Example: Recognize 1101 (continued)
A
1/0
B
1/0
C
0/0
D
1/1
§ The state have the following abstract meanings:
• A: No proper sub-sequence of the sequence has
occurred.
• B: The sub-sequence 1 has occurred.
• C: The sub-sequence 11 has occurred.
• D: The sub-sequence 110 has occurred.
• The 1/1 on the arc from D to B means that the last 1
has occurred and thus, the sequence is recognized.
Chapter 5 – Part 2 13
Example: Recognize 1101 (continued)
§ The other arcs are added to each state for
inputs not yet listed. Which arcs are missing?
A
1/0
B
1/0
C
0/0
D
§ Answer:
1/1
“0” arc from A
“0” arc from B
“1” arc from C
“0” arc from D.
Chapter 5 – Part 2 14
Example: Recognize 1101 (continued)
§ State transition arcs must represent the fact
that an input subsequence has occurred. Thus
we get:
0/0
A
1/0
1/0
B
1/0
0/0
C
0/0
D
1/1
0/0
§ Note that the 1 arc from state C to state C
implies that State C means two or more 1’s have
occurred.
Chapter 5 – Part 2 15
Formulation: Find State Table
§ From the State Diagram, we can fill in the State Table.
§ There are 4 states, one
input, and one output.
We will choose the form
with four rows, one for
each current state.
§ From State A, the 0 and
1 input transitions have
been filled in along with
the outputs.
0/0
A
1/0
1/0
1/0
B
C
0/0
0/0
D
1/1
0/0
Present
State
A
B
C
D
Next State
x=0 x=1
A
B
Output
x=0 x=1
0
0
Chapter 5 – Part 2 16
Formulation: Find State Table
§ From the state diagram, we complete the
state table.
0/0
1/0
A
1/0
B
1/0
0/0
Present
State
A
B
C
D
Next State
x=0 x=1
A
B
A
C
D
C
A
B
Output
x=0 x=1
0
0
0
0
0
0
0
1
C
0/0
D
1/1
0/0
§ What would the state diagram and state table
look like for the Moore model?
Chapter 5 – Part 2 17
Example: Moore Model for Sequence 1101
§ For the Moore Model, outputs are associated with
states.
§ We need to add a state “E” with output value 1
for the final 1 in the recognized input sequence.
• This new state E, though similar to B, would generate
an output of 1 and thus be different from B.
§ The Moore model for a sequence recognizer
usually has more states than the Mealy model.
Chapter 5 – Part 2 18
Example: Moore Model (continued)
0
1
§ We mark outputs on
states for Moore model
0
1
1
A/0
B/0
C/0
D/0
§ Arcs now show only
state transitions
0
1
1
§ Add a new state E to
0
E/1
produce the output 1
§ Note that the new state,
0
E produces the same behavior
in the future as state B. But it gives a different output
at the present time. Thus these states do represent a
different abstraction of the input history.
Chapter 5 – Part 2 19
Example: Moore Model (continued)
§ The state table is shown
below
0
A/0
§ Memory needs more
state in the Moore model:
“Moore is More.”
Present
State
A
B
C
D
E
Next State
x=0 x=1
A
B
A
C
D
C
A
E
A
C
1
1
1
B/0
0
1
0
Output
y
0
0
0
0
1
C/0
0
D/0
1
E/1
0
Chapter 5 – Part 2 20
State Assignment – Example 1
Present
State
A
B
C
D
Next State
x=0 x=1
A
B
A
C
D
C
A
B
Output
x=0 x=1
0
0
0
0
0
0
0
1
§ Does code assignment make a difference in cost?
• Select codes in such a way that the logic required to implement the
flip-flop input equations and output equations is minimized.
• In our example, we simply assign the state codes in Gray code order
because it makes it easier for the next-state and output functions to be
placed on a K map.
Chapter 5 – Part 2 21
State Assignment – Example 1 (continued)
§ Assignment 1: A = 0 0, B = 0 1, C = 1 0, D = 1 1
§ The resulting coded state table:
Present Next State
Output
State x = 0 x = 1 x = 0 x = 1
Y1Y2 D1D2 D1D2
00
00 01
0
0
01
00 10
0
0
10
11 10
0
0
11
00 01
0
1
Chapter 5 – Part 2 22
State Assignment – Example 1 (continued)
§ Assignment 2: A = 0 0, B = 0 1, C = 1 1, D = 1 0
§ The resulting coded state table:
Present Next State
Output
State x = 0 x = 1 x = 0 x = 1
00
00 01
0
0
01
00 11
0
0
11
10 11
0
0
10
00 01
0
1
Chapter 5 – Part 2 23
Find Flip-Flop Input and Output
Equations: Example 1 – Assignment 1
§ Assume D flip-flops
§ Interchange the bottom two rows of the state
table, to obtain K-maps for D1, D2, and Z:
D1
X
D2
X
0 0
0 1
0 1
Y2
0 0
Y1
1 1
0 0
Y2
0 1
Y1
1 0
Z
Chapter 5 – Part 2 24
Optimization: Example 1: Assignment 1
§ Performing two-level optimization:
D1
X
0 0
D2
X
Z
0 1
0 1
Y2
0 0
Y1
1 1
0 0
Y2
0 1
Y1
1 0
D1 = Y1Y2 + XY1Y2
D2 = XY1Y2 + XY1Y2 + XY1Y2
Z = XY1Y2
Gate Input Cost = 22
Chapter 5 – Part 2 25
Find Flip-Flop Input and Output
Equations: Example 1 – Assignment 2
§ Assume D flip-flops
§ Obtain K-maps for D1, D2, and Z:
D1
X
0 0
0 1
Y2
1 1
Y1
0 0
D2
X
0 1
Z
X
0 0
0 0
0 1
Y2
Y2
0 0
0 1
Y1
Y1
0 1
0 1
Chapter 5 – Part 2 26
Optimization: Example 1: Assignment 2
§ Performing two-level optimization:
D1
X
0 0
D2
X
0 1
Z
X
0 0
0 1
Y2
1 1
Y1
0 0
0 0
0 1
Y2
Y2
0 0
0 1
Y1
Y1
0 1
0 1
D1 = Y1Y2 + XY2
Gate Input Cost = 9
D2 = X
Select this state assignment for
Z = XY1Y2 completion of the design
Chapter 5 – Part 2 27
Map Technology
§ Library:
§ Initial Circuit:
• D Flip-flops
with Reset
(not inverted)
• NAND gates
with up to 4
inputs and
inverters
X
Clock
Y1
D
C
R
Z
Y2
D
C
R
Reset
Chapter 5 – Part 2 28
Mapped Circuit – Final Result
Y1
D
C
R
Z
X
Clock
Y2
D
C
R
Reset
Chapter 5 – Part 2 29
Sequential Design: Example 2
§ Design a sequential modulo 3 accumulator for 2bit operands
§ Definitions:
• Modulo n adder – an adder that gives the result of the
addition as the remainder of the sum divided by n
§ Example: (2 + 2) modulo 3 = remainder of 4/3 = 1
• Accumulator – a circuit that “accumulates” the sum of
its input operands over time – it adds each input
operand to the stored sum, which is initially 0.
§ Stored sum: (Y1,Y0), Input: (X1,X0), Output:
(Z1,Z0)
Chapter 6 – Part 2 1
Modulo 3 Accumulator
§ For example, originally, Y1Y0=00 (assume this
state is called A/00) and the first input is X1X0=10,
then ( 10 + 00 ) mod 3 = 10. Therefore, state A/00
will transfer to state C/10. If the first input is
X1X0=01, state A/00 will transfer to B/01 because
the remainder of (stored sum + input) mod 3 = 01.
§ Why we don’t need input X1X0=11 ? Because
whenever the input is 11, no state change!! (
something + 11) mod 3 = something itself!
Chapter 6 – Part 2 2
Analysis
§
§
§
Assume that X1X0 is input (a two-bit binary number),
Z1Z0 is output, Y1Y0 is stored sum and it is used to
store the result of [(X1X0 + Y1Y0) mod 3].
Originally, Y1Y0=00. Also, Z1Z0=Y1Y0 (now you
understand that the output Z1Z0 only depends on the
state Y1Y0 and therefore this is a Moore model
sequential circuit).
We’re using D Flip-Flops for storing Y1Y0. For
example, originally, Y1Y0=00 (assume this state is called
A/00) and the first input is X1X0=01, then (01 + 00) mod
3 = 01. Therefore, state A/00 will transfer to state B/01.
Since there are only 3 possibilities for state Y1Y0 (A/00,
B/01, C/10), we only need 3 states to describe the
behavior of this sequential circuit.
Chapter 6 – Part 2 3
Example 2 (continued)
§ Complete the state diagram:
00
Reset
A/00
01
C/10
B/01
Chapter 6 – Part 2 4
Example 2 (continued)
§ Complete the state table
X 1X 0
Y 1Y 0
00
01
11
10
Z1Z0
Y1(t+1), Y1(t+1), Y1(t+1), Y1(t+1),
Y0(t+1) Y0(t+1) Y0(t+1) Y0(t+1)
A (00)
B (01)
– (11)
C (10)
00
01
X
10
01
10
X
00
X
X
X
X
10
00
X
01
00
01
11
10
§ State Assignment: (Y1,Y0) = (Z1,Z0)
§ Codes are in gray code order to ease use of K-maps in the next step
Chapter 6 – Part 2 5
Example 2 (continued)
§ Find optimized flip-flop input equations for D flip-flops
D1
D0
X1
X1
X 1
1 X
Y1
X X X X
1 X
1
Y0
Y1
X
X X X X
Y0
X
X 1
X0
X0
§ D1 = Y1X1’X0’ + Y0X0 + Y1’Y0’X1
§ D0 = Y0X1’X0’ + Y1X1 + Y1’Y0’X0
1
Chapter 6 – Part 2 6
Circuit – Final Result with AND, OR, NOT
X1
Y1
D
X0
Z1
C
R
Y0
D
Z0
C
R
Reset
Clock
Chapter 6 – Part 2 7
Sequential Design: Example 3 (Q4-13)
§ Design a sequential circuit with two D
flip-flops A and B and one input X. When
X=0, the state of the circuit remains the
same. When X=1, the circuit goes through
the state transitions from 00 to 10 to 11 to
01, back to 00, and then repeats.
Chapter 6 – Part 2 8
Draw the state table
Chapter 6 – Part 2 9
Derive equations using K-map
Chapter 6 – Part 2 10
Terms of Use
§ © 2004 by Pearson Education,Inc. All rights reserved.
§ The following terms of use apply in addition to the standard Pearson
Education Legal Notice.
§ Permission is given to incorporate these materials into classroom
presentations and handouts only to instructors adopting Logic and
Computer Design Fundamentals as the course text.
§ Permission is granted to the instructors adopting the book to post these
materials on a protected website or protected ftp site in original or
modified form. All other website or ftp postings, including those
offering the materials for a fee, are prohibited.
§ You may not remove or in any way alter this Terms of Use notice or
any trademark, copyright, or other proprietary notice, including the
copyright watermark on each slide.
§ Return to Title Page
Chapter 6 – Part 2 15
Sequential Networks:
Registers, Finite State Machines
1
D Flip-Flop (Delay)
Q
D
CLK
Q’
State table
PS D 0 1
0 0 1
1 0 1
Id
D Q(t) Q(t+1)
0
1
2
3
0
0
1
1
0
1
0
1
0
0
1
1
Characteristic Expression
Q(t+1) = D(t)
What does the
equation mean?
NS= Q(t+1)
2
iClicker
How long does a D-flip flop store a bit before its
output can potentially change?
A. Half a clock cycle
B. One clock cycle
C. Two clock cycles
D. There is no minimum time
3
4
Shift register
• Holds & shifts samples of input
OUT1
IN
D Q
D Q
OUT2
D Q
OUT3
OUT4
D Q
CLK
5
Pattern Recognizer
• Combinational function of input samples
OUT
OUT1
IN
D Q
D Q
OUT2
D Q
OUT3
OUT4
D Q
CLK
6
Counters
•Sequences through a fixed set of patterns
OUT1
IN
D Q
D Q
OUT2
D Q
OUT3
OUT4
D Q
CLK
7
What we will learn:
1. Describe the desired behavior of a sequential circuit over time
(FSMs)
2. Given the behavior of a sequential circuit, implement the circuit
Describing Wall-E
Wall-E is a Finite State Machine
Active
Inactive
Implementing Wall-E
8
Finite State Machines:
Describing circuit behavior over time
Symbol/ Circuit
2 bit Counter
9
Finite State Machines:
Describing circuit behavior over time
Output over time
Symbol/ Circuit
CLK
time
Free running
2 bit Counter
Q1
Q0
What is the expected output of the counter over time?
10
Finite State Machines:
Describing circuit behavior over time
Symbol/ Circuit
Diagram that depicts
behavior over time
00
2 bit Counter
01
11
10
11
Implementing the 2 bit counter
S0
S1
S3
Current state
Next State
S0
S1
S1
S2
S2
S3
S3
S0
S2
State Diagram
Q1(t)
Q0(t)
Q1(t+1)
State Table
Q0(t+1)
12
State Table
Q1(t)
Q0(t)
Q1(t+1)
Q0(t+1)
0
0
0
1
0
1
1
0
1
0
1
1
1
1
0
0
PI Q: Which of the following is the likely
structure of the circuit realization of the
counter
A.
Combinational
circuit
Circuit with no flip flops
B.
D
Q0(t)
Combinational
circuit
Q1(t)
D
Q
Q’
Q
Q’
CLK
C.
Q
Q0(t)
Combinational
circuit
Q1(t)
D
Q
Q’
CLK
Circuit with 2 flip flops
Circuit with one flip flop
13
State Table
Q1(t)
Q0(t)
Q1(t+1)
Q0(t+1)
0
0
0
1
0
1
1
0
1
0
1
1
1
1
0
0
B.
D
Q0(t)
Combinational
Q1(t)circuit
D
D0(t) = Q0(t)’
D1(t) = Q0(t) Q1(t)’ + Q0(t)’ Q1(t)
Q
Q’
Q
Q’
CLK
Circuit with 2 flip flops
14
Q1(t)
Q0(t)
Q1(t+1)
Q0(t+1)
0
0
0
1
0
1
1
0
1
0
1
1
1
1
0
0
Q0(t+1) = Q0(t)’
Q1(t+1) = Q0(t) Q1(t)’ + Q0(t)’ Q1(t)
State Table
D
Q0(t)
D
Q1(t)
Q
Q’
Q
Q’
CLK
We store the current state using D-flip
flops so that:
•Inputs to the combinational circuit
don’t change while the next output is
being computed
•The transition to the next state only
occurs at the rising edge of the clock
Implementation of 2-bit counter
15
Finite State Machines
And
Sequential circuit Design
16
Generalized Model of Sequential Circuits
Y
X
S(t)
CLK
17
Canonical Form: Mealy and Moore Machines
Mealy Machine: yi(t) = fi(X(t), S(t))
Moore Machine: yi(t) = fi(S(t))
si(t+1) = gi(X(t), S(t))
x(t)
C1
C2
CLK
S(t)
Mealy Machine
y(t)
x(t)
C1
y(t)
C2
CLK
S(t)
Moore Machine
18
Differences in State Diagram: Mealy vs. Moore
Machines
x(t)
C1
C2
CLK
y(t)
x(t)
C1
y(t)
C2
CLK
S(t)
Mealy Machine
S(t)
Moore Machine
19
Life on Mars?
Mars rover has a binary input x. When it receives the input sequence x(t2, t) = 001 from its life detection sensors, it means that the it has detected
life on Mars ☺ and the output y(t) = 1, otherwise y(t) = 0 (no life on
Mars ).
Implement the Life-on-Mars
Pattern Recognizer!
20
This pattern recognizer should have
A.One state because it has one output
B.One state because it has one input
C.Two states because the input can be 0 or 1
D.More than two states because ….
E.None of the above
Life on Mars?
Mars rover has a binary input x. When it receives the input sequence x(t2, t) = 001 from its life detection sensors, it means that the it has detected
life on Mars ☺ and the output y(t) = 1, otherwise y(t) = 0 (no life on
Mars ).
21
Mars Life Recognizer FSM
Which of the following diagrams is a correct Mealy solution
for the 001 pattern recognizer on the Mars rover?
1/1
A. 1/0
S0
0/0
S1
0/0
S2
0/0
S2
1/0
1/0
B. 1/0
0/0
S0
0/0
C. Both A and B are correct
D. None of the above
S1
1/1
0/0
22
Mars Life Recognizer FFs
Pattern Recognizer ‘001’
x(t)
1/1
1/0
C1
S0
0/0
1/0
S1
0/0
S2
0/0
y(t)
C2
CLK
S(t)
Mealy Machine
What does state table need to show to design controls of C1?
A.(current input x(t), current state S(t) vs. next state, S(t+1))
B.(current input, current state vs. current output y(t))
C.(current input, current state vs. current output, next state)
D.None of the above
23
State Diagram => State Table with State Assignment
x(t)
1/1
1/0
C1
0/0
S0
S1
0/0
S2
C2
y(t)
0/0
CLK
1/0
S(t)
Mealy Machine
S(t)\x
0
1
S0
S1,0
S0,0
S1
S2,0
S0,0
S2
S2,0
S0,1
State Assignment
S0: 00
S1: 01
S2: 10
S(t)\x
0
1
00
01,0
00,0
01
10,0
00,0
10
10,0
00,1
Q1(t+1)Q0(t+1), y
24
State Diagram => State Table => Excitation Table =>
Circuit
Q1(t) Q0(t)\x
0
1
id Q1Q0x
D1
D0
y
00
01,0
00,0
0
000
0
1
0
01
10,0
00,0
10
10,0
00,1
1
001
0
0
0
2
010
1
0
0
3
011
0
0
0
4
100
1
0
0
5
101
0
0
1
6
110
X
X
X
7
111
X
X
X
x(t)
C1
C2
CLK
S(t)
Mealy Machine
y(t)
25
State Diagram => State Table => Excitation Table => Circuit
id Q1Q0x
0
000
D1
0
D0
1
Q0
y D1(t):
0
0
1
001
0
0
0
2
010
1
0
0
3
011
0
0
0
4
100
1
0
0
5
101
0
0
1
6
110
X
X
X
7
111
X
X
X
0
1
x(t)
2
1
3
0
6
4
X
7
0
1
5
X
0
Q1
D1(t) = x’Q0 + x’Q1
D0 (t)= Q’1Q’0 x’
y= Q1x
26
State Diagram => State Table => Excitation Table => Circuit
Q’1
Q’0
x’
x’
Q0
D0
Q
D
D1
Q1
y
Q
D
Q0
Q1
Q’
Q’
x
x(t)
D1(t) = x’Q0 + x’Q1
D0 (t)= Q’1Q’0 x’
y= Q1x
C1
C2
CLK
y(t)
S(t)
Mealy Machine
27
Moore FSM for the Mars Life
Recognizer
Which of the following diagrams is a correct Moore solution to the ‘001’
pattern recognizer?
1/1
A.
1/0
0/0
S0
B.
1/0
0
1
C. Both A and B are correct
D. None of the above
S2
0/0
1
1
S0
0
0/0
S1
S1
0
0
0
1
S2
0
S3
1
0
28
Moore Mars Life Recognizer:
FF Input Specs
Pattern Recognizer ‘001’
x(t)
1
1
S0
0
0
S1
0
C1
C2
y(t)
0
0
1
S2
0
S3
1
CLK
S(t)
1
0
Moore Machine
What does state table need to show to design controls of C2?
A.(current input x(t), current state S(t) vs. next state, S(t+1))
B.(current input, current state vs. current output y(t))
C.(current state vs. current output y(t) and next state)
D.(current state vs. current output y(t) )
E. None
of the above
29
Moore Mars Life Recognizer:
State Table
1
1
S0
0
0
0
0
S1
0
1
1
S2
0
0
S3
1
ID Q1Q0x
D1 D0
y
000
0
1
0
1
001
0
0
0
2
010
1
0
0
3
011
0
0
0
4
100
1
0
0
00,0
5
101
1
1
0
10,0
11,0
6
110
0
1
1
01,1
00,1
7
111
0
0
1
S(t)\x
0
1
S0
S1,0
S0,0
0
S1
S2,0
S0,0
S2
S2,0
S3,0
S3
S1,1
S0,1
Q1Q0\x
0
1
00
01,0
00,0
01
10,0
10
11
Q1(t+1)Q0(t+1), y
Mars Life Recognizer:
Combinational Circuit Design
Q0
D1(t):
0
0
1
id Q1Q0x
D1
D0
y
000
0
1
0
0
1
001
0
0
0
2
010
1
0
0
3
011
0
0
0
4
100
1
0
0
5
101
1
1
0
6
110
0
1
1
7
111
0
0
1
2
6
1
3
7
0
x(t)
0
4
1
5
0
0
1
Q1
Q0
D0(t):
0
1
1
2
0
3
1
7
0
x(t)
6
4
0
5
0
0
1
Q1
Q0
y(t):
0
0
1
x(t)
2
0
3
0
6
1
7
0
4
0
5
1
0
Q1
Mars Life Recognizer Circuit
Implementation
State Diagram => State Table => Excitation Table => Circuit
Q0
D0
D
D1
D1(t)= Q1(t)Q0(t)’+Q1(t)’Q0(t) x(t)
D0(t)= Q1(t)’Q0(t)’x(t)’+
Q1(t)Q0(t) x(t)’+Q1(t)Q0(t)’ x(t)
y(t)= Q1(t)Q0(t)
Q’
Q1
Q
D
x(t)
y
Q
Q’
C1
C2
y(t)
CLK
S(t)
Moore Machine
32
FSM Specification
x(t)
Q
D
Q0(t)
Q1(t)
Q’
Q
D
Q’
Q0(t)
Q1(t)
y(t)
CLK
33
Finite State Machine Example
• Traffic light controller
– Traffic sensors: TA, TB (TRUE when there’s traffic)
– Lights: LA, LB
Bravado
LA
Academic
TA
LB
LA
TA
TB
LB
Blvd.
Labs
TB
Dining
Hall
Fields
Ave.
Dorms
34
FSM Black Box
• Inputs: CLK, Reset, TA, TB
• Outputs: LA, LB
CLK
TA
TB
Traffic
Light
Controller
LA
LB
Reset
35
FSM State Transition Diagram
Reset
Academic
Labs
LA
TB
TA
Dining
Hall
LB
LA
TA
TB
LB
Blvd.
S0
LA: green
LB: red
Bravado
• Moore FSM: outputs labeled in each state
• States: Circles
• Transitions: Arcs
Fields
Ave.
Dorms
36
FSM State Transition Diagram
Bravado
• Moore FSM: outputs labeled in each state
LA
Academic
TA
TA
Which of the following is true about
the controller?
A. The traffic light on Academic Ave
(LA) remains green as long as
there is traffic on that street
B. The traffic light on both avenues
are green for exactly once clock
cycle in every four clock cycles
S0
LA: green
LB: red
S3
LA: red
LB: yellow
TA
LB
LA
TA
TB
LB
Blvd.
Labs
Reset
TB
Dining
Hall
Fields
Ave.
Dorms
S1
LA: yellow
LB: red
S2
LA: red
LB: green
TB
TB
37
FSM State Transition Table
TA
Reset
S0
LA: green
LB: red
S3
LA: red
LB: yellow
PS
TA
S1
LA: yellow
LB: red
S2
LA: red
LB: green
TB
TB
Inputs
NS
TA
TB
S0
0
X
S1
S0
1
X
S0
S1
X
X
S2
S2
X
0
S3
S2
X
1
S2
S3
X
X
S0
Output
LA
LB
38
FSM State Transition Table
PS
TA
Reset
S0
LA: green
LB: red
S3
LA: red
LB: yellow
TA
S1
LA: yellow
LB: red
S2
LA: red
LB: green
TB
TB
Inputs
TA
TB
S0
0
X
S0
1
S1
Encoding
Output
LA
LB
S1
green
red
X
S0
green
red
X
X
S2
yellow
red
S2
X
0
S3
red
green
S2
X
1
S2
red
green
S3
X
X
S0
red
yellow
PS
State
NS
Inputs
NS
Q1(t)
Q0(t)
TA
TB
Q1(t +1)
Q0(t +1)
0
0
0
X
0
1
0
0
1
X
0
0
S0
00
S1
01
0
1
X
X
1
0
S2
10
1
0
X
0
1
1
1
0
X
1
1
0
1
1
X
X
0
0
S3
11
39
State Transition Table
PS
Q1(t) Q0(t)
0
0
0
0
0
1
1
0
1
0
1
1
Inputs
TA TB
0
X
1
X
X
X
X
0
X
1
X
X
NS
Q1(t +1) Q0(t +1)
0
1
0
0
1
0
1
1
1
0
0
0
Q1(t+1)= Q1(t)  Q0(t)
Q0(t+1)= Q’1(t)Q’0(t)T’A + Q1(t)Q’0(t)T’B
40
FSM Schematic: State Register
CLK
S’1
S1
S’0
S0
r
Reset
state register
41
Logic Diagram
CLK
TA
S’1
S1
S’0
S0
S1=Q1
S0=Q0
r
TB
Reset
S1
inputs
S0
next state logic
state register
Q1(t+1)= Q1(t)  Q0(t)
Q0(t+1)= Q’1(t)Q’0(t)T’A + Q1(t)Q’0(t)T’B
42
FSM Output Table
PS
Inputs
NS
TA
TB
S0
0
X
S0
1
S1
Output
LA
LB
S1
green
red
X
S0
green
red
X
X
S2
yellow
red
S2
X
0
S3
red
green
S2
X
1
S2
red
green
S3
X
X
S0
red
yellow
PS
Output
Encoding
green
00
yellow
01
red
10
Outputs
Q1
Q0
LA1
LA0
LB1
LB0
0
0
0
0
1
0
0
1
0
1
1
0
1
0
1
0
0
0
1
1
1
0
0
1
Current state determines the output
LA1 = Q1
LA0 = Q’1Q0
LB1 = Q’1
LB0 = Q1Q0
43
FSM Schematic: Output Logic
CLK
S’1
LA1
S1
LA0
TA
S’0
S0
LB1
r
TB
Reset
S1
inputs
S0
LB0
next state logic
state register
LA1 = Q1
LA0 = Q’1Q0
LB1 = Q’1
LB0 = Q1Q0
output logic
outputs
44
Moore vs Mealy
45
Moore vs Mealy
•
Moore machine: A vending
machine. The vending machine’s
output (e.g.,dispensing a soda)
depends on its current state
(e.g., whether it has received
enough money for the selected
soda). The vending machine’s
output does not depend on the
current input (e.g., the button that
is pressed).
•
Mealy machine: A traffic light. The traffic
light’s output (e.g., turning green)
depends on its current state
(e.g., whether it is currently
red, yellow, or green) and the current
input (e.g., whether the car sensor is
triggered).
46
Summary: Implementation
• Set up canonical form
• Mealy or Moore machine
• Identify the next states
• state diagram ⇨ state table
• state assignment
• Derive excitation table
• Inputs of flip flops
• Design the combinational logic
• don’t care set utilization
47
Sequential Networks:
Latches and flip flops
1
Flight attendant call button
•
Flight attendant call button
–
Ca l l
button
Press call: light turns on
•
–
–
Bl ue light
Bi t
Stora ge
Ca ncel
button
Stays on after button released
Press cancel: light turns off
Logic gate circuit to implement this?
1. Call button pressed – light turns on
Bl ue light
Ca l l
button
•
SR latch implementation
–
–
C all
button
Bi t
Stora ge
Ca ncel
button
Call=1 : sets Q to 1 and keeps it at 1
Cancel=1 : resets Q to 0
2. Call button released – light stays
on
Ca l l
button
S
Bl ue light
Bi t
Stora ge
Ca ncel
button
Bl ue light
Cancel
button
Q
R
a
3. Cancel button pressed – light turns
off
2
SR (Set/Reset) Latch
• SR Latch
R
S
• Consider the four possible cases:
▪
▪
▪
▪
N1
Q
N2
Q
(S+Q)’
S = 1, R = 0: set output to ‘1’
S = 0, R = 1: (reset) output to ‘0’
S = 0, R = 0: store – output should be unchanged
S = 1, R = 1: Trouble!
3
SR Latch Analysis
▪ S = 1, R = 0:
R
S
0
1
N1
Q
N2
Q
N1
Q
N2
Q
▪ S = 0, R = 1:
R
S
1
0
4
SR Latch Analysis
▪ S = 0, R = 0:
R
S
N1
Q
N2
Q
5
SR Latch Analysis
▪ S = 0, R = 0:
R
S
N1
Q
N2
Q
What happens if Qprev=0 and Q’prev=0?
A.The output Q toggles
B.The output Q remains 0 and Q’ changes to 1
C.The output Q becomes 1 and Q’ remains 0
6
SR Latch Analysis
– S = 1, R = 1:
R
S
1
1
N1
Q
N2
Q
7
SR Latch Analysis
– S = 0, R = 0: then Q = Qprev and Q = Qprev (memory!)
Qprev = 0
R
0
N1
Qprev = 1
0
Q
R
1
S
0
0
0
N1
1
Q
0
N2
1
Q
S
1
0
N2
0
Q
– S = 1, R = 1: then Q = 0 and Q = 0 (invalid state: Q ≠ NOT Q)
R
1
N1
0
Q
0
S
0
1
N2
0
Q
8
SR Latch Symbol
• SR stands for Set/Reset Latch
– Stores one bit of state (Q)
• Control what value is being stored with S, R inputs
– Set: Make the output 1 (S = 1, R = 0, Q = 1)
– Reset: Make the output 0 (S = 0, R = 1, Q = 0)
Must do something to avoid invalid state (S = R = 1)
9
Clocks
Sources: TSR, Katz, Boriello, Vahid,
Rosing
10
Clock question
The clock shown in the waveform
below has:
1
n
s
A. Clock period of 4ns with 250MHz frequency
B. Clock duty cycle 75%
C. Clock period of 1ns with 1GHz frequency
D. A. & B.
E. None of the above
11
C
L
K
D Latch
•
•
•
Two inputs: CLK, D
– CLK: controls when the output changes
– D (the data input): controls what the output changes to
Function
– When CLK = 1, D passes through to Q (the latch is transparent)
– When CLK = 0, Q holds its previous value (the latch is opaque)
Avoids invalid case when Q ≠ NOT Q
D Latch
Symbol
CLK
D
Q
Q
12
D Latch Internal Circuit
CLK
R
D
R
Q
CLK
Q
D
S
D
CLK
0
1
1
D
X
0
1
D
X
1
0
S
0
0
1
S
Q
R
0
1
0
Q
Q
Q
Q
Q
Qprev Qprev
0
1
1
0
13
•
•
•
D Flip-Flop
Two inputs: CLK, D
Function
– The flip-flop “samples” D on the rising edge of CLK
• When CLK rises from 0 to 1, D passes through to Q
• Otherwise, Q holds its previous value
– Q changes only on the rising edge of CLK
A flip-flop is an edge-triggered device because it is activated on the clock edge
(when CLK rises from 0 1)
– D passes through to Q
D Flip-Flop
Symbols
D
Q
Q
14
D Flip-Flop Internal
Circuit
•
•
CLK
CLK
D
D
Q
L1
Q
When CLK = 0
– L1 is transparent, L2 is opaque
– D passes through to N1
When CLK = 1
– L2 is transparent, L1 is opaque
– N1 passes through to Q
CLK
N1
D
Q
Q
L2
Q
Q
15
Latch and Flip-flop (two latches)
CLK
A latch can be considered as a
door
CLK
D
CLK = 0, door is
shut
A flip-flop is a two door
entrance
CLK =
1
D
Q
L1
Q
CLK
N1
D
Q
Q
L2
Q
Q
CLK = 1, door is
unlocked
CLK =
0
CLK =
1
16
D Flip-Flop vs. D Latch
CLK
D
Q
Q
D
Q
Q
CLK
D
Q (latch)
Q (flop)
17
D Flip-Flop vs. D Latch
CLK
D
Q
Q
D
Q
Q
CLK
D
Q (latch)
Q (flop)
18
Rising vs. Falling Edge D
Flip-Flop
D
The triangle
means clock
input, edge
triggered
Q’
D
Q
Q
Symbol for risingedge
triggered D flipflop
Internal design:
Just invert servant
clock rather than
master
falling edges
rising edges
Clk
Q’
Clk
Symbol for fallingedge
triggered D19 flipflop
Enabled D-FFs
• Inputs: CLK, D, EN
– The enable input (EN) controls when new data (D) is stored
• Function
– EN = 1: D passes through to Q on the clock edge
– EN = 0: the flip-flop retains its previous state
Internal
Circuit
EN
Symbol
CLK
0
D
D
1
Q
Q
D
Q
EN
21
Bit Storage Overview
S (set)
SR latch
Q
R (reset)
S=1 s ets Q to 1, R=1
res ets Q to 0.
Probl em: SR=11
yi el d undefined Q.
Level-sensitive SR latch
S
S1
D
C
C
R
D latch
S
Q
R1
S a nd R only have effect
when C=1. We ca n design
outs ide ci rcuit s o SR=11
never ha ppens when C=1.
Probl em: a voiding SR=11
ca n be a burden.
D flip-flop
D
Q
R
SR ca n’t be 11 i f D i s stable
before a nd while C=1, a nd
wi l l be 11 for only a brief
gl i tch even i f D changes while
C=1. Probl em: C=1 too l ong
propa gates new va lues
through too many latches:
too s hort may not enable a
s tore.
Clk
D latch
D latch
Dm Qm
Ds Qs’
Cm
master
Cs Qs
servant
Q’
Q
Onl y l oads D va lue present a t
ri s ing cl ock edge, s o va lues can’t
propa gate to other fl ip-flops
duri ng same cl ock cycl e. Tradeoff:
us es more gates i nternally than D
l a tch, and requires more external
ga tes than SR – but gate count is
l ess of an i ssue today.
22
23
Shift register
• Holds & shifts samples of input
OUT1
IN
D Q
D Q
OUT2
D Q
OUT3
OUT4
D Q
CLK
24
Pattern Recognizer
• Combinational function of input
samples
OUT
OUT1
IN
D Q
D Q
OUT2
D Q
OUT3
OUT4
D Q
CLK
25
Counters
•Sequences through a fixed set of patterns
OUT1
IN
D Q
D Q
OUT2
D Q
OUT3
OUT4
D Q
CLK
26
Logic and
Computer
Design
Fundamentals
Fifth Edition
M. Morris Mano
California State University, Los Angeles
Charles R. Kime
University of Wisconsin, Madison
Tom Martin
Virginia Tech
Boston Columbus Indianapolis New York San Francisco Hoboken
Amsterdam Cape Town Dubai London Madrid Milan Munich Paris Montreal Toronto
Delhi Mexico City São Paulo Sydney Hong Kong Seoul Singapore Taipei Tokyo
Vice President and Editorial Director, ECS: Marcia J.
Horton
Acquisitions Editor: Julie Bai
Executive Marketing Manager: Tim Galligan
Marketing Assistant: Jon Bryant
Senior Managing Editor: Scott Disanno
Production Project Manager: Greg Dulles
Program Manager: Joanne Manning
Global HE Director of Vendor Sourcing and
Procurement: Diane Hynes
Director of Operations: Nick Sklitsis
Operations Specialist: Maura Zaldivar-Garcia
Cover Designer: Black Horse Designs
Manager, Rights and Permissions: Rachel Youdelman
Associate Project Manager, Rights and Permissions:
Timothy Nicholls
Full-Service Project Management: Shylaja Gattupalli,
Jouve India
Composition: Jouve India
Printer/Binder: Edwards Brothers
Cover Printer: Phoenix Color/Hagerstown
Typeface: 10/12 Times Ten LT Std
Copyright © 2015, 2008, 2004 by Pearson Higher Education, Inc., Hoboken, NJ 07030. All rights reserved. Manufactured
in the United States of America. This publication is protected by Copyright and permissions should be obtained from the
publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means,
electronic, mechanical, photocopying, recording, or likewise. To obtain permission(s) to use materials from this work, please
submit a written request to Pearson Higher Education, Permissions Department, 221 River Street, Hoboken, NJ 07030.
Many of the designations by manufacturers and seller to distinguish their products are claimed as trademarks. Where
those designations appear in this book, and the publisher was aware of a trademark claim, the designations have
been printed in initial caps or all caps.
The author and publisher of this book have used their best efforts in preparing this book. These efforts include
the development, research, and testing of theories and programs to determine their effectiveness. The author and
publisher make no warranty of any kind, expressed or implied, with regard to these programs or the documentation
contained in this book. The author and publisher shall not be liable in any event for incidental or consequential
damages with, or arising out of, the furnishing, performance, or use of these programs.
Library of Congress Cataloging-in-Publication Data
Mano, M. Morris, 1927Logic and computer design fundamentals / Morris Mano, California State University, Los Angeles;
Charles R. Kime, University of Wisconsin, Madison; Tom Martin, Blacksburg, Virginia. — Fifth Edition.
pages cm
ISBN 978-0-13-376063-7 — ISBN 0-13-376063-4
1. Electronic digital computers—Circuits. 2. Logic circuits. 3. Logic design. I. Kime, Charles R.
II. Martin, Tom, 1969- III. Title.
TK7888.4.M36 2014
621.39’2—dc23
2014047146
10 9 8 7 6 5 4 3 2 1
ISBN-10: 0-13-376063-4
ISBN-13: 978-0-13-376063-7
Contents
Preface
Chapter 1
xii
3
Digital Systems and Information
3
1-1
4
6
7
10
12
14
15
17
18
20
20
23
25
26
26
29
30
32
33
33
1-2
1-3
1-4
1-5
1-6
1-7
1-8
Chapter 2
Information Representation
The Digital Computer
Beyond the Computer
More on the Generic Computer
Abstraction Layers in Computer Systems Design
An Overview of the Digital Design Process
Number Systems
Binary Numbers
Octal and Hexadecimal Numbers
Number Ranges
Arithmetic Operations
Conversion from Decimal to Other Bases
Decimal Codes
Alphanumeric Codes
ASCII Character Code
Parity Bit
Gray Codes
Chapter Summary
References
Problems
37
Combinational Logic Circuits
37
2-1
38
38
40
44
Binary Logic and Gates
Binary Logic
Logic Gates
HDL Representations of Gates
iii
iv
Contents
2-2
2-3
2-4
2-5
2-6
2-7
2-8
2-9
2-10
2-11
Chapter 3
Boolean Algebra
Basic Identities of Boolean Algebra
Algebraic Manipulation
Complement of a Function
Standard Forms
Minterms and Maxterms
Sum of Products
Product of Sums
Two-Level Circuit Optimization
Cost Criteria
Map Structures
Two-Variable Maps
Three-Variable Maps
Map Manipulation
Essential Prime Implicants
Nonessential Prime Implicants
Product-of-Sums Optimization
Don’t-Care Conditions
Exclusive-Or Operator and Gates
Odd Function
Gate Propagation Delay
HDLs Overview
Logic Synthesis
HDL Representations—VHDL
HDL Representations—Verilog
Chapter Summary
References
Problems
45
49
51
54
55
55
59
60
61
61
63
65
67
71
71
73
74
75
78
78
80
82
84
86
94
101
102
102
113
Combinational Logic Design
113
3-1
3-2
3-3
3-4
114
118
122
122
123
123
126
128
132
135
137
138
139
3-5
3-6
Beginning Hierarchical Design
Technology Mapping
Combinational Functional Blocks
Rudimentary Logic Functions
Value-Fixing, Transferring, and Inverting
Multiple-Bit Functions
Enabling
Decoding
Decoder and Enabling Combinations
Decoder-Based Combinational Circuits
Encoding
Priority Encoder
Encoder Expansion
Contents
3-7
3-8
3-9
3-10
3-11
3-12
3-13
Chapter 4
Selecting
Multiplexers
Multiplexer-Based Combinational Circuits
Iterative Combinational Circuits
Binary Adders
Half Adder
Full Adder
Binary Ripple Carry Adder
Binary Subtraction
Complements
Subtraction Using 2s Complement
Binary Adder-Subtractors
Signed Binary Numbers
Signed Binary Addition and Subtraction
Overlow
HDL Models of Adders
Behavioral Description
Other Arithmetic Functions
Contraction
Incrementing
Decrementing
Multiplication by Constants
Division by Constants
Zero Fill and Extension
Chapter Summary
References
Problems
v
140
140
150
155
157
157
158
159
161
162
164
165
166
168
170
172
174
177
178
179
180
180
182
182
183
183
184
197
Sequential Circuits
197
4-1
4-2
198
201
201
204
204
206
207
209
210
210
211
213
216
218
4-3
4-4
4-5
Sequential Circuit Deinitions
Latches
SR and SR Latches
D Latch
Flip-Flops
Edge-Triggered Flip-Flop
Standard Graphics Symbols
Direct Inputs
Sequential Circuit Analysis
Input Equations
State Table
State Diagram
Sequential Circuit Simulation
Sequential Circuit Design
vi
Contents
4-6
4-7
4-8
4-9
4-10
4-11
4-12
4-13
4-14
Chapter 5
Design Procedure
Finding State Diagrams and State Tables
State Assignment
Designing with D Flip-Flops
Designing with Unused States
Veriication
State-Machine Diagrams and Applications
State-Machine Diagram Model
Constraints on Input Conditions
Design Applications Using State-Machine Diagrams
HDL Representation for Sequential Circuits—VHDL
HDL Representation for Sequential Circuits—Verilog
Flip-Flop Timing
Sequential Circuit Timing
Asynchronous Interactions
Synchronization and Metastability
Synchronous Circuit Pitfalls
Chapter Summary
References
Problems
218
219
226
227
230
232
234
236
238
240
248
257
266
267
270
271
277
278
279
280
295
Digital Hardware Implementation
295
5-1
295
295
296
302
304
306
308
311
313
318
318
318
5-2
5-3
Chapter 6
The Design Space
Integrated Circuits
CMOS Circuit Technology
Technology Parameters
Programmable Implementation Technologies
Read-Only Memory
Programmable Logic Array
Programmable Array Logic Devices
Field Programmable Gate Array
Chapter Summary
References
Problems
323
Registers and Register Transfers
323
6-1
324
325
327
329
331
6-2
6-3
6-4
Registers and Load Enable
Register with Parallel Load
Register Transfers
Register Transfer Operations
Register Transfers in VHDL and Verilog
Contents
6-5
6-6
6-7
6-8
6-9
6-10
6-11
6-12
6-13
6-14
Chapter 7
Microoperations
Arithmetic Microoperations
Logic Microoperations
Shift Microoperations
Microoperations on a Single Register
Multiplexer-Based Transfers
Shift Registers
Ripple Counter
Synchronous Binary Counters
Other Counters
Register-Cell Design
Multiplexer and Bus-Based Transfers for
Multiple Registers
High-Impedance Outputs
Three-State Bus
Serial Transfer and Microoperations
Serial Addition
Control of Register Transfers
Design Procedure
HDL Representation for Shift Registers
and Counters—VHDL
HDL Representation for Shift Registers
and Counters—Verilog
Microprogrammed Control
Chapter Summary
References
Problems
vii
332
333
335
337
337
338
340
345
347
351
354
359
361
363
364
365
367
368
384
386
388
390
391
391
403
Memory Basics
403
7-1
7-2
403
404
406
407
409
409
411
415
418
419
420
424
426
428
7-3
7-4
7-5
7-6
Memory Deinitions
Random-Access Memory
Write and Read Operations
Timing Waveforms
Properties of Memory
SRAM Integrated Circuits
Coincident Selection
Array of SRAM ICs
DRAM ICs
DRAM Cell
DRAM Bit Slice
DRAM Types
Synchronous DRAM (SDRAM)
Double-Data-Rate SDRAM (DDR SDRAM)
viii
Contents
7-7
7-8
Chapter 8
RAMBUS® DRAM (RDRAM)
Arrays of Dynamic RAM ICs
Chapter Summary
References
Problems
429
430
430
431
431
433
Computer Design Basics
433
8-1
8-2
8-3
434
434
437
437
440
442
443
444
445
447
453
453
454
455
457
460
461
463
466
467
471
476
478
478
8-4
8-5
8-6
8-7
8-8
8-9
8-10
Chapter 9
Introduction
Datapaths
The Arithmetic/Logic Unit
Arithmetic Circuit
Logic Circuit
Arithmetic/Logic Unit
The Shifter
Barrel Shifter
Datapath Representation
The Control Word
A Simple Computer Architecture
Instruction Set Architecture
Storage Resources
Instruction Formats
Instruction Speciications
Single-Cycle Hardwired Control
Instruction Decoder
Sample Instructions and Program
Single-Cycle Computer Issues
Multiple-Cycle Hardwired Control
Sequential Control Design
Chapter Summary
References
Problems
485
Instruction Set Architecture
485
9-1
485
487
487
488
489
489
490
9-2
Computer Architecture Concepts
Basic Computer Operation Cycle
Register Set
Operand Addressing
Three-Address Instructions
Two-Address Instructions
One-Address Instructions
Contents
9-3
9-4
9-5
9-6
9-7
9-8
9-9
9-10
Chapter 10
Zero-Address Instructions
Addressing Architectures
Addressing Modes
Implied Mode
Immediate Mode
Register and Register-Indirect Modes
Direct Addressing Mode
Indirect Addressing Mode
Relative Addressing Mode
Indexed Addressing Mode
Summary of Addressing Modes
Instruction Set Architectures
Data-Transfer Instructions
Stack Instructions
Independent versus Memory-Mapped I/O
Data-Manipulation Instructions
Arithmetic Instructions
Logical and Bit-Manipulation Instructions
Shift Instructions
Floating-Point Computations
Arithmetic Operations
Biased Exponent
Standard Operand Format
Program Control Instructions
Conditional Branch Instructions
Procedure Call and Return Instructions
Program Interrupt
Types of Interrupts
Processing External Interrupts
Chapter Summary
References
Problems
ix
490
491
494
495
495
496
496
497
498
499
500
501
502
502
504
505
505
506
508
509
510
511
512
514
515
517
519
520
521
522
523
523
531
Risc and Cisc Central Processing Units
531
10-1
532
536
537
539
541
541
544
545
548
10-2
10-3
Pipelined Datapath
Execution of Pipeline Microoperations
Pipelined Control
Pipeline Programming and Performance
The Reduced Instruction Set Computer
Instruction Set Architecture
Addressing Modes
Datapath Organization
Control Organization
x
Contents
10-4
10-5
10-6
Chapter 11
Data Hazards
Control Hazards
The Complex Instruction Set Computer
ISA Modiications
Datapath Modiications
Control Unit Modiications
Microprogrammed Control
Microprograms for Complex Instructions
More on Design
Advanced CPU Concepts
Recent Architectural Innovations
Chapter Summary
References
Problems
550
557
561
563
564
566
567
569
572
573
576
579
580
581
585
Input—Output and Communication
585
11-1
11-2
585
586
586
587
589
592
592
593
594
595
597
598
599
600
601
604
605
606
608
608
610
611
612
614
615
615
616
11-3
11-4
11-5
11-6
11-7
11-8
Computer I/O
Sample Peripherals
Keyboard
Hard Drive
Liquid Crystal Display Screen
I/O Transfer Rates
I/O Interfaces
I/O Bus and Interface Unit
Example of I/O Interface
Strobing
Handshaking
Serial Communication
Synchronous Transmission
The Keyboard Revisited
A Packet-Based Serial I/O Bus
Modes of Transfer
Example of Program-Controlled Transfer
Interrupt-Initiated Transfer
Priority Interrupt
Daisy Chain Priority
Parallel Priority Hardware
Direct Memory Access
DMA Controller
DMA Transfer
Chapter Summary
References
Problems
Contents
Chapter 12
xi
619
Memory Systems
619
12-1
12-2
12-3
619
622
624
626
631
632
633
634
636
637
637
639
641
643
643
644
644
12-4
12-5
Index
Memory Hierarchy
Locality of Reference
Cache Memory
Cache Mappings
Line Size
Cache Loading
Write Methods
Integration of Concepts
Instruction and Data Caches
Multiple-Level Caches
Virtual Memory
Page Tables
Translation Lookaside Buffer
Virtual Memory and Cache
Chapter Summary
References
Problems
648
Preface
The objective of this text is to serve as a cornerstone for the learning of logic design,
digital system design, and computer design by a broad audience of readers. This ifth
edition marks the continued evolution of the text contents. Beginning as an adaptation of a previous book by the irst author in 1997, it continues to offer a unique
combination of logic design and computer design principles with a strong hardware
emphasis. Over the years, the text has followed industry trends by adding new material such as hardware description languages, removing or de-emphasizing material of
declining importance, and revising material to track changes in computer technology
and computer-aided design.
New to this editioN
The ifth edition relects changes in technology and design practice that require computer system designers to work at higher levels of abstraction and manage larger
ranges of complexity than they have in the past. The level of abstraction at which
logic, digital systems, and computers are designed has moved well beyond the level
at which these topics are typically taught. The goal in updating the text is to more
effectively bridge the gap between existing pedagogy and practice in the design of
computer systems, particularly at the logic level. At the same time, the new edition
maintains an organization that should permit instructors to tailor the degree of technology coverage to suit both electrical and computer engineering and computer science audiences. The primary changes to this edition include:
• Chapter 1 has been updated to include a discussion of the layers of abstractions
in computing systems and their role in digital design, as well as an overview of
the digital design process. Chapter 1 also has new material on alphanumeric
codes for internationalization.
• The textbook introduces hardware description languages (HDLs) earlier, starting in Chapter 2. HDL descriptions of circuits are presented alongside logic schematics and state diagrams throughout the chapters on combinational and
sequential logic design to indicate the growing importance of HDLs in contemporary digital system design practice. The material on propagation delay, which is
a irst-order design constraint in digital systems, has been moved into Chapter 2.
• Chapter 3 combines the functional block material from the old Chapter 3 and
the arithmetic blocks from the old Chapter 4 to present a set of commonly
xii
Preface
xiii
occurring combinational logic functional blocks. HDL models of the functional blocks are presented throughout the chapter. Chapter 3 introduces the
concept of hierarchical design.
• Sequential circuits appear in Chapter 4, which includes both the description of
design processes from the old Chapter 5, and the material on sequential circuit
timing, synchronization of inputs, and metastability from the old Chapter 6.
The description of JK and T lip-lops has been removed from the textbook
and moved to the online Companion Website.
• Chapter 5 describes topics related to the implementation of digital hardware,
including design of complementary metal-oxide (CMOS) gates and programmable logic. In addition to much of the material from the old Chapter 6,
Chapter 5 now includes a brief discussion of the effect of testing and veriication on the cost of a design. Since many courses employing this text have lab
exercises based upon ield programmable gate arrays (FPGAs), the description of FPGAs has been expanded, using a simple, generic FPGA architecture
to explain the basic programmable elements that appear in many commercially available FPGA families.
• The remaining chapters, which cover computer design, have been updated to
relect changes in the state-of-the art since the previous edition appeared.
Notable changes include moving the material on high-impedance buffers from
the old Chapter 2 to the bus transfer section of Chapter 6 and adding a discussion of how procedure call and return instructions can be used to implement
function calls in high level languages in Chapter 9.
Offering integrated coverage of both digital and computer design, this edition
of Logic and Computer Design Fundamentals features a strong emphasis on fundamentals underlying contemporary design. Understanding of the material is supported by clear explanations and a progressive development of examples ranging
from simple combinational applications to a CISC architecture built upon a RISC
core. A thorough coverage of traditional topics is combined with attention to computer-aided design, problem formulation, solution veriication, and the building of
problem-solving skills. Flexibility is provided for selective coverage of logic design,
digital system design, and computer design topics, and for coverage of hardware
description languages (none, VHDL, or Verilog®).
With these revisions, Chapters 1 through 4 of the book treat logic design,
Chapters 5 through 7 deal with digital systems design, and Chapters 8 through 12
focus on computer design. This arrangement provides solid digital system design
fundamentals while accomplishing a gradual, bottom-up development of fundamentals for use in top-down computer design in later chapters. Summaries of the
topics covered in each chapter follow.
Logic Design
Chapter 1, Digital Systems and Information, introduces digital computers, computer systems abstraction layers, embedded systems, and information representation
including number systems, arithmetic, and codes.
xiv
Preface
Chapter 2, Combinational Logic Circuits, deals with gate circuits and their
types and basic ideas for their design and cost optimization. Concepts include Boolean algebra, algebraic and Karnaugh-map optimization, propagation delay, and gatelevel hardware description language models using structural and datalow models in
both VHDL and Verilog.
Chapter 3, Combinational Logic Design, begins with an overview of a contemporary logic design process. The details of steps of the design process including
problem formulation, logic optimization, technology mapping to NAND and NOR
gates, and veriication are covered for combinational logic design examples. In addition, the chapter covers the functions and building blocks of combinational design
including enabling and input-ixing, decoding, encoding, code conversion, selecting,
distributing, addition, subtraction, incrementing, decrementing, illing, extension and
shifting, and their implementations. The chapter includes VHDL and Verilog models
for many of the logic blocks.
Chapter 4, Sequential Circuits, covers sequential circuit analysis and design.
Latches and edge-triggered lip-lops are covered with emphasis on the D type.
Emphasis is placed on state machine diagram and state table formulation. A complete design process for sequential circuits including speciication, formulation, state
assignment, lip-lop input and output equation determination, optimization, technology mapping, and veriication is developed. A graphical state machine diagram model
that represents sequential circuits too complex to model with a conventional state
diagram is presented and illustrated by two real world examples. The chapter includes
VHDL and Verilog descriptions of a lip-lop and a sequential circuit, introducing
procedural behavioral VHDL and Verilog language constructs as well as test benches
for veriication. The chapter concludes by presenting delay and timing for sequential
circuits, as well as synchronization of asynchronous inputs and metastability.
Digital Systems Design
Chapter 5, Digital Hardware Implementation, presents topics focusing on various
aspects of underlying technology including the MOS transistor and CMOS circuits,
and programmable logic technologies. Programmable logic covers read-only memories, programmable logic arrays, programmable array logic, and ield programmable
gate arrays (FPGAs). The chapter includes examples using a simple FPGA architecture to illustrate many of the programmable elements that appear in more complex,
commercially available FPGA hardware.
Chapter 6, Registers and Register Transfers, covers registers and their applications. Shift register and counter design are based on the combination of lip-lops
with functions and implementations introduced in Chapters 3 and 4. Only the ripple
counter is introduced as a totally new concept. Register transfers are considered
for both parallel and serial designs and time–space trade-offs are discussed. A section focuses on register cell design for multifunction registers that perform multiple
operations. A process for the integrated design of datapaths and control units using
register transfer statements and state machine diagrams is introduced and illustrated
by two real world examples. Verilog and VHDL descriptions of selected register
types are introduced.
Preface
xv
Chapter 7, Memory Basics, introduces static random access memory (SRAM)
and dynamic random access memory (DRAM), and basic memory systems. It also
describes briely various distinct types of DRAMs.
Computer design
Chapter 8, Computer Design Basics, covers register iles, function units, datapaths,
and two simple computers: a single-cycle computer and a multiple-cycle computer.
The focus is on datapath and control unit design formulation concepts applied to
implementing speciied instructions and instruction sets in single-cycle and multiplecycle designs.
Chapter 9, Instruction Set Architecture, introduces many facets of instruction set architecture. It deals with address count, addressing modes, architectures,
and the types of instructions and presents loating-point number representation
and operations. Program control architecture is presented including procedure
calls and interrupts.
Chapter 10, RISC and CISC Processors, covers high-performance processor
concepts including a pipelined RISC processor and a CISC processor. The CISC
processor, by using microcoded hardware added to a modiication of the RISC
processor, permits execution of the CISC instruction set using the RISC pipeline,
an approach used in contemporary CISC processors. Also, sections describe highperformance CPU concepts and architecture innovations including two examples
of multiple CPU microprocessors.
Chapter 11, Input–Output and Communication, deals with data transfer
between the CPU and memory, input–output interfaces and peripheral devices. Discussions of a keyboard, a Liquid Crystal Display (LCD) screen, and a hard drive as
peripherals are included, and a keyboard interface is illustrated. Other topics range
from serial communication, including the Universal Serial Bus (USB), to interrupt
system implementation.
Chapter 12, Memory Systems, focuses on memory hierarchies. The concept of
locality of reference is introduced and illustrated by consideration of the cache/main
memory and main memory/hard drive relationships. An overview of cache design
parameters is provided. The treatment of memory management focuses on paging
and a translation lookaside buffer supporting virtual memory.
In addition to the text itself, a Companion Website and an Instructor’s Manual are provided. Companion Website (www.pearsonhighered.com/mano) content
includes the following: 1) reading supplements including material deleted from prior
editions, 2) VHDL and Verilog source iles for all examples, 3) links to computeraided design tools for FPGA design and HDL simulation, 4) solutions for about
one-third of all text chapter problems, 5) errata, 6) PowerPoint® slides for Chapters 1
through 8, 7) projection originals for complex igures and tables from the text, and
8) site news sections for students and instructors pointing out new material, updates,
and corrections. Instructors are encouraged to periodically check the instructor’s site
news so that they are aware of site changes. Instructor’s Manual content includes
suggestions for use of the book and all problem solutions. Online access to this manual is available from Pearson to instructors at academic institutions who adopt the
xvi
Preface
book for classroom use. The suggestions for use provide important detailed information for navigating the text to it with various course syllabi.
Because of its broad coverage of both logic and computer design, this book
serves several different objectives in sophomore through junior level courses. Chapters
1 through 9 with selected sections omitted, provide an overview of hardware for computer science, computer engineering, electrical engineering, or engineering students in
general in a single semester course. Chapters 1 through 4 possibly with selected parts
of 5 through 7 give a basic introduction to logic design, which can be completed in a
single quarter for electrical and computer engineering students. Covering Chapters
1 through 7 in a semester provides a stronger, more contemporary logic design treatment. The entire book, covered in two quarters, provides the basics of logic and computer design for computer engineering and science students. Coverage of the entire
book with appropriate supplementary material or a laboratory component can ill a
two-semester sequence in logic design and computer architecture. Due to its moderately paced treatment of a wide range of topics, the book is ideal for self-study by engineers and computer scientists. Finally, all of these various objectives can also beneit
from use of reading supplements provided on the Companion Website.
The authors would like to acknowledge the instructors whose input contributed
to the previous edition of the text and whose inluence is still apparent in the current
edition, particularly Professor Bharat Bhuva, Vanderbilt University; Professor Donald
Hung, San Jose State University; and Professors Katherine Compton, Mikko Lipasti,
Kewal Saluja, and Leon Shohet, and Faculty Associate Michael Morrow, ECE, University of Wisconsin, Madison. We appreciate corrections to the previous editions provided by both instructors and students, most notably, those from Professor Douglas
De Boer of Dordt College. In getting ready to prepare to think about getting started
to commence planning to begin working on the ifth edition, I received valuable feedback on the fourth edition from Patrick Schaumont and Cameron Patterson at Virginia
Tech, and Mark Smith at the Royal Institute of Technology (KTH) in Stockholm, Sweden. I also beneited from many discussions with Kristie Cooper and Jason Thweatt
at Virginia Tech about using the fourth edition in the updated version of our department’s Introduction to Computer Engineering course. I would also like to express
my appreciation to the folks at Pearson for their hard work on this new edition. In
particular, I would like to thank Andrew Gilillan for choosing me to be the new third
author and for his help in planning the new edition; Julie Bai for her deft handling of
the transition after Andrew moved to another job, and for her guidance, support, and
invaluable feedback on the manuscript; Pavithra Jayapaul for her help in text production and her patience in dealing with my delays (especially in writing this preface!);
and Scott Disanno and Shylaja Gattupalli for their guidance and care in producing the
text. Special thanks go to Morris Mano and Charles Kime for their efforts in writing
the previous editions of this book. It is an honor and a privilege to have been chosen as
their successor. Finally, I would like to thank Karen, Guthrie, and Eli for their patience
and support while I was writing, especially for keeping our mutt Charley away from
this laptop so that he didn’t eat the keys like he did with its short-lived predecessor.
Tom Martin
Blacksburg, Virginia
Logic and
Computer
Design
Fundamentals
LCD
Screen
Hard Drive
Keyboard
Drive Controller
Bus Interface
Graphics Adapter
Internal
FPU Cache
CPU MMU
Processor
RAM
External
Cache
C H A P T E R
1
Digital Systems
and Information
his book deals with logic circuits and digital computers. Early computers were used
for computations with discrete numeric elements called digits (the Latin word for
ingers)—hence the term digital computer. The use of “digital” spread from the
computer to logic circuits and other systems that use discrete elements of information,
giving us the terms digital circuits and digital systems. The term logic is applied to circuits
that operate on a set of just two elements with values True (1) and False (0). Since
computers are based on logic circuits, they operate on patterns of elements from these
two-valued sets, which are used to represent, among other things, the decimal digits.
Today, the term “digital circuits” is viewed as synonymous with the term “logic circuits.”
The general-purpose digital computer is a digital system that can follow a stored
sequence of instructions, called a program, that operates on data. The user can specify
and change the program or the data according to speciic needs. As a result of this
lexibility, general-purpose digital computers can perform a variety of informationprocessing tasks, ranging over a very wide spectrum of applications. This makes the
digital computer a highly general and very lexible digital system. Also, due to its
generality, complexity, and widespread use, the computer provides an ideal vehicle for
learning the concepts, methods, and tools of digital system design. To this end, we use
the exploded pictorial diagram of a computer of the class commonly referred to as a PC
(personal computer) given on the opposite page. We employ this generic computer to
highlight the signiicance of the material covered and its relationship to the overall
system. A bit later in this chapter, we will discuss the various major components of the
generic computer and see how they relate to a block diagram commonly used to
represent a computer. We then describe the concept of layers of abstraction in digital
system design, which enables us to manage the complexity of designing and
programming computers constructed using billions of transistors. Otherwise, the
remainder of the chapter focuses on the digital systems in our daily lives and introduces
approaches for representing information in digital circuits and systems.
T
3
4
CHAPTER 1 / DigiTAl SySTEmS AnD infoRmATion
1-1
iNformatioN represeNtatioN
Digital systems store, move, and process information. The information represents a
broad range of phenomena from the physical and man-made world. The physical
world is characterized by parameters such as weight, temperature, pressure, velocity,
low, and sound intensity and frequency. Most physical parameters are continuous,
typically capable of taking on all possible values over a deined range. In contrast, in
the man-made world, parameters can be discrete in nature, such as business records
using words, quantities, and currencies, taking on values from an alphabet, the integers, or units of currency, respectively. In general, information systems must be able
to represent both continuous and discrete information. Suppose that temperature,
which is continuous, is measured by a sensor and converted to an electrical voltage,
which is likewise continuous. We refer to such a continuous voltage as an analog
signal, which is one possible way to represent temperature. But, it is also possible
to represent temperature by an electrical voltage that takes on discrete values that
occupy only a inite number of values over a range, for example, corresponding to
integer degrees centigrade between -40 and +119. We refer to such a voltage as a
digital signal. Alternatively, we can represent the discrete values by multiple voltage
signals, each taking on a discrete value. At the extreme, each signal can be viewed as
having only two discrete values, with multiple signals representing a large number of
discrete values. For example, each of the 160 values just mentioned for temperature
can be represented by a particular combination of eight two-valued signals. The signals in most present-day electronic digital systems use just two discrete values and
are therefore said to be binary. The two discrete values used are often called 0 and 1,
the digits for the binary number system.
We typically represent the two discrete values by ranges of voltage values
called HIGH and LOW. Output and input voltage ranges are illustrated in
Figure 1-1(a). The HIGH output voltage value ranges between 0.9 and 1.1 volts, and
the LOW output voltage value between -0.1 and 0.1 volts. The high input range
allows 0.6 to 1.1 volts to be recognized as a HIGH, and the low input range allows
OUTPUT
HIGH
Voltage (Volts)
1.0
INPUT
1.0
0.9
HIGH
0.5
Time
0.0
(b) Time-dependent voltage
0.6
0.4
1
LOW
0.1
0.0
Volts
(a) Example voltage ranges
LOW
Time
0
(c) Binary model of time-dependent voltage
FIguRE 1-1
Examples of Voltage Ranges and Waveforms for Binary Signals
1-1 / information Representation
5
-0.1 to 0.4 volts to be recognized as a LOW. The fact that the input ranges are wider
than the output ranges allows the circuits to function correctly in spite of variations
in their behavior and undesirable “noise” voltages that may be added to or subtracted from the outputs.
We give the output and input voltage ranges a number of different names.
Among these are HIGH (H) and LOW (L), TRUE (T) and FALSE (F), and 1 and 0.
It is natural to associate the higher voltage ranges with HIGH or H, and the lower
voltage ranges with LOW or L. For TRUE and 1 and FALSE and 0, however, there is
a choice. TRUE and 1 can be associated with either the higher or lower voltage range
and FALSE and 0 with the other range. Unless otherwise indicated, we assume that
TRUE and 1 are associated with the higher of the voltage ranges, H, and the FALSE
and 0 are associated with the lower of the voltage ranges, L. This particular convention is called positive logic.
It is interesting to note that the values of voltages for a digital circuit in
Figure 1-1(a) are still continuous, ranging from -0.1 to +1.1 volts. Thus, the voltage
is actually analog! The actual voltages values for the output of a very high-speed
digital circuit are plotted versus time in Figure 1-1(b). Such a plot is referred to as a
waveform. The interpretation of the voltage as binary is based on a model using
voltage ranges to represent discrete values 0 and 1 on the inputs and the outputs.
The application of such a model, which redeines all voltage above 0.5 V as 1 and
below 0.5 V as 0 in Figure 1-1(b), gives the waveform in Figure 1-1(c). The output
has now been interpreted as binary, having only discrete values 1 and 0, with the
actual voltage values removed. We note that digital circuits, made up of electronic
devices called transistors, are designed to cause the outputs to occupy the two distinct output voltage ranges for 1 (H) and 0 (L) in Figure 1-1, whenever the outputs
are not changing. In contrast, analog circuits are designed to have their outputs
take on continuous values over their range, whether changing or not.
Since 0 and 1 are associated with the binary number system, they are the preferred names for the signal ranges. A binary digit is called a bit. Information is
represented in digital computers by groups of bits. By using various coding techniques, groups of bits can be made to represent not only binary numbers, but also
other groups of discrete symbols. Groups of bits, properly arranged, can even
specify to the computer the program instructions to be executed and the data to be
processed.
Why is binary used? In contrast to the situation in Figure 1-1, consider a system with 10 values representing the decimal digits. In such a system, the voltages
available—say, 0 to 1.0 volts—could be divided into 10 ranges, each of length
0.1 volt. A circuit would provide an output voltage within each of these 10 ranges.
An input of a circuit would need to determine in which of the 10 ranges an applied
voltage lies. If we wish to allow for noise on the voltages, then output voltage
might be permitted to range over less than 0.05 volt for a given digit representation, and boundaries between inputs could vary by less than 0.05 volt. This would
require complex and costly electronic circuits, and the output still could be disturbed by small “noise” voltages or small variations in the circuits occurring
during their manufacture or use. As a consequence, the use of such multivalued
circuits is very limited. Instead, binary circuits are used in which correct circuit
6
CHAPTER 1 / DigiTAl SySTEmS AnD infoRmATion
operation can be achieved with signiicant variations in values of the two output
voltages and the two input ranges. The resulting transistor circuit with an output
that is either HIGH or LOW is simple, easy to design, and extremely reliable. In
addition, this use of binary values makes the results calculated repeatable in the
sense that the same set of input values to a calculation always gives exactly the
same set of outputs. This is not necessarily the case for multivalued or analog circuits, in which noise voltages and small variations due to manufacture or circuit
aging can cause results to differ at different times.
The Digital Computer
A block diagram of a digital computer is shown in Figure 1-2. The memory stores
programs as well as input, output, and intermediate data. The datapath performs
arithmetic and other data-processing operations as speciied by the program. The
control unit supervises the low of information between the various units. A datapath, when combined with the control unit, forms a component referred to as a central processing unit, or CPU.
The program and data prepared by the user are transferred into memory by
means of an input device such as a keyboard. An output device, such as an LCD (liquid crystal display), displays the results of the computations and presents them to the
user. A digital computer can accommodate many different input and output devices,
such as DVD drives, USB lash drives, scanners, and printers. These devices use digital logic circuits, but often include analog electronic circuits, optical sensors, LCDs,
and electromechanical components.
The control unit in the CPU retrieves the instructions, one by one, from the
program stored in the memory. For each instruction, the control unit manipulates the
datapath to execute the operation speciied by the instruction. Both program and
data are stored in memory. A digital computer can perform arithmetic computations,
manipulate strings of alphabetic characters, and be programmed to make decisions
based on internal and external conditions.
Memory
CPU
Control
Unit
Datapath
Input/Output
FIguRE 1-2
Block Diagram of a Digital Computer
1-1 / information Representation
7
Beyond the Computer
In terms of world impact, computers, such as the PC, are not the end of the story.
Smaller, often less powerful, single-chip computers called microcomputers or microcontrollers, or special-purpose computers called digital signal processors (DSPs)
actually are more prevalent in our lives. These computers are parts of everyday products and their presence is often not apparent. As a consequence of being integral
parts of other products and often enclosed within them, they are called embedded
systems. A generic block diagram of an embedded system is shown in Figure 1-3.
Central to the system is the microcomputer (or its equivalent). It has many of the
characteristics of the PC, but differs in the sense that its software programs are often
permanently stored to provide only the functions required for the product. This software, which is critical to the operation of the product, is an integral part of the embedded system and referred to as embedded software. Also, the human interface of
the microcomputer can be very limited or nonexistent. The larger informationstorage components such as a hard drive and compact disk or DVD drive frequently
are not present. The microcomputer contains some memory; if additional memory is
needed, it can be added externally.
With the exception of the external memory, the hardware connected to the
embedded microcomputer in Figure 1-3 interfaces with the product and/or the outside world. The input devices transform inputs from the product or outside world
into electrical signals, and the output devices transform electrical signals into outputs to the product or outside world. The input and output devices are of two types,
those which use analog signals and those which use digital signals. Examples of digital input devices include a limit switch which is closed or open depending on whether
a force is applied to it and a keypad having ten decimal integer buttons. Examples of
Analog
Input Devices
and Signal
Conditioning
D-to-A
Converters
A-to-D
Converters
Digital
Input Devices
and Signal
Conditioning
Microcomputer,
Microcontroller,
or Digital Signal
Processor
Signal
Conditioning
and Digital
Output Devices
External
Memory
FIguRE 1-3
Block Diagram of an Embedded System
Signal
Conditioning
and Digital
Output Devices
8
CHAPTER 1 / DigiTAl SySTEmS AnD infoRmATion
analog input devices include a thermistor which changes its electrical resistance in
response to the temperature and a crystal which produces a charge (and a corresponding voltage) in response to the pressure applied. Typically, electrical or electronic circuitry is required to “condition” the signal so that it can be read by the
embedded system. Examples of digital output devices include relays (switches that
are opened or closed by applied voltages), a stepper motor that responds to applied
voltage pulses, or an LED digital display. Examples of analog output devices include
a loudspeaker and a panel meter with a dial. The dial position is controlled by the
interaction of the magnetic ields of a permanent magnet and an electromagnet
driven by the voltage applied to the meter.
Next, we illustrate embedded systems by considering a temperature measurement performed by using a wireless weather station. In addition, this example also
illustrates analog and digital signals, including conversion between the signal types.
ExAMPLE 1-1 Temperature Measurement and Display
A wireless weather station measures a number of weather parameters at an outdoor
site and transmits them for display to an indoor base station. Its operation can be
illustrated by considering the temperature measurement illustrated in Figure 1-4
with reference to the block diagram in Figure 1-3. Two embedded microprocessors
are used, one in the outdoor site and the other in the indoor base station.
The temperature at the outdoor site ranges continuously from -40°F to
+115°F. Temperature values over one 24-hour period are plotted as a function of
time in Figure 1-4(a). This temperature is measured by a sensor consisting of a thermistor (a resistance that varies with temperature) with a ixed current applied by an
electronic circuit. This sensor provides an analog voltage that is proportional to the
temperature. Using signal conditioning, this voltage is changed to a continuous voltage ranging between 0 and 15 volts, as shown in Figure 1-4(b).
The analog voltage is sampled at a rate of once per hour (a very slow sampling
rate used just for illustration), as shown by the dots in Figure 1-4(b). Each value sampled is applied to an analog-to-digital (A/D) converter, as in Figure 1-3, which replaces
the value with a digital number written in binary and having decimal values between
0 and 15, as shown in Figure 1-4(c). A binary number can be interpreted in decimal
by multiplying the bits from left to right times the respective weights, 8, 4, 2, and 1,
and adding the resulting values. For example, 0101 can be interpreted as
0 * 8 + 1 * 4 + 0 * 2 + 1 * 1 = 5. In the process of conversion, the value of the
temperature is quantized from an ininite number of values to just 16 values.
Examining the correspondence between the temperature in Figure 1-4(a) and the voltage in Figure 1-4(b), we ind that the typical digital value of temperature represents an
actual temperature range up to 5 degrees above or below the digital value. For example, the analog temperature range between -25 and -15 degrees is represented by the
digital temperature value of -20 degrees. This discrepancy between the actual temperature and the digital temperature is called the quantization error. In order to obtain
greater precision, we would need to increase the number of bits beyond four in the
output of the A/D converter. The hardware components for sensing, signal conditioning, and A/D conversion are shown in the upper left corner of Figure 1-3.
1-1 / information Representation
Temperature (degrees F)
120
80
40
0
40
0
4
8
12
16
20
24
(a) Analog temperature
Sensor and
Signal Conditioning
Voltage (Volts)
16
12
Time (hours)
Sampling point
8
4
0
Time (Hours)
0
8
12
16
20
(b) Continuous (analog) voltage
4
24
Analog-to-Digital
(A/D) Conversion
Digital numbers (binary)
16
11
00
00
01
0101
01 01
0100
0
00 0
1
00 1
11
4
01
8
00
1
00 1
00 11
11
01
00
01
0
011
10
01
1
01 1
01 11
1
01 1
0111
1
01 1
10
01
0
00 0
0011
0011
11
12
Time (hours)
0
0
8
4
12
16
20
24
16
20
24
20
24
(c) Digital voltage
Digital-to-Analog
(D/A) Conversion
Voltage (volts)
16
12
8
4
0
Time (hours)
0
4
8
12
(d) Discrete (digital) voltage
Signal Conditioning
Voltage (volts)
16
12
8
4
0
0
4
8
12
16
Time (hours)
Output
(e) Continuous (analog) voltage
20 40 60
0 Temp 80
20
100
40 120
20 40 60
0 Temp 80
20
100
40 120
20 40 60
0 Temp 80
20
100
40 120
20 40 60
0 Temp 80
20
100
40 120
20 40 60
0 Temp 80
20
100
40 120
(f) Continuous (analog) readout
FIguRE 1-4
Temperature Measurement and Display
9
10
CHAPTER 1 / DigiTAl SySTEmS AnD infoRmATion
Next, the digital value passes through the microcomputer to a wireless transmitter as a digital output device in the lower right corner of Figure 1-3. The digital
value is transmitted to a wireless receiver, which is a digital input device in the base
station. The digital value enters the microcomputer at the base station, where calculations may be performed to adjust its value based on thermistor properties. The
resulting value is to be displayed with an analog meter shown in Figure 1-4(f) as the
output device. In order to support this display, the digital value is converted to an
analog value by a digital-to-analog converter, giving the quantized, discrete voltage
levels shown in Figure 1-4(d). Signal conditioning, such as processing of the output
by a low-pass analog ilter, is applied to give the continuous signal in Figure 1-4(e).
This signal is applied to the analog voltage display, which has been labeled with the
corresponding temperature values shown for ive selected points over the 24-hour
■
period in Figure 1-4(f).
You might ask: “How many embedded systems are there in my current living
environment?” Do you have a cell phone? An iPod™? An Xbox™? A digital camera? A microwave oven? An automobile? All of these are embedded systems. In
fact, a late-model automobile can contain more than 50 microcontrollers, each controlling a distinct embedded system, such as the engine control unit (ECU), automatic braking system (ABS), and stability control unit (SCU). Further, a signiicant
proportion of these embedded systems communicate with each other through a
CAN (controller area network). A more recently developed automotive network,
called FlexRay, provides high-speed, reliable communication for safety-critical tasks
such as braking-by-wire and steering-by-wire, eliminating primary dependence on
mechanical and hydraulic linkages and enhancing the potential for additional safety
features such as collision avoidance. Table 1-1 lists examples of embedded systems
classiied by application area.
Considering the widespread use of personal computers and embedded systems, digital systems have a major impact on our lives, an impact that is not often
fully appreciated. Digital systems play central roles in our medical diagnosis and
treatment, in our educational institutions and workplaces, in moving from place to
place, in our homes, in interacting with others, and in just having fun! The complexity
of many of these systems requires considerable care at many levels of design abstraction to make the systems work. Thanks to the invention of the transistor and the
integrated circuit and to the ingenuity and perseverance of millions of engineers and
programmers, they indeed work and usually work well. In the remainder of this text,
we take you on a journey that reveals how digital systems work and provide a
detailed look at how to design digital systems and computers.
More on the Generic Computer
At this point, we will briely discuss the generic computer and relate its various parts
to the block diagram in Figure 1-2. At the lower left of the diagram at the beginning
of this chapter is the heart of the computer, an integrated circuit called the processor.
Modern processors such as this one are quite complex and consist of tens to hundreds of millions of transistors. The processor contains four functional modules: the
CPU, the FPU, the MMU, and the internal cache.
1-1 / information Representation
11
TABLE 1-1
Embedded System Examples
Application Area
Product
Banking, commerce and
manufacturing
Copiers, FAX machines, UPC scanners, vending
machines, automatic teller machines, automated
warehouses, industrial robots, 3D printers
Communication
Wireless access points, network routers, satellites
Games and toys
Video games, handheld games, talking stuffed toys
Home appliances
Digital alarm clocks, conventional and microwave
ovens, dishwashers
Media
CD players, DVD players, lat panel TVs, digital
cameras, digital video cameras
Medical equipment
Pacemakers, incubators, magnetic resonance
imaging
Personal
Digital watches, MP3 players, smart phones,
wearable itness trackers
Transportation and navigation
Electronic engine controls, trafic light controllers,
aircraft light controls, global positioning systems
We have already discussed the CPU. The FPU ( loating-point unit) is somewhat like the CPU, except that its datapath and control unit are speciically designed
to perform loating-point operations. In essence, these operations process information represented in the form of scientiic notation (e.g., 1.234 * 107), permitting the
generic computer to handle very large and very small numbers. The CPU and the
FPU, in relation to Figure 1-2, each contain a datapath and a control unit.
The MMU is the memory management unit. The MMU plus the internal cache
and the separate blocks near the bottom of the computer labeled “External Cache”
and “RAM” (random-access memory) are all part of the memory in Figure 1-2. The
two caches are special kinds of memory that allow the CPU and FPU to get at the
data to be processed much faster than with RAM alone. RAM is what is most commonly referred to as memory. As its main function, the MMU causes the memory
that appears to be available to the CPU to be much, much larger than the actual size
of the RAM. This is accomplished by data transfers between the RAM and the hard
drive shown at the top of the drawing of the generic computer. So the hard drive,
which we discuss later as an input/output device, conceptually appears as a part of
both the memory and input/output.
The connection paths shown between the processor, memory, and external
cache are the pathways between integrated circuits. These are typically implemented
12
CHAPTER 1 / DigiTAl SySTEmS AnD infoRmATion
as ine copper conductors on a printed circuit board. The connection paths below the
bus interface are referred to as the processor bus. The connections above the bus
interface are the input/output (I/O) bus. The processor bus and the I/O bus attached
to the bus interface carry data having different numbers of bits and have different
ways of controlling the movement of data. They may also operate at different speeds.
The bus interface hardware handles these differences so that data can be communicated between the two buses.
All of the remaining structures in the generic computer are considered part
of I/O in Figure 1-2. In terms of sheer physical volume, these structures dominate.
In order to enter information into the computer, a keyboard is provided. In order
to view output in the form of text or graphics, a graphics adapter card and LCD
(liquid crystal display) screen are provided. The hard drive, discussed previously, is
an electromechanical magnetic storage device. It stores large quantities of information in the form of magnetic lux on spinning disks coated with magnetic materials. In order to control the hard drive and transfer information to and from it, a
drive controller is used. The keyboard, graphics adapter card, and drive controller
card are all attached to the I/O bus. This allows these devices to communicate
through the bus interface with the CPU and other circuitry connected to the processor buses.
1-2 abstractioN Layers iN computer systems desigN
As described by Moggridge, design is the process of understanding all the relevant
constraints for a problem and arriving at a solution that balances those constraints.
In computer systems, typical constraints include functionality, speed, cost, power,
area, and reliability. At the time that this text is being written in 2014, leading edge
integrated circuits have billions of transistors—designing such a circuit one transistor
at a time is impractical. To manage that complexity, computer systems design is
typically performed in a “top down” approach, where the system is speciied at a high
level and then the design is decomposed into successively smaller blocks until a
block is simple enough that it can be implemented. These blocks are then connected
together to make the full system. The generic computer described in the previous
section is a good example of blocks connected together to make a full system. This
book begins with smaller blocks and then moves toward putting them together into
larger, more complex blocks.
A fundamental aspect of the computer systems design process is the concept of
“layers of abstraction.” Computer systems such as the generic computer can be
viewed at several layers of abstraction from circuits to algorithms, with each higher
layer of abstraction hiding the details and complexity of the layer below. Abstraction
removes unnecessary implementation details about a component in the system so
that a designer can focus on the aspects of the component that matter for the problem being solved. For example, when we write a computer program to add two variables and store the result in a third variable, we focus on the programming language
constructs used to declare the variables and describe the addition operation. But
when the program executes, what really happens is that electrical charge is moved
around by transistors and stored in capacitive layers to represent the bits of data and
1-2 / Abstraction layers in Computer Systems Design
13
Algorithms
Programming Languages
Operating Systems
Instruction Set Architecture
Microarchitecture
Register Transfers
Logic Gates
Transistor Circuits
FIguRE 1-5
Typical Layers of Abstraction in Modern Computer Systems
control signals necessary to perform the addition and store the result. It would be
dificult to write programs if we had to directly describe the low of electricity for
individual bits. Instead, the details of controlling them are managed by several layers
of abstractions that transform the program into a series of more detailed representations that eventually control the low of electrical charges that implement the
computation.
Figure 1-5 shows the typical layers of abstraction in contemporary computing
systems. At the top of the abstraction layers, algorithms describe a series of steps that
lead to a solution. These algorithms are then implemented as a program in a highlevel programming language such as C++, Python, or Java. When the program is running, it shares computing resources with other programs under the control of an
operating system. Both the operating system and the program are composed of
sequences of instructions that are particular to the processor running them; the set of
instructions and the registers (internal data memory) available to the programmer
are known as the instruction set architecture. The processor hardware is a particular
implementation of the instruction set architecture, referred to as the microarchitecture; manufacturers very often make several different microarchitectures that execute the same instruction set. A microarchitecture can be described as underlying
sequences of transfers of data between registers. These register transfers can be
decomposed into logic operations on sets of bits performed by logic gates, which are
electronic circuits implemented with transistors or other physical devices that control the low of electrons.
An important feature of abstraction is that lower layers of abstraction can usually be modiied without changing the layers above them. For example, a program
written in C++ can be compiled on any computer system with a C++ compiler and
then executed. As another example, an executable program for the Intel™ x86
instruction set architecture can run on any microarchitecture (implementation) of
that architecture, whether that implementation is from Intel™ or AMD. Consequently,
abstraction allows us to continue to use solutions at higher layers of abstraction even
when the underlying implementations have changed.
This book is mainly concerned with the layers of abstraction from logic gates
up to operating systems, focusing on the design of the hardware up to the interface
between the hardware and the software. By understanding the interactions of the
14
CHAPTER 1 / DigiTAl SySTEmS AnD infoRmATion
layers of abstraction, we can choose the proper layer of abstraction on which to concentrate for a given design, ignoring unnecessary details and optimizing the aspects
of the system that are likely to have the most impact on achieving the proper balance
of constraints for a successful design. Oftentimes, the higher layers of abstraction
have the potential for much more improvement in the design than can be found at
the lower layers. For example, it might be possible to re-design a hardware circuit for
multiplying two numbers so that it runs 20–50% faster than the original, but it might
be possible to have much bigger impact on the speed of the overall circuit if the algorithm is modiied to not use multiplication at all. As technology has progressed and
computer systems have become more complex, the design effort has shifted to higher
layers of abstraction and, at the lower layers, much of the design process has been
automated. Effectively using the automated processes requires an understanding of
the fundamentals of design at those layers of abstraction.
An Overview of the Digital Design Process
The design of a digital computer system starts from the speciication of the problem
and culminates in representation of the system that can be implemented. The design
process typically involves repeatedly transforming a representation of the system at
one layer of abstraction to a representation at the next lower level of abstraction, for
example, transforming register transfers into logic gates, which are in turn transformed into transistor circuits.
While the particular details of the design process depend upon the layer of
abstraction, the procedure generally involves specifying the behavior of the system,
generating an optimized solution, and then verifying that the solution meets the speciication both in terms of functionality and in terms of design constraints such as speed
and cost. As a concrete example of the procedure, the following steps are the design
procedure for combinational digital circuits that Chapters 2 and 3 will introduce:
1. Speciication: Write a speciication for the behavior of the circuit, if one is not
already available.
2. Formulation: Derive the truth table or initial Boolean equations that deine
the required logical relationships between inputs and outputs.
3. Optimization: Apply two-level and multiple-level optimization to minimize
the number of logic gates required. Draw a logic diagram or provide a netlist
for the resulting circuit using logic gates.
4. Technology Mapping: Transform the logic diagram or netlist to a new diagram
or netlist using the available implementation technology.
5. Veriication: Verify the correctness of the inal design.
For digital circuits, the speciication can take a variety of forms, such as text or a
description in a hardware description language (HDL), and should include the respective symbols or names for the inputs and outputs. Formulation converts the speciication into forms that can be optimized. These forms are typically truth tables or Boolean
expressions. It is important that verbal speciications be interpreted correctly when
formulating truth tables or expressions. Often the speciications are incomplete, and
any wrong interpretation may result in an incorrect truth table or expression.
1-3 / number Systems
15
Optimization can be performed by any of a number available methods, such as
algebraic manipulation, the Karnaugh map method, which will be introduced in
Chapter 2, or computer-based optimization programs. In a particular application,
speciic criteria serve as a guide for choosing the optimization method. A practical
design must consider constraints such as the cost of the gates used, maximum allowable propagation time of a signal through the circuit, and limitations on the fan-out
of each gate. This is complicated by the fact that gate costs, gate delays, and fan-out
limits are not known until the technology mapping stage. As a consequence, it is dificult to make a general statement about what constitutes an acceptable end result
for optimization. It may be necessary to repeat optimization and technology mapping multiple times, repeatedly reining the circuit so that it has the speciied behavior while meeting the speciied constraints.
This brief overview of the digital design process provides a road map for the
remainder of the book. The generic computer consists mainly of an interconnection
of digital modules. To understand the operation of each module, we need a basic
knowledge of digital systems and their general behavior. Chapters 1 through 5 of this
book deal with logic design of digital circuits in general. Chapters 4 and 6 discuss the
primary components of a digital system, their operation, and their design. The operational characteristics of RAM are explained in Chapter 7. Datapath and control for
simple computers are introduced in Chapter 8. Chapters 9 through 12 present the
basics of computer design. Typical instructions employed in computer instruction-set
architectures are presented in Chapter 9. The architecture and design of CPUs are
examined in Chapter 10. Input and output devices and the various ways that a CPU
can communicate with them are discussed in Chapter 11. Finally, memory hierarchy
concepts related to the caches and MMU are introduced in Chapter 12.
To guide the reader through this material and to keep in mind the “forest” as
we carefully examine many of the “trees,” accompanying discussion appears in a
blue box at the beginning of each chapter. Each discussion introduces the topics in
the chapter and ties them to the associated components in the generic computer diagram at the start of this chapter. At the completion of our journey, we will have covered most of the various modules of the computer and will have gained an
understanding of the fundamentals that underlie both its function and design.
1-3
Number systems
Earlier, we mentioned that a digital computer manipulates discrete elements of information and that all information in the computer is represented in binary form.
Operands used for calculations may be expressed in the binary number system or in
the decimal system by means of a binary code. The letters of the alphabet are also
converted into a binary code. The remainder of this chapter introduces the binary
number system, binary arithmetic, and selected binary codes as a basis for further
study in the succeeding chapters. In relation to the generic computer, this material is
very important and spans all of the components, excepting some in I/O that involve
mechanical operations and analog (as contrasted with digital) electronics.
The decimal number system is employed in everyday arithmetic to represent
numbers by strings of digits. Depending on its position in the string, each digit has an
associated value of an integer raised to the power of 10. For example, the decimal
16
CHAPTER 1 / DigiTAl SySTEmS AnD infoRmATion
number 724.5 is interpreted to represent 7 hundreds plus 2 tens plus 4 units plus 5
tenths. The hundreds, tens, units, and tenths are powers of 10 implied by…