04.10.

2011

Digital Design g ta es g
Chapter 3: Sequential Logic Design -- Controllers
Slides to accompany the textbook Digital Design, with RTL Design, VHDL, and Verilog, 2nd Edition, by Frank Vahid, John Wiley and Sons Publishers, 2010. http://www.ddvahid.com p

Copyright 2010 Frank Vahid

Instructors of courses requiring Vahid's Digital Design textbook (published by John Wiley and Sons) have permission to modify and use these slides for customary course-related activities, subject to keeping this copyright notice in place and unmodified. These slides may be posted as unanimated pdf versions on publicly-accessible course websites.. PowerPoint source (or pdf Digital not be 2e with animations) may Design posted to publicly-accessible websites, but may be posted for students on internal protected sites or distributed directly to students by other electronic means. Copyright 2010 1 Instructors may make printouts of the slides available to students for a reasonable photocopying charge, without incurring royalties. Any other use requires explicit permission. Instructors Frank Vahid may obtain PowerPoint source or obtain special use permissions from Wiley see http://www.ddvahid.com for information.

Introduction
1 a

3.1

Sequential circuit
Output depends not just on present inputs (as in combinational circuit), but on past sequence of inputs ), p q p
Stores bits, also known as having state

1 0 Combinational digital circuit F

1 a b 0 Sequential digital circuit

Simple example: a circuit that counts up in binary

This chapter will:

Design a new building block, a flip-flop, to store one bit Combine flip-flops to build multi-bit storage register Describe sequential behavior with finite state machines Convert a finite state machine to a controller sequential circuit with a register and combinational logic
Must know sequence of past inputs to know output

Digital Design 2e Copyright 2010 Frank Vahid

2
Note: Slides with animation are denoted with a small red "a" near the animated items

04.10.2011

Storing One Bit Flip-Flops

Example Requiring Bit Storage
Call button Blue light Bit Storage

3.2

Flight attendant call button

Press call: light turns on
Stays on after button released

Cancel button

1. Call button pressed light turns on

Call button Cancel button Blue light Bit Storage

Press cancel: light turns off

Stays off after button released

Logic gate circuit to implement this?

Call Cancel
a

2. Call button released light stays on

Q
Call button Cancel button Bit Storage

Blue light

Doesnt work. Q=1 when Call=1, but doesnt stay 1 when Call returns to 0 Need some form of feedback in the circuit
Digital Design 2e Copyright 2010 Frank Vahid

3. Cancel button pressed light turns off 3

First attempt at Bit Storage

Need some sort of feedback
Does circuit on the right do what we want?
No: Once Q becomes 1 (when S=1), Q stays 1 forever no value of S can bring Q back to 0
S 0 0 t 0Q S 1
0 t 0Q

S t

S 1 0 t

1Q

S 1 1 t

1Q

S 0 1 t

1Q

S t Q

1 0 1 0 1 0
4

Digital Design 2e Copyright 2010 Frank Vahid

04.10.2011

Bit Storage Using an SR Latch

S (set) SR latch

Does the circuit to the right, with cross-coupled NOR gates, do what we want?
Yes! How did someone come up with that circuit? Maybe just trial and error, a bit of insight...
R (reset)
S=0 0 1 t S=0 0 1 R=0 1 t S=1 1 0 R=0 0 t S=0 1 0 Q R=0 0 t

Recall NOR
0 0 1

1 R=1

0 Q

0 Q

1 S 0 R1 0 t 1 0 1 Q 0

Digital Design 2e Copyright 2010 Frank Vahid

Example Using SR Latch for Bit Storage

SR latch can serve as bit storage in previous example of flight attendant call button flight-attendant
Call=1 : sets Q to 1
Q stays 1 even after Call=0
Call button Cancel button Blue lig ht Bit S torage

Cancel=1 : resets Q to 0

Call button

0
a

But, theres a problem...

Cancel
button

Blue light Q R

Digital Design 2e Copyright 2010 Frank Vahid

04.10.2011

Problem with SR Latch

Problem
If S=1 and R=1 simultaneously, we dont know what value Q will take
1

S=1 0 0

S=0 0 1

S=0 1 0

S R t

0 1 0 1 0 1

0 R=1

0 Q R=0
a

1 Q R=0

0 Q

Q 0
a

Q may oscillate. Then, because one path will be slightly longer than the other, Q will eventually settle to 1 or 0 but we dont know which. Known as a race condition.
Digital Design 2e Copyright 2010 Frank Vahid

t Q

1 0 1 0

Problem with SR Latch

Designer might try to avoid problem using external circuit
Circuit should prevent SR from ever being 11 But 11 can occur due to different path delays
External circuit Call button Call S SR latch
1 Call 0 1

Q Cancel button Cncl R

Cncl 0 1 S 0 SR = 11 1 R 0 2 ns
8

Assume 1 ns delay per gate. The longer path from Call to R than from Call to S causes SR=11 for short time could be long enough to cause oscillation
Digital Design 2e Copyright 2010 Frank Vahid

04.10.2011

Problem with SR Latch

Glitch can also cause undesired set or reset
External circuit Call button Call S SR latch

