SEQUENTIAL DESIGN
Mr. Amit Kumar
Latches VS Flip Flop
D Q
Level-sensitive latch
holds value when clock is low a b
D Q D Q
Transparent when clock is high
What does it take to build a
consistent timing methodology in
with only latches? clk
Very hard! All stages transparent
a
at same time.
Require that minimum propagation b
delay is greater than high phase of
the clock (duty period)
Abstraction of State Elements
Divide circuit into combinational logic and state
Localize feedback loops and make it easy to break
cycles
Implementation of storage elements leads to various
forms of sequential logic
Inputs Outputs
Combinational
Logic
State Inputs State Outputs
Storage Elements
Forms of Sequential Logic
Asynchronous sequential logic state changes
occur whenever state inputs change (elements
may be simple wires or delay elements)
Synchronous sequential logic state changes
occur in lock step across all storage elements
(using a periodic waveform - the clock)
Clock
Finite State Machine Representations
States: determined by possible values in sequential
storage elements
Transitions: change of state
Clock: controls when state can change by controlling
storage elements
001 010 111
In = 1 In = 0
In = 0
100 110
In = 1
Sequential Logic
Sequences through a series of states
Based on sequence of values on input signals
Clock period defines elements of sequence
Can Any Sequential System be Represented
with a State Diagram?
Shift Register
Input value shown
OUT1 OUT2 OUT3
on transition arcs
Output values shown
within state node IN D Q D Q D Q
CLK
1
100 110
1 0 1 1
1
0 000 1 010 101 0 111 1
0
0 0 1 0
001 011
0
Two Kinds of FSMs
Moore Machine vs Mealy Machine
Output (t) =
Output (t) = G( state(t))
G( state(t), Input )
Input
Input
state
state
Combinational
Logic
state(t+1) = F ( state(t), input(t)) state(t+1) = F ( state(t), input)
Input / Out
Input State
State / out
Counters are Simple Finite State Machines
Counters
Proceed thru well-defined state sequence in response to enable
Many types of counters: binary, BCD, Gray-code
3-bit up-counter: 000, 001, 010, 011, 100, 101, 110, 111, 000, ...
3-bit down-counter: 111, 110, 101, 100, 011, 010, 001, 000, 111,
...
001 010 011
000 3-bit up-counter 100
111 110 101
Verilog Upcounter
module binary_cntr (q, clk)
inputs clk;
outputs [2:0] q;
reg [2:0] q;
reg [2:0] p;
always @(q) //Calculate next state
case (q)
3b000: p = 3b001;
3b001: p = 3b010;
3b111: p = 3b000;
endcase
always @(posedge clk) //next becomes current state
q <= p;
endmodule
How Do We Turn a State Diagram into Logic?
Counter
Three flip-flops to hold state
Logic to compute next state
Clock signal controls when flip-flop memory can change
Wait long enough for combinational logic to compute new value
Don't wait too long as that is low performance
OUT1 OUT2 OUT3
D Q D Q D Q
CLK
"1"
FSM Design Procedure
Start with counters
Simple because output is just state
Simple because no choice of next state based on input
State diagram to state transition table
Tabular form of state diagram
Like a truth-table
State encoding
Decide on representation of states
For counters it is simple: just its value
Implementation
Flip-flop for each state bit
Combinational logic based on encoding
FSM Design Procedure: State Diagram to
Encoded State Transition Table
Tabular form of state diagram
Like a truth-table (specify output for all input
combinations)
Encoding of states: easy for counters just use
value
current state next state
001 010 011 0 000 001 1
1 001 010 2
2 010 011 3
000 3-bit up-counter 100
3 011 100 4
4 100 101 5
111 110 101 5 101 110 6
6 110 111 7
7 111 000 0
Implementation
D flip-flop for each state bit
Combinational logic based on encoding
C3 C2 C1 N3 N2 N1 notation to show
function represent
0 0 0 0 0 1
input to D-FF
0 0 1 0 1 0
0 1 0 0 1 1 N1 := C1'
0 1 1 1 0 0 N2 := C1C2' + C1'C2
1 0 0 1 0 1 := C1 xor C2
N3 := C1C2C3' + C1'C3 + C2'C3
1 0 1 1 1 0
:= C1C2C3' + (C1' + C2')C3
1 1 0 1 1 1 := (C1C2) xor C3
1 1 1 0 0 0
N3 C3 N2 C3 N1 C3
0 0 1 1 0 1 1 0 1 1 1 1
C1 0 1 0 1 C1 1 0 0 1 C1 0 0 0 0
C2 C2 C2
Task
Implement the same design using JK Flip
Flop
Project 1: Parity Checker FSM
State Transition
Diagram
circuit is in one of two
states.
transition on each
cycle with each new
input, over exactly one
arc (edge).
Output depends on
which state the circuit
is in.
State Transition Table
Invent a code to represent states:
present state (ps) OUT IN next state (ns) Derive logic equations
0 0 0 0 from table (how?):
0 0 1 1
OUT = PS
1 1 0 1
1 1 1 0 NS = PS xor IN
Formal Design Process
Logic equations from table:
OUT = PS Review of Design Steps:
NS = PS xor IN 1. Circuit functional specification
2. State Transition Diagram
Circuit Diagram: 3. Symbolic State Transition Table
4. Encoded State Transition Table
5. Derive Logic Equations
6. Circuit Diagram
ps ns FFs for state
CL for NS and OUT
XOR gate for ns calculation
DFF to hold present state
no logic needed for output
Project 2: Door Lock System
Door combination lock:
punch in 3 values in sequence and the door
opens; if there is an error the lock must be reset;
once the door opens the lock must be reset
inputs: sequence of input values, reset
outputs: door open/close
memory: must remember combination
or always have it available as an input
Solution
Abstract control
Finite-state diagram
States: 5 states
represent point in execution of machine
each state has outputs
Transitions: 6 from state to state, 5 self transitions, 1 global
changes of state occur when clock says its ok
based on value of inputs
Inputs: reset, new, results of comparisons
Output: open/closed
Solved FSM
ERR
closed
C1!=value
C2!=value C3!=value
& new
& new & new
S1 S2 S3 OPEN
reset closed closed closed open
C1=value C2=value C3=value
& new & new & new
not new not new not new
Contd..
Finite-state machine
generate state table (much like a truth-table)
ERR
closed
not equal not equal
& new not equal
& new
Symbolic states S1 S2 S3
& new
OPEN
reset closed closed closed
open
mux=C1 equal mux=C2 equal mux=C3 equal
& new & new & new
not new not new not new
next
reset new equal state state mux open/closed
1 S1 C1 closed
0 0 S1 S1 C1 closed
0 1 0 S1 ERR closed
0 1 1 S1 S2 C2 closed
0 0 S2 S2 C2 closed
0 1 0 S2 ERR closed
0 1 1 S2 S3 C3 closed
0 0 S3 S3 C3 closed
0 1 0 S3 ERR closed
0 1 1 S3 OPEN closed
0 OPEN OPEN open
0 ERR ERR closed
Encoding of States
Encode state table
state can be: S1, S2, S3, OPEN, or ERR
needs at least 3 bits to encode: 000, 001, 010, 011, 100
and as many as 5: 00001, 00010, 00100, 01000, 10000
choose 4 bits: 0001, 0010, 0100, 1000, 0000
Encode outputs
output mux can be: C1, C2, or C3
needs 2 to 3 bits to encode
choose 3 bits: 001, 010, 100
output open/closed can be: open or closed
needs 1 or 2 bits to encode
choose 1 bits: 1, 0
Encoding of States
Encode state table
state can be: S1, S2, S3, OPEN, or ERR
choose 4 bits: 0001, 0010, 0100, 1000, 0000
output mux can be: C1, C2, or C3
choose 3 bits: 001, 010, 100
output open/closed can be: open or closed
choose 1 bits: 1, 0
next
reset new equal state state mux open/closed
1 0001 001 0
0 0 0001 0001 001 0
0 1 0 0001 0000 0
good choice of encoding!
0 1 1 0001 0010 010 0
0 0 0010 0010 010 0
0 1 0 0010 0000 0 mux is identical to
0 1 1 0010 0100 100 0 last 3 bits of next state
0 0 0100 0100 100 0
0 1 0 0100 0000 0 open/closed is
0 1 1 0100 1000 1 identical to first bit
0 1000 1000 1 of state
0 0000 0000 0
State Minimization
Fewer states may mean fewer state variables
High-level synthesis may generate many redundant states
Two state are equivalent if they are impossible to distinguish from the
outputs of the FSM, i. e., for any input sequence the outputs are the
same
Two conditions for two states to be equivalent:
1) Output must be the same in both states
2) Must transition to equivalent states for all input combinations
Sequential Logic Implementation Summary
Models for representing sequential circuits
Abstraction of sequential elements
Finite state machines and their state diagrams
Inputs/outputs
Mealy, Moore, and synchronous Mealy machines
Finite state machine design procedure
Deriving state diagram
Deriving state transition table
Determining next state and output functions
Implementing combinational logic
