Transcript slides

Review for Exam 2
 Chapters 4 and 5
 Close book and close notes
 Bring pencil
 No computers or cell phones allowed
Logic and Computer Design Fundamentals
Chapter 4 – Arithmetic Functions
Charles Kime & Thomas Kaminski
© 2008 Pearson Education, Inc.
(Hyperlinks are active in View Show mode)
Implementations: Half-Adder
 The most common half
adder implementation is:
S = XY
C = XY
X
Y
S
C
X Y
C
S
0
0
1
1
0
0
0
1
0
1
1
0
0
1
0
1
Implementation: Full Adder
 Full Adder Schematic for bit i
Gi
Si =(Ai Bi)Ci
Co = AB + (AB)Ci
or Ci+1 = AiBi + (AiBi )Ci
Ai Bi
Pi
with
G = generate (=AB) and
P = propagate (=AB)
Ci+1 = Gi + Pi · Ci
or:
Ci+
1
Si
Co= (G = Generate) OR (P =Propagate AND Ci = Carry In)
Ci
4-bit Ripple-Carry Binary Adder
 A four-bit Ripple Carry Adder made from four
Ai
Bi
1-bit Full Adders:
Ci+1
FA
Si
 Slow adder: many delays from input to output
Ci
Delay of a Full Adder
 Assume that AND, OR gates have 1 gate delay
and the XOR has 2 gate delays
 Delay of the Sum and Carry bit:
=  
Gi
Si Ai Bi Ci
Ai Bi
S0= A0 B0 C0
2 delays
2+2=4 delays
P
i
Ci
Ci+1=AiBi+ ( Ai  Bi) Ci
C1 =A0B0+ ( A0 B0) C0
@2
Ci+
1
Si
@3
2+2=4 delays
Delay of the Carry
C2 = A1B1+ ( A1 B1) C1
@2
@4
@?
Gi
Ai Bi
@?
C3 = A2B2+ ( A2 B2) C2
@2
@6
Pi
@7
@8
C4: delay 8+2 = 10
Ci+1
For n stage: delay of Cn: 2n+2 delays!
and Sn: 2n+4 (=@Cn + 2)
The bottleneck is the delay of the carry.
Si
Ci
Delay in a Ripple-carry adder
Example: 4-bit adder (n=4)
@0
@0
@10
@10
@4
@6
@8
@8
@6
@4
One problem with the addition of binary numbers is the
length of time to propagate the ripple carry from the least
significant bit to the most significant bit.
Example: 32-bit Ripple-carry has a unit gate delay of 1ns.
•What is the total delay of the adder?
•What is the max frequency at which it can be clocked?
Carry Lookahead Adder
 Uses a different circuit to calculate
the carry out (calculates it ahead), to
speed up the overall addition
 Requires more complex circuits.
 Trade-off: speed vs. area (complexity,
cost)
PFA generates G and P
@6
4-bit Implementation
@6
@6
@4
@4
C 1 = G0 + P 0 C 0
C2= G1 + P1G0 + P1P0 C0
@4
C3= G2 + P2G1 + P2P1G0 + P2P1P0 C0
Carry lookahead logic
@4
4-3 b. Complements
 Two type of complements:
• Diminished Radix Complement of N
 Defined as (rn - 1) – N, with n = number of digits
or bits
 1’s complement for radix 2
• Radix Complement
 Defined as rn - N
 2’s complement in binary
 As we will see shortly, subtraction is done by
adding the complement of the subtrahend
 If the result is negative, takes its 2’s
complement
Binary 1's Complement
 For r = 2, N = 0111 00112, n = 8 (8 digits):
(rn – 1) = 256 -1 = 25510 or 111111112
 The 1's complement of 011100112 is then:
11111111
rn – 1
- N
– 01110011
1’s compl
10001100
 Since the 2n – 1 factor consists of all 1's
and since 1 – 0 = 1 and 1 – 1 = 0, the one's
complement is obtained by
complementing each individual bit
(bitwise NOT).
Binary 2's Complement
 For r = 2, N = 0111 00112, n = 8 (8 digits), we
have:
(rn ) = 25610 or 1000000002
 The 2's complement of 01110011 is then:
100000000
rn
- N
– 01110011
2’s compl
10001101
 Note the result is the 1's complement plus 1:
01110011 Invert bit-wise
10001100
+
1
2’s complement
10001101
Alternate 2’s Complement Method
 Given: an n-bit binary number, beginning at