1 Call 0 1 Cncl 0
Q

1 S 0 1 SR = 01 (undesired glitch) 4 ns
9

Cancel button

Cncl

Suppose this wire has 4 ns delay

R 0

Digital Design 2e Copyright 2010 Frank Vahid

Solution: Level-Sensitive SR Latch

Add enable input C Only let S and R change when C=0
Ensure circuit in front of SR never sets SR 11, SR=11 except briefly due to path delays
Level-sensitive SR latch S S1

C Q R R1
S

Set C=1 after time for S and R to be stable When C becomes 1, the stable S and R value passes through the two AND gates to the SR latchs S1 R1 inputs. 1
Call

Level-sensitive SR latch Call S S1

S Clk C Cncl

0 1

C R

Q Q

0 1 0 R Q C
1

Level-sensitive SR latch symbol

0 1 0
S1

R Cncl
Digital Design 2e Copyright 2010 Frank Vahid

R1

1 0

Glitch on R (or S) doesnt affect R1 (or (S1)

Correct values when enabled

1 R1 0

10

04.10.2011

Level-Sensitive D Latch
SR latch requires careful design to ensure SR=11 never occurs D latch relieves designer of that burden
Inserted inverter ensures R always opposite of S
D 1 0 1 0 1 S1 0 1 0 1 0
D C Q Q
a

D latch D S S1

C Q R R1

D latch symbol
a

R1
Digital Design 2e Copyright 2010 Frank Vahid

11

Problem with Level-Sensitive D Latch

D latch still has problem (as does SR latch)
When C=1, through how many latches will a signal travel? Depends on how long C=1 C 1
Clk_A signal may travel through multiple latches Clk_B signal may travel through fewer latches

1
D1 C1 Q1

1?
D2 C2 Q2

1?
D3 C3 Q3

1?
D4 C4 Q4

Clk Clk_A
Digital Design 2e Copyright 2010 Frank Vahid

Clk_B
12

04.10.2011

Problem with Level-Sensitive D Latch

D latch D1 D2 S1

0>1
S2

D latch

0>1

0>1
C2

0>1

C1

D3 Q3 D4 Q4 C3 Q1 R1 R2 C4

0>1 (a)

1>0 1>0

Q2

0>1

Clk

Clk D1 Q1/D2
a

Long clock Clk D1 Q1/D2 S2 R2 2nd latch set (b) Q2

Short clock

Q1 doesn't change

S2 R2 Q2

(c) 13

Digital Design 2e Copyright 2010 Frank Vahid

D Flip-Flop
Can we design bit storage that only stores a value on the rising edge of a clock signal?
rising edges
Clk

Flip-flop: Bit storage that stores on clock edge One design master-servant
Clk = 0 master enabled, loads D, appears at Qm enabled D Qm. Servant disabled. Clk = 1 Master disabled, Qm stays same. Servant a latch enabled, loads Qm, appears at Qs. Thus, value at D (and hence at Qm) when Clk changes from 0 to 1 gets stored into servant
D flip-flop D latch D latch Ds Cs Qs Qs Clk D/Dm Cm Q
Note: Hundreds of different flip-flop designs exist

Dm Cm

Qm

Qm/Ds Cs Qs
14

master Clk
Digital Design 2e Copyright 2010 Frank Vahid

servant

04.10.2011

D Flip-Flop
Solves problem of not knowing through how many latches a signal travels when C=1
In figure below, signal travels through exactly one flip-flop, for Clk_A or Clk_B Clk B Why? Because on rising edge of Clk, all four flip-flops are loaded simultaneously then all four no longer pay attention to their input, until the next rising edge. Doesnt matter how long Clk is 1.

D1

Q1

D2

Q2

D3

Q3

D4

Q4
Two latches inside each flip-flop

Clk Clk_A Clk_B

Digital Design 2e Copyright 2010 Frank Vahid

15

D Flip-Flop

D
The triangle means edgetriggered clock input

Q Q

Q Q

Internal design: Just invert servant clock rather than master

Symbol for rising-edge y g g triggered D flip-flop

rising edges
Clk

Symbol for falling-edge y g g triggered D flip-flop

falling edges
Clk

Digital Design 2e Copyright 2010 Frank Vahid

16

04.10.2011

D Latch vs. D Flip-Flop

Latch is level-sensitive
Stores D when C=1

Flip-flop is edge triggered p p g gg

Stores D when C changes from 0 to 1

Saying level-sensitive latch or edge-triggered flip-flop is redundant Comparing behavior of latch and flip-flop:
Clk D 3 Q (D latch) 1 2
a

Q (D flip-flop)
Digital Design 2e Copyright 2010 Frank Vahid

10

Latch follows D while Clk is 1 Flip-flop only loads D during Clk rising edge
17

Clock Signal
Flip-flop Clk inputs typically connect to one clock signal
Coming from an oscillator component Generates periodic p lsing signal pulsing
Below: "Period" = 20 ns, "Frequency" = 1/20 ns = 50 MHz "Cycle" is duration of 1 period (20 ns); below shows 3.5 cycles
Osc. Clk

1 Clk Time: 0 0 ns 0 10 ns 1 20 ns 0 30 ns 1 40 ns 0 50 ns 1 60 ns 0
Freq. 100 GHz 10 GHz 1 GHz 100 MHz 10 MHz Period 0.01 ns 0.1 ns 1 ns 10 ns 100 ns

Period/Freq shortcut: Remember 1 ns 1 GHz

Digital Design 2e Copyright 2010 Frank Vahid

18

04.10.2011

Flight-Attendant Call Button Using D Flip-Flop

D flip-flop will store bit Inputs are Call, Cancel, and present value of D flip-flop, Q Truth table shown below
a

Call button
Cancel

Call
Comb.

Blue light

Cncl Circuit
Clk Q

button Q

Preserve value: if Q=0, make D=0; if Q=1, make D=1 Cancel -- make D=0 Call -- make D=1 Lets give priority to Call -- make D=1
Digital Design 2e Copyright 2010 Frank Vahid

Call but ton

Call
D Q

Cancel
but ton

Cancel Q
Clk

Blue light

Circuit derived from truth table, using Chapter 2 combinational logic design process 19

Bit Storage Summary

SR latch S (set)
Level-sensitive SR latch S S1

D latch D C S S1 D D latch Dm Qm

D flip-flop D latch Q Ds Qs Q Cs Qs servant

C Q R (reset) Feature: S=1 sets Q to 1, R=1 resets Q to 0. Problem: SR=11 yields undefined Q, other glitches may set/reset inadvertently. R R1 Feature: S and R only have effect when C=1. An external circuit can prevent SR=11 when C=1. g Problem: avoiding SR=11 can be a burden. Q

Q R R1

Cm master Clk

Feature: SR cant be 11. Problem: C=1 for too long will propagate new values through too many latches; for too short may not g result in the bit being stored.

Feature: Only loads D value present at rising clock edge, so values can't propagate to other flip-flops during same clock cycle. Tradeoff: uses g y more gates internally, and requires more external gates than SRbut transistors today are more plentiful and cheaper.

We considered increasingly better bit storage until we arrived at the robust D flip-flop bit storage
Digital Design 2e Copyright 2010 Frank Vahid

20

10

04.10.2011

Basic Register
Typically, we store multi-bit items
e.g., storing a 4-bit binary number

Register: multiple flip-flops sharing clock signal g p p p g g

From this point, well use registers for bit storage
No need to think of latches or flip-flops But now you know whats inside a register
I3 I2 I1 I0 4-bit register D Q clk Q3 Q2 Q1 Q0 D Q D Q D Q

I3 I2 I1 I0 reg(4) (4)

Q3 Q2 Q1 Q0

Digital Design 2e Copyright 2010 Frank Vahid

21

Example Using Registers: Temperature Display

Temperature history display
Sensor outputs temperature as 5-bit binary number Timer pulses C every hour Record temperature on each pulse display last three recorded values pulse,
Present 1 hour ago Display 2 hours ago Display

24 21
a

Temperature sensor
x4 x3 x2 x1 x0 timer C

Display

a4 a3 a2 a1 a0

b4 b3 b2 b1 b0

c4 c3 c2 c1 c0

18

TemperatureHistoryStorage T t Hi t St

Digital Design 2e Copyright 2010 Frank Vahid

22

11

04.10.2011

Example Using Registers: Temperature Display

Use three 5-bit registers
24 21 18
a

a4 a3 a2 a1 a0 x4 x3 x2 x1 x0 C I4 I3 I2 I1 I0 Ra Q4 Q3 Q2 Q1 Q0 I4 I3 I2 I1 I0 Rb Q4 Q3 Q2 Q1 Q0

b4 b3 b2 b1 b0 I4 I3 I2 I1 I0 Rc Q4 Q3 Q2 Q1 Q0

c4 c3 c2 c1 c0

TemperatureHistoryStorage

x4...x0 C
a

15 18 20 21 21 22 24 24 24 25 25 26 26 26 27 27 27 27

Ra Rb Rc

0 0 0

18 0 0

21 18 0

24 21 18

25 24 21

26 25 24

27 26 25

Note that registers only loaded on rising clock edges

Digital Design 2e Copyright 2010 Frank Vahid

23

Finite-State Machines (FSMs) and Controllers

Want sequential circuit with particular behavior over time p Example: Laser timer
Pushing button causes x=1 for exactly 3 clock cycles
Precisely-timed laser pulse
b Controller x clk patient laser

3.3

How? Lets try three flip-flops

b=1 gets stored in first D flipflop Then 2nd flip-flop on next cycle, cycle then 3rd flip-flop on flip flop next OR the three flip-flop outputs, so x should be 1 for three cycles
Digital Design 2e Copyright 2010 Frank Vahid
a

0 0 1
a

b clk

Bad job what if button pressed a second time during those 3 cycles?

24

12

04.10.2011

Need a Better Way to Design Sequential Circuits

Also bad because of ad hoc design process
How create other sequential circuits?

Need
A way to capture desired sequential behavior A way to convert such behavior to a sequential circuit
Step Step 1: Capture behavior Capture the function Description Create a truth table or equations, whichever is most natural for the given problem, to describe the desired behavior of each output of the combinational logic. This substep is only necessary if you captured the function using a truth table instead of equations. Create an equation for each output by ORing all the minterms for that output. Simplify the equations if desired. For each output, create a circuit corresponding to the outputs equation. (Sharing gates among multiple outputs is OK optionally.)

Like we had for designing combinational circuits

Digital Design 2e Copyright 2010 Frank Vahid

Step 2: Convert to circuit

2A: Create equations 2B: Implement as a gatebased circuit

25

Capturing Sequential Circuit Behavior as FSM

Outputs: x

Finite-State Machine (FSM)

Describes desired behavior of sequential circuit
Akin to Boolean equations for combinational behavior

x=0 Lo

clk^

x=1 Hi

List states, and transitions among states

Example: Toggle x every clock cycle Two states: Lo (x=0), and Hi (x=1) Transition from Lo to Hi or Hi to Hi, Lo, on rising clock edge (clk^) Arrow points to initial state (when circuit first starts)
Depicting multibit or other info in a timing diagram

clk^ Lo Hi Lo Hi Lo Hi Lo Hi

clk state Outputs: x

cycle 1

cycle 2

cycle 3

cycle 4

Lo

Hi

Lo

Hi

Lo or Lo

Hi

Digital Design 2e Copyright 2010 Frank Vahid

26
Hi

13

04.10.2011

FSM Example: Three Cycles High System

Want 0, 1, 1, 1, 0, 1, 1, 1, ...
For one clock cycle each
Outputs: x x=0 Off clk^ x=1 On1 clk^ clk^ x=1 On2 clk^ x=1 On3
a

Capture as FSM
Four states: 0, first 1, second 1, third 1 Transition on rising clock edge to next state

clk State Off On1On2On3 Off On1On2On3 Off Outputs: x

a

Digital Design 2e Copyright 2010 Frank Vahid

27

Three-Cycles High System with Button Input

Four states Wait in Off while b is 0 (b clk ) (b*clk^) When b is 1 (b*clk^), transition to On1
Sets x=1 Next two clock edges, transition to On2, then On3
Inputs: b x=0 Off b*clk ^ x=1 clk^ On1 b'*clk ^ Outputs: x clk^

x=1 On2

clk^

x=1 On3

clk Inputs: I t b State Off Off Off Off Off On1On2On3 Off Outputs: x

So x=1 for three cycles after button pressed

Digital Design 2e Copyright 2010 Frank Vahid

28

14

04.10.2011

FSM Simplification: Rising Clock Edges Implicit

Every edge ANDed with rising clock edge What if we wanted a transition without a rising edge
We dont consider such asynchronous FSMs less common, and advanced topic Only consider synchronous FSMs rising edge on every transition
Inputs: b; Outputs: x
x=0 Off b*clk ^ x=1 clk^ On1 b *clk^ clk^

x=1 On2

clk^

x=1 On3

Inputs: b; Outputs: x x=0 Off b x=1 x=1 On2 x=1 On3 b

a

Note: Transition with no associated condition thus transistions to next state on next clock cycle
Digital Design 2e Copyright 2010 Frank Vahid

On1

29

FSM Definition
FSM consists of
Set of states
Ex: {Off, On1, On2, On3}
Inputs: b; Outputs: x x=0 Off b x=1 On1 x=1 On2 x=1 On3 b

Set of inputs, set of outputs

Ex: Inputs: {b}, Outputs: {x}

Initial state
Ex: Off

Set of transitions
Each with condition Describes next states E H 5t Ex: Has transitions iti

We often draw FSM graphically, known as state diagram

Can also use table (state table), or textual languages

Set of actions
Sets outputs in each state Ex: x=0, x=1, x=1, and x=1
Digital Design 2e Copyright 2010 Frank Vahid

30

15

04.10.2011

FSM Example: Secure Car Key

Many new car keys include tiny computer chip
Wh key turned, cars computer When k t d t (under engine hood) requests identifier from key Key transmits identifier
Else, computer doesnt start car
r=0

Inputs: a; Outputs: r Wait a K1 r=1 a K2 r=1 K3 r=0 K4 r=1

FSM
Wait until computer requests ID p q (a=1) Transmit ID (in this case, 1 1 0 1)

Digital Design 2e Copyright 2010 Frank Vahid

31

FSM Example: Secure Car Key (cont.)

Nice feature of FSM
Can evaluate output behavior for different input sequence p q Timing diagrams show states and output values for different input waveforms
Wait r=0 a K1 r=1 a K2 r=1 K3 r=0 K4 r=1 Inputs: a; Outputs: r

Q: Determine states and r value for given input waveform:

clk Inputs a State Outputs r Wait Wait K1 K2 K3 K4 Wait Wait clk Inputs a State Output r Wait Wait K1 K2 K3 K4 Wait K1
a

Digital Design 2e Copyright 2010 Frank Vahid

32

16

04.10.2011

Ex: Earlier Flight-Attendant Call Button

Previously built using SR latch, then D flip-flop Capture desired bit storage behavior using FSM instead
Clear and precise description of desired behavior Well later convert to a circuit
Inputs: Call, Cncl L=0 Call' LightOff Call Outputs: L L=1 LightOn (Cncl*Call')' Cncl*Call'
Digital Design 2e Copyright 2010 Frank Vahid