the least significant bit and proceeding
upward:
• Copy all least significant 0’s
• Copy the first 1
• Complement all bits thereafter.
 2’s Complement Example:
10010100
• Copy underlined bits:
100
• and complement bits to the left:
01101100
3-3c. Subtraction with 2’s Complement
 For n-digit, unsigned numbers M and
N, find M  N in base 2: Algorithm
Add the 2's complement of the
subtrahend N to the minuend M:
M + (2n  N) = M  N + 2n
Unsigned 2’s Complement Subtraction
Example 1
 Find 010101002 – 010000112
84
-67
17
Discard carry
101010100
01010100
–01000011 2’s comp + 10111101
00010001
The carry of 1 indicates that no
correction of the result is required
Unsigned 2’s Complement Subtraction
Example 2
 Find 010000112 – 010101002
67
-84
-17
01000011
– 01010100
0
01000011
2’s comp + 10101100
11101111 2’s comp
00010001
 The carry of 0 indicates that a
correction of the result is required.
 Result = – (00010001)
Signed Binary Numbers
 So far we focused on the addition and
subtraction of unsigned numbers.
 For SIGNED numbers:
• How to represent a sign (+ or –)?
 One need one more bit of information.
 Two ways:
• Sign + magnitude
• Signed-Complements
 Thus:
• Positive number are unchanged
• Negative numbers: use one of the above methods
Exercise
 Give the sign+magnitude, 1’s
complement and 2’s complement of
(using minimal required bits):
Sign+Mag
+2
010
-2
110
+3
011
-3
111
+0
000
-0
100
One’s compl.
010
101
011
100
000
111
Two’s compl.
010
110
011
101
000
000
2’s Complement Arithmetic
 Addition: Simple rule
• Represent negative number by its 2’s
complement. Then, add the numbers including
the sign bits, discarding a carry out of the
sign bits (2's complement):
• Indeed, e.x. M+(-N)  M + (2n-N)
 If M ≥ N: (M-N) + 2n
ignore carry out: M-N is the
answer in two’s complement)
 If M ≤ N: (M-N) + 2n = 2n – (N-M) which is 2’s
complement of the (negative) number (M-N): -(N-M).
 Subtraction: M-N  M + (2n-N)
Form the complement of the number you are
subtracting and follow the rules for addition.
Overflow examples (continued)
carries
18
+15
33
011110
010010
+0 0 1 1 1 1
100001
-31!
wrong answer
due to overflow
18
- 15
3
110000
010010
+1 1 0 0 0 1
000011
3
correct answer
no overflow
Overflow occurs when the carry-in into the sign bit (most
left bit) is different from the carry-out of the sign bit.
Logic and Computer Design Fundamentals
Chapter 5 – Sequential Circuits
Charles Kime & Thomas Kaminski
© 2008 Pearson Education, Inc.
(Hyperlinks are active in View Show mode)
5-1 Sequential circuit block
diagram
Outputs
Inputs
Combinational
Logic
Next
State
Storage State
Elements (or present state)
Combinatorial Logic gives:
CLOCK
•Next state function
Next State = f(Inputs, State)
•Output function
Synchronous
machine
Types of Sequential Circuits Illustra
 Moore machine:
• Outputs = h(State)
 Mealy machine
• Outputs = g(Inputs, State)
Mealy
Comb. Outputs
logic
Inputs
Combinational
Logic
Next
State
Storage State
Elements (or present state)
CLOCK
Basic (NOR) S – R Latch
 Function Table:
R (reset)
S (set)
Q
Q
 This element is also the basic building block in
SRAM memories
S R Q Q
0 0 hold, no change
0 1 0 1 Reset
1 0 1 0 Set
1 1
0 0 not allowed, unstable (Q=Q)
Timing waveforms of NOR S-R latch
S
0
R
0
Q
0
Q
1
S
1
Q
R
2
Q
set
reset
tpd
No change
unstable
not allowed
Clocked (NOR) S-R Latch
S
1
Q
2
Q
Clk
R
• Clk=0: input has no effect: latch is always in
“hold” mode
• Clk=1: latch is a regular S-R latch
Function table of the (NAND) S - R
latch
S (set)
R (reset)
Function table:
S R
1 1
0 1
1 0
0 0
Q
Q
Q Q
hold, no change
1 0 Set
0 1 Reset
1 1 not allowed, unstable (Q=Q=1)
S = 0, R = 0 is
forbidden as input pattern
Latch with NAND
A
A
=
1
A
A
When both S=R=1: the NAND gates act as inverters and
the circuit implements two inverters: “hold mode”
Q
1
Q
Q
Clocked latch:
C
0
1
1
1
1
S
x
0
0
1
1
R Next state Q(t+1)
S
Q(t) no change
x
0 Q(t) no change
Q(t+1) = 0, Reset C
1
0
Q(t+1) = 1, Set
1
Q=Q’=1 UndefinedR
1
Q
S
Q
R
Q
D Latch (Delay latch)
 S-R Latch can be used