Call button Cancel button b tt

Blue light Bit Storage

33

How To Capture Desired Behavior as FSM

List states
Give meaningful names show initial state names, Optionally add some transitions if they help

Create transitions
For each state, define all possible transitions leaving that state.

Refine the FSM

Execute the FSM mentally and make any needed improvements.

Digital Design 2e Copyright 2010 Frank Vahid

34

17

04.10.2011

FSM Capture Example: Code Detector

Unlock door (u=1) only when buttons pressed in sequence:
start then red blue start, red, blue, green, red
Start Red Green Blue Bl
a

s u r g b a Code detector

1
Door lock

Input from each button: s, r, g, b

Also, output a indicates that some colored button pressed
Wait u=0 s Start u=0 ar Red1 u=0
Digital Design 2e Copyright 2010 Frank Vahid

Wait for start button s' Wait for first colored button

Inputs: s,r,g,b,a Outputs: u

Capture as FSM p
List states
Some transitions included

ab

Blue u=0

ag

Green u=0

ar

Red2 u=1
35

FSM Capture Example: Code Detector

Capture as FSM
List states Create transitions
a

Start Red Green Blue Bl

s u r g b a Code detector Door lock

Wait u=0 s Start u=0 ar Red1 u=0

Digital Design 2e Copyright 2010 Frank Vahid