D
for at D Latch:
Q
C
Q(t+1)
SR latch:
S R Q+ Q+
0 0
hold,
0 1 0 1
1 0 1 0
1 1 0 0
Q
D
Q
C
Q
Function table D latch:
D Q(t+1)
0 0
1 1
Latch issues
 Latches can cause serious timing
problems (races) in sequential
circuits
• Due to the fact that a latch is
“transparent” when the clock C = 1
 The timing problems can be
prevented by using “Flip-Flops”
The Latch Timing Problem (continued)
 Similar timing problems in the sequential circuits:
Outputs
Inputs
X0 X2
Combinational
Logic
X1 X2
X3
Next State
D Latch
X0
X1 X2
(storage) State
C=0 1
• The state should change only once every new clock cycle:
• C=1:
• Now the current state becomes X1 and a new state is generated by the
combinational logic circuit: X2.
• However, if C=1, the new “next state” X2 will create a new current state
X2!, etc…
How to solve the timing problem: use
Flip-Flops
 A solution to the latch timing problem is to break the closed
path from In to Out within the storage element
In
D
Q
In
Out
D
Q
C
Q
C: 0 1
C: 0 1
C
Q
Out
D-Flip-Flop
D-Latch
C
C
In
In
Out
Out
Symbol: Master-Slave Flip-Flop
S
S
C
C
R
R
Q
Y
S
Q
Q
Q
Q
C
Q
Y’
R
Notice; the output changes when
the clock C goes low.
C
Symbol:
S
Q
C
R
Q
Sometimes one adds:
To indicate that the input responds when C=1, but the output changes
when C goes to 0
Flip-Flop Problem: 1’ catching
Glitch
C
S
R
Y
Master out
Q
Slave out
Master Slave
active active
S
S
C
C
R
R
1’ catching
Q
Y
S
Q
Q
Q
Q
C
Q
Y’
R
wrong output
should have
been 0
Flip-Flop Solution: Edge-triggered
 An edge-triggered flip-flop changes values
at the clock edge (transition):
• responds to its input at a well-defined moment
(at the clock-transition)
• ignores the pulse while it is at a constant level
Negative edge-triggered
Clock
Positive edge-triggered
ignored
In
The value of the input at the clock transition (negative or positive)
determines the output
Edge-Triggered D Flip-Flop
D
D
Q
S
Q
Q
Q
Q
C
C
C
Q
R
 The 1s-catching behavior is not present with D replacing S
and R inputs
 The change of the D flip-flop output is associated with the
negative edge at the end of the pulse:
 It is called a negative-edge triggered flip-flop
No 1’s catching in the edge-triggered D
Flip-Flops
D
D
Q
C
C
Q
Y
S
C
R
Q
Q
Q
Q
C
D
Y
Master out
Q
Slave out
Master
active
Slave
active
no 1’ catching
correct output
Exercise
Timing diagram of a (Nor) S-R MasterSlave Flip-Flop
S
Q
C
R
C
Master
active
Q
=
S
S
C
C
R
R
Q
Y
S
Q
Q
Q
Q
C
Q
Y’
R
Slave
active Master
active
S
R
Y
undefined
Y’
undefined
Master out
Q
Slave out
undefined
Direct inputs: active-low or activehigh
 D flip-flop with active-low direct inputs :
Direct
inputs
S
D
Q
C
R
Q
S
0
1
1
1
 Active high direct inputs:
D
S
Q
C Q
R
S
0
1
0
0
R
1
0
1
1
C
x
x
D
x
x
0
1
Q
1
0
0
1
Q’
0
1
1
0
R
1
0
0
0
C
x
x
D
x
x
0
1
Q
0
1
0
1
Q’
1
0
1
0
5-4 Sequential Circuit Analysis
 Consider the following circuit:
input
x
Q
A
C Q’
A
Q
B
D
D
CLK
states
 What does it do?
How do the outputs
change when an
input arrives?
C Q'
y
output
Step 1: Input and output equations
DA
x
• DA = A(t)x(t)+B(t)x(t)
• DB = A(t)x(t)
Q
A
C Q’
A
Q
B
D
Next State
 Output y
DB
• y(t) = x(t)(B(t) + A(t))
D
CLK
C Q'
y
Output
Present state
 Boolean equations for
the inputs to the flip
flops:
State Table

For the example: A(t+1) = A(t)x(t) + B(t)x(t)
B(t+1) =A (t)x(t)
y(t) =x (t)(B(t) + A(t))
(2m+n) rows
23 rows
Inputs of the table
m: no. of FF
n: no. of inputs
Outputs of the table
Present State
Input
Next State
Output
A(t) B(t)
0 0
0 0
0 1
0 1
1 0
1 0
1 1
1 1
x(t)
0
1
0
1
0
1
0
1
A(t+1) B(t+1)
y(t)
0
0
0
1
0
1
0
1
0
1
0
1
0
0
0
0
0
0
1
0
1
0
1
0
State diagram convention
Moore Machine:
Mealy Machine:
to next
state
In/out
in
State
out
Example:
AB
y
State
1
x
01
1
Moore type output depends
only on state
x/y’
x=1/y=0
01
01
Mealy type output depends
on state and input
State Diagram for the example
 Graphical representation of the state table:
x=0/y=0
x=0/y=1
AB
00
x=1/y=0
x=0/y=1 1 0
x=1/y=0
Present State
Input
Next State
Output
A(t) B(t)
0 0
0 0
0 1
0 1
1 0
1 0
1 1
1 1
x(t)
0
1
0
1
0
1
0
1
A(t+1) B(t+1)
0
0
0
1
0
0
1
1
0
0
1
0
0
0
1
0
y(t)
0
0
1
0
1
0
1
0
x=1/y=0
x=0/y=1
11
01
x=1/y=0
Equivalent State Example
0/0
 Are there other equivalent states?
 Examining the new diagram,
states S1 and S2 are equivalent since
S0
1/0
• their outputs for input
0 is 1 and input 1 is 0,
and
• their next state for input
0 is both S0 and for input
1 is both S2,
 Replacing S1 and S2 by a
single state gives state
diagram:
S1
0/1
1/0
0/1
S2
1/0
0/0
S0
1/0
S1
0/1
1/0
Exercise: Derive the state diagram of
the following Circuit
 Logic Diagram:
D
Q
A
C RQ
Moore or Mealy?
What is the reset state?
D
Q
B
C RQ
5V
D
Q
Reset
•
•
Clock
CR Q
C
Z
5-5 Sequential Circuit Design
Idea,
New product
Specification
?
IN
•Word description
State Diagram
Comb.
Crct.
DA
DB
•State Table
State encoding
Design
procedure
•Select type of Flip-flop
•Input equations to FF, output eq.
•Verification
O
U
T
Specification
 Component Forms of Specification
•
•
•
•
•
•
Written description
Mathematical description
Hardware description language
Tabular description
Equation description
Diagram describing operation (not just
structure)
5-6 Other Flip-Flop Types
 J-K and T flip-flops
• Behavior
• Implementation
 Basic descriptors for understanding
and using different flip-flop types
• Characteristic tables
• Characteristic equations
• Excitation tables
J-K Flip-flop
 Behavior of JK flip-flop:
• Same as S-R flip-flop with
J analogous to S and K
analogous to R
• Except that J = K = 1 is
allowed, and
• For J = K = 1, the flip-flop
changes to the opposite
state (toggle)
 Behavior described
by the characteristic
table (function table):
J
Q
C
K
J
0
0
1
1
K Q(t+1)
0 Q(t) no change
1 0
reset
0 1
set
1 Q(t) toggle
T Flip-flop
 Behavior described T
by its characteristic 0
1
table:
• Has a single input T
 For T = 0, no change
to state
 For T = 1, changes
to opposite state
Q(t+1)
Q(t) no change
Q(t) complement
Characteristic equation:
Q(t+1)=T’Q(t) + TQ’(t)
= TQ(t)
T
C