Inputs: s,r,g,b,a Outputs: u

a

s' a' ab

ar'

Blue u=0

ag

Green u=0

ar

Red2 u=1
36

18

04.10.2011

FSM Capture Example: Code Detector

Capture as FSM
List states Create transitions
Repeat for remaining states
a

Start Red Green Blue Bl

s u r g b a Code detector Door lock

Refine FSM
Mentally execute Works for normal sequence Wait Check unusual cases All colored buttons u=0 s pressed
Door opens! Change conditions: other buttons NOT pressed also

Inputs: s,r,g,b,a Outputs: u

s' a' ab a'

ar'

ab'

ag'

ar'

Start u=0 ar Red1 u=0

Blue u=0

ag a'

Green u=0

ar a'

Red2 u=1
37

Digital Design 2e Copyright 2010 Frank Vahid

FSM Capture Example: Code Detector

Start Red Green Blue Bl s u r g b a Code detector Door lock
a

Inputs: s,r,g,b,a Outputs: u Wait u=0 s Start u=0 arb'g' Red1

Digital Design 2e Copyright 2010 Frank Vahid

'g ')' rb

s' a'

)' 'g'

a(

')' )

abr'g' a'

Blue u=0

agr'b' a'

Green u=0

a(rb'g')

a(gr'b

a(

br

'

arb'g' a'

Red2 u=1
38

u=0

19

04.10.2011

Controller Design
Converting FSM to sequential circuit
Circuit called controller Standard controller architecture
State register stores encoding of current state
e.g., Off:00, On1:01, On2:10, On3:11

3.4

Laser timer FSM

Inputs: b; Outputs: x x=0 Off b x=1 On1 x=1 On2 x=1 On3 b

Combinational logic computes outputs and next state from inputs and current state Rising clock edge takes controller to next state
Controller I O FSM outputs

Controller for laser timer FSM

Laser timer controller b FSM inputs Combinational n1 logic l i n0 s1 s0 State register x FSM outputs

General form
a

FSM inputs

Combinational logic S m

clk
m

clk

m-bit state register N

Digital Design 2e Copyright 2010 Frank Vahid

39

Controller Design Process

Step Step 1: Capture the Capture FSM behavior 2A: Set up architecture 2B: Encode the states 2C: 2C Fill in i the truth table 2D: Implement combinational logic
Digital Design 2e Copyright 2010 Frank Vahid

Description Create an FSM that describes the desired behavior of the controller.
Use state register of appropriate width and combinational logic. The logics inputs are the state register bits and the FSM inputs; outputs are next state bits and the FSM outputs. Assign unique binary number (encoding) to each state. Usually use fewest bits, assign encoding to each state by counting up in binary. Translate FSM to truth table for combinational logic such that the logic will generate the outputs and next state signals for the given FSM. Ordering the inputs with state bits first makes the correspondence between the table and the FSM clear. Implement the combinational logic using any method.

Step 2: Convert to circuit

40

20

04.10.2011

Controller Design: Laser Timer Example

Step 1: Capture the FSM
Already done
Inputs: b; Outputs: x x=0 00 b Off
a

Step 2A: Set up architecture

2-bit state register (for 4 states) Input b, output x Next state signals n1, n0

b x=1 01 On1 x=1 10 On2 x=1 11 On3

Step 2B: Encode the states

Any encoding with each state unique will work

b Combinational n1 logic n0 s1 s0 clk State register

FSM outputs
a

Digital Design 2e Copyright 2010 Frank Vahid

FSM inputs

41

Controller Design: Laser Timer Example (cont)

Step 2C: Fill in truth table
Inputs: b; Outputs: x x=0 00 b O ff b x=1 01 On1 x=1 10 On2 x=1 11 On3
a

FSM outputs

FSM inputs

b Combinational n1 logic n0 s1 s0 clk State register

Digital Design 2e Copyright 2010 Frank Vahid

42

21

04.10.2011

Controller Design: Laser Timer Example (cont)

Step 2D: Implement combinational logic
FSM outputs FSM inputs

b Combinational n1 logic n0 s1 1 s0 0 clk State register

x = s1 + s0 (note that x=1 if s1=1 or s0=1) n1 = s1s0b + s1s0b + s1s0b + s1s0b s1 s0b s1 s0b s1s0 b s1s0 b n1 = s1s0 + s1s0 n0 = s1s0b + s1s0b + s1s0b n0 = s1s0b + s1s0
Digital Design 2e Copyright 2010 Frank Vahid

43

Controller Design: Laser Timer Example (cont)

FSM inputs

Step 2D: Implement combinational logic (cont)

b
b

Combinational Logic x
FSM outputs

x Combinational n1 logic n0 s1 s0

n1

clk

State register

n0

s1 clk

s0

State register

x = s1 + s0 n1 = s1s0 + s1s0 n0 = s1s0b + s1s0

Digital Design 2e Copyright 2010 Frank Vahid

44

22

04.10.2011

Understanding the Controllers Behavior

x=0
00 Off

x=0 b x=1
10 On2 00 Off

x=0 b x=1
10 On2 00 Off

b x=1
10 On2

x=1
01 On1

x=1
11 On3

x=1
01 On1

x=1
11 On3

x=1
01 On1

x=1
11 On3

b 0

0 0 0 0 0

x 0 n1 0

b 1

0 0 0 0 1

x 0 n1 0

b 1

0 1 1 0 0

x 1 n1 1
a

n0 0 0 clk s1 0 0 s0 0 0 state=00 clk s1 0 0 s0 0 1 state=00 0

n0 1 0 clk s1 0 1 s0 1 0 state=01

n0 0

clk Inputs: b Outputs: x

Digital Design 2e Copyright 2010 Frank Vahid

45

Controller Example:
Button Press Synchronizer
clk Inputs: bi cycle1 cycle2 cycle3 cycle4

bi

Button press synchronizer controller

bo

Outputs: bo

Want simple sequential circuit that converts button press to single cycle duration, regardless of length of time that button was actually pressed
We assumed such an ideal button press signal in earlier example, like the button in the laser timer controller
Digital Design 2e Copyright 2010 Frank Vahid

46

23

04.10.2011

Controller Example:
Button Press Synchronizer (cont)
FSM inputs: bi; FSM outputs: bo bi A bo=0 bi B bo=1 bi bi bi bi C bi bo=0
clk bi Combinational logic s1 1 s0 0 bo n1 n0 State register n1 = s1s0bi + s1s0bi s1 s0bi n0 = s1s0bi bo = s1s0bi + s1s0bi = s1s0 Combinational logic bo
a

FSM outputs

FSM inputs

Step 2A: Set up architecture

Step 1: Capture FSM

Combinational logic Inputs Outputs s1 s0 bi n1 n0 bo 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 1 1 0 0 0 0 1 1 1 0 0 0
bi

n1

FSM inputs: bi; FSM outputs: bo bi 00 bo=0 bi 01 bo=1 bi bi bi bi 10 bi bo=0

A B C unused

n0

s1 clk

s0 State register

Step 2B: Encode states

Step 2C: Fill in truth table

Digital Design 2e Copyright 2010 Frank Vahid

Step 2D: Implement combinational logic

47

Controller Example: Sequence Generator

Want generate sequence 0001, 0011, 1100, 1000, (repeat)
Each value for one clock cycle Common, e.g., to create pattern in 4 lights, or control magnets of a stepper motor
Inputs: none; Outputs: w,x,y,z wxyz=0001 A wxyz=1000 D
Combinational logic s1 s0
B wxyz=0011

w x y z n1 n0

Inputs: none; Outputs: w,x,y,z p ; p , ,y,

wxyz=0001 A wxyz=1000 D

00 01

11 10

B wxyz=0011

C wxyz=1100

clk

State register

C wxyz=1100

Step 1: Create FSM

Step 2A: Set up architecture

w = s1 x = s1s0 y = s1s0 z = s1 n1 = s1 xor s0 n0 = s0 s1 clk

Step 2B: Encode states

w x y z
a

s0 State register

n0

n1

Digital Design 2e Copyright 2010 Frank Vahid

Step 2C: Fill in truth table

Step 2D: Implement combinational logic 48

24

04.10.2011

Controller Example: Secure Car Key

Inputs: a; Outputs: r Wait r=0 a K1 r=1 a K2 r=1 K3 r=0 K4 r=1
a

(from earlier example)

St 1 tep

r
Combinational logic

Step 2A

n2 n1
n0

s2 s1 s0
clk

State register

Inputs: a; Outputs: r

000

Step 2B

r=0

001
r=1

010
r=1

011
r=0

100
r=1

Digital Design 2e Copyright 2010 Frank Vahid

Step 2C Well omit Step 2D 49

Converting a Circuit to FSM (Reverse Engineering)

2D: Circuit to eqns Step 1: FSM (get from table)
a

What does this circuit do?

x y z

y=s1 z = s1s0 n1=(s1 xor s0)x n0 (s1 s0 )x n0=(s1*s0)x

2C: Truth table

states
D C

Outputs:y, z A B yz=10 C yz=01

n1 n0 s1 clk s0
State register
x

yz=10 D yz=00

states with outputs

Inputs: x; Outputs:y, z x A yz=10 x B x C x yz=01 yz=10 10

Work backwards
2B: (Un)encode states Pick any state names you want
Digital Design 2e Copyright 2010 Frank Vahid

D yz=00

states with outputs and transitions

50

2A: Set up arch already done

25

04.10.2011

Reverse Engin. the D-flip-flop Flight Atten. Call Button

Call button Cancel button D Clk Q Q Blue light

2C: Truth table 2B: (Un)encode states

2A: Set up arch (nothing to do) Inputs: Call, Cncl L=0 LightOff Call Outputs : L L=1 LightOn Cncl'+Call Call'*Cncl 51

2D: Circuit to eqns L=Q D = Cncl'Q + Call (next state)

Don t Dont let the way the circuit is drawn confuse you; the combinational logic is everything outside the register

Step 1: FSM Call' (get from table)

Digital Design 2e Copyright 2010 Frank Vahid

Common Mistakes when Capturing FSMs

Non-exclusive transitions
a b ab=11 next state?
ab

Incomplete transitions
a

a ab what if ab=00?

a ab

a ab

Digital Design 2e Copyright 2010 Frank Vahid

52

26

04.10.2011

Verifying Correct Transition Properties

Can verify using Boolean algebra Answer:
a * ab

Only one condition true: AND of each condition pair (for = (a * a) * b transitions leaving a state) should equal 0 proves p g ) q p pair = 0 * b =0 can never simultaneously be true a OK! One condition true: OR of all conditions of transitions leaving a state) should equal 1 proves at least one a + ab = a*(1+b) + ab condition must be true = a + ab + ab = a + (a+a)b Example
a ab
=a+b Fails! Might not be 1 (i e a=0 (i.e., a 0, b=0)

Q: For shown transitions, prove whether: * Only one condition true (AND of each pair is always 0) * One condition true (OR of all transitions is always 1)
Digital Design 2e Copyright 2010 Frank Vahid

53

Verifying transition properties

Recall code detector FSM
Wait We fixed a problem with the u=0 s transition conditions Do the transitions obey the two Start required transition properties? u=0 ar s
a

a ab a Blue u=0 ag a Green u=0 ar a Red2 u=1

Consider transitions of state Start, and the only one true property

Red1 u=0

ar * a a * a(r+b+g) = (a*a)r = 0*r =0 =0

A: ar should be arbg Fails! Means that two of Starts (likewise for ab, ag, ar) transitions could be true
Digital Design 2e Copyright 2010 Frank Vahid

ar * a(r+b+g) Intuitively: press red and blue = (a*a)*(r+b+g) = 0*(r+b+g) buttons at same time: conditions = (a*a)*r*(r+b+g) = a*r*(r+b+g) ar, and a(r+b+g) will both be true. true Which one should be = arr+arb+arg + b+ taken? = 0 + arb+arg a Q: How to solve? = arb + arg = ar(b+g)

Note: As evidence the pitfall is common, we admit the mistake was not initially intentional. A reviewer of an earlier edition of the book caught it. 54

27

04.10.2011

Simplifying Notations
FSMs
Assume unassigned output implicitly assigned 0
a=0 b=1 c=0 a=0 b=0 c=1
a

Sequential circuits
Assume unconnected clock inputs connected to same external clock

clk

b=1

b=0 c=1

Digital Design 2e Copyright 2010 Frank Vahid

55

Mathematical Formalisms
Two formalisms to capture behavior thus far
Boolean equations for combinational circuit design FSMs for sequential circuit design

Not necessary
But tremendously beneficial
Structured methodology Correct circuits Automated design, automated verification, many more advantages

Digital Design 2e Copyright 2010 Frank Vahid

56

28

04.10.2011

More on Flip-Flops and Controllers

Non-ideal flip-flop behavior
Cant change flip-flop input too close to clock edge Setup time: time D must be stable before edge
Else, stable value not present at internal latch
clk D

3.5

Hold time: time D must be held stable after edge

Else, new value doesnt have time to loop around and stabilize in internal latch
Setup time violation
D latch D S Q C u Q u R R Q Q
Digital Design 2e Copyright 2010 Frank Vahid

setup time clk D

C D S 2 3 4 7 5 6 1

hold time

Leads to oscillation!

57

Metastability
Violating setup/hold time can lead to bad situation
Metastable state: Any flip-flop state other than stable 1 or 0
Eventually settles to either, but we dont know which

clk
D

setup time violation Q metastable state

ai

For internal circuits, we can make sure to observe setup time But what if input is from external (asynchronous) source, e.g., button press?

Partial solution
Insert synchronizer flip-flop for asynchronous input
Special flip-flop with very small setup/hold time
ai
a

Digital Design 2e Copyright 2010 Frank Vahid

synchronizer

58

29

04.10.2011

Metastability
Synchronizer flip-flop doesnt completely prevent metastability
But reduces probability of metastability in dozens/hundreds of internal flipflops storing important values Adding more synchronizer flip-flops further reduces probability
First ff likely stable before next clock; second ff very unlikely to have setup time violated

Drawback: Change on input is delayed to internal flip-flops

By three clock cycles in below circuit
Probability of flip-flop being metastable is: low ai very low very very low incredibly low
a

synchronizers
Digital Design 2e Copyright 2010 Frank Vahid

59

Example of Reducing Metastability Probability

Recall earlier secure car key controller
Inputs: a; Outputs: r Wait r=0 a K1 r=1 a K2 r=1 K3 r=0 K4 r=1
outputs

Adding synchronizer flip-flop reduces metastability probability in state register, at expense of 1 cycle delay
Original a D flip-flop a Combinational n2 logic n1 n0 s2 clk s1 s0 r

a
FSM inputs

r
Combinational logic

n2 n1
n0 0

s2 s1 s0
clk

State register

State register

Digital Design 2e Copyright 2010 Frank Vahid

60

30

04.10.2011

Flip-Flop Set and Reset Inputs

Some flip-flops have additional reset/set inputs
Synchronous
Synch. reset: Clears Q to 0 on next clock edge Synch. set: Sets Q to 1 on next clock edge Have priority over D input
D Q Q
D Q Q
D AR Q Q

AR

AS

cycle 1 clk

cycle 2

cycle 3

cycle 4

D AR

Asynchronous
Asynch. reset: Clear Q to 0, y , independently of clock
Example timing diagram shown

Asynch. set: set Q to 1, indep. of clock

Digital Design 2e Copyright 2010 Frank Vahid

61

Initial State of a Controller

All our FSMs had initial state
But our sequential circuits did not Can accomplish using flip-flops flip flops with reset/set inputs
Shown circuit initializes flip-flops to 01
Inputs: x; Outputs: b x=0 Off b x=1 On1
b Combinational logic s1 State register D Q Q s0

b x=1 On2 x=1 On3

x n1 n0

Designer must ensure resetcontroller input is 1 during power up of circuit

By electronic circuit design
clk

Q Q

Controller with reset to initial state 01 (assuming state Off was encoded as 01).
Digital Design 2e Copyright 2010 Frank Vahid

reset controller

62

31

04.10.2011

Glitching
Glitch: Temporary values on outputs that appear soon after input changes, before stable new output values g glitching outputs may g p y Designer must determine whether g pose a problem
If so, may consider adding flip-flops to outputs
Delays output by one clock cycle, but may be OK Called registered output
b x Combinational n1 logic n0 s1 s0 State register D flip-flop xr

Laser timer controller with flipflop to prevent glitches on x from unintentionally turning on laser
63

Digital Design 2e Copyright 2010 Frank Vahid

Glitching
Alternative registered output approach, avoid 1 cycle delay:
Add extra state register bit for each output Connect output directly to its bit No logic between state register flip-flop and output, hence no glitches
Inputs: b Outputs: x x=0 000 b Off b x=1 011 On1 x=1 101 On2 x=1 111 On3

x Combinational n1 n0 logic nx s1 s0 sx State register

Digital Design 2e Copyright 2010 Frank Vahid

But, uses more flip-flops, plus more logic to compute next state

64

32

04.10.2011

Product Profile: Pacemaker

Digital Design 2e Copyright 2010 Frank Vahid

65

Product Profile: Pacemaker

Pacemaker Osc ra s Controller p t z s Wait t=0 p=0 sz Pace p=1 t=0 Timer (counts down from 0.8s) rv lv ResetTimer la

Inputs: s z s, Outputs: t, p t=1, p=0 sz

Basic pacemaker

Digital Design 2e Copyright 2010 Frank Vahid

66

33

04.10.2011

Product Profile: Pacemaker

Pacemaker Osc right atrium left atrium sa pa sv pv ta za tv zv PaceV right left ventricle ventricle pv=1 sv*zv sv sa WaitV tv=1 ResetTimerV sv*zv Inputs: sa, za, sv, zv Outputs: pa ta pv tv pa, ta, pv, ta=1 ResetTimerA WaitA sa*za

Controller

sa*za PaceA

pa=1

TimerA

TimerV

Atrioventricular pacemaker
Digital Design 2e Copyright 2010 Frank Vahid

67

Chapter Summary
Sequential circuits
Have state

Created robust bit-storage device: D flip-flop

Put several together to build register, which we used to store state

Defined FSM model to capture sequential behavior

Using mathematical models Boolean equations for combinational circuit, and FSMs for sequential circuits is important

Defined Capture/Convert process for sequential circuit design

Converted FSM to standard controller architecture

So now we know how to build the class of sequential circuits known as controllers
Digital Design 2e Copyright 2010 Frank Vahid

68

34