Finite State Machines
Finite State Machines
? Design methodology for sequential logic -- identify distinct states -- create state transition diagram -- choose state encoding -- write combinational Verilog for next-state logic -- write combinational Verilog for output signals
? Lots of examples
6.111 Fall 2017
Lecture 6
1
Finite State Machines
? Finite State Machines (FSMs) are a useful abstraction for sequential circuits with centralized "states" of operation
? At each clock edge, combinational logic computes outputs and next state as a function of inputs and present state
inputs +
present state
n
Combinational Logic
outputs +
next state
n
Q
D
Registers
CLK
6.111 Fall 2017
Lecture 6
2
Two Types of FSMs
Moore and Mealy FSMs : different output generation
? Moore FSM:
inputs
x0...xn
Comb. Logic
? Mealy FSM:
inputs
x0...xn
Comb. Logic
next state
S+
n
CLK
D
Q
Registers
present state S
Comb. Logic
n
direct combinational path!
S+
D
Q
n
Registers
CLK
S
Comb. Logic
n
outputs
yk = fk(S)
outputs
yk = fk(S, x0...xn)
6.111 Fall 2017
Lecture 6
3
Design Example: Level-to-Pulse
? A level-to-pulse converter produces a singlecycle pulse each time its input goes high.
? It's a synchronous rising-edge detector. ? Sample uses:
? Buttons and switches pressed by humans for arbitrary periods of time
? Single-cycle enable signals for counters
Whenever input L goes from low to high...
Level to L Pulse P
Converter
CLK
6.111 Fall 2017
Lecture 6
...output P produces a single pulse, one clock
period wide.
4
Step 1: State Transition Diagram
? Block diagram of desired system:
Synchronizer
unsynchronized user input
CLK
DQ
DQ
Edge Detector
Level to L Pulse P
FSM
? State transition diagram is a useful FSM representation and design aid:
"if L=1 at the clock edge, then jump to state 01."
L=1
L=1
Binary values of states
00
L=0
Low input,
Waiting for rise
P = 0
01
Edge Detected!
P = 1
L=0
"if L=0 at the clock edge, then stay in state
00."
1111
High input, Waiting for fall
L=1
P = 0
L=0
This is the output that results from this state. (Moore or Mealy?)
6.111 Fall 2017
Lecture 6
5
Valid State Transition Diagrams
L=1
L=1
00
L=0
Low input,
Waiting for rise
P = 0
01
Edge Detected!
P = 1
11
High input, Waiting for fall
L=1
P = 0
L=0
L=0
? Arcs leaving a state are mutually exclusive, i.e., for any combination input values there's at most one applicable arc
? Arcs leaving a state are collectively exhaustive, i.e., for any combination of input values there's at least one applicable arc
? So for each state: for any combination of input values there's exactly one applicable arc
? Often a starting state is specified
? Each state specifies values for all outputs (Moore)
6.111 Fall 2017
Lecture 6
6
Choosing State Representation
Choice #1: binary encoding
For N states, use ceil(log2N) bits to encode the state with each state represented by a unique combination of the bits. Tradeoffs: most efficient use of state registers, but requires more complicated combinational logic to detect when in a particular state.
Choice #2: "one-hot" encoding
For N states, use N bits to encode the state where the bit corresponding to the current state is 1, all the others 0. Tradeoffs: more state registers, but often much less combinational logic since state decoding is trivial.
6.111 Fall 2017
Lecture 6
7
Step 2: Logic Derivation
Transition diagram is readily converted to a state transition table (just a truth table)
L=1
L=1
L=0
00
Low input,
Waiting for rise
P = 0
01
Edge Detected!
P = 1
L=0
11
L=1
High input,
Waiting for fall
P = 0
L=0
Current State
In
Next State
Out
S1 S0 L S1+ S0+ P
0 00 0 0 0
0 01 0 1 0
0 10 0 0 1
0 11 1 1 1
1 10 0 0 0
1 11 1 1 0
? Combinational logic may be derived using Karnaugh maps
S1S0 for S1+:
L 00 01 11 10
0000X
1 011X
S1S0 for S0+:
L 00 01 11 10 0000X 1 111X
L Comb. Logic
S+
D
Q
n Registers
CLK
S1+ = LS0
S
S0+ = L
P Comb. Logic
n
P = S1S0
S0S1
for P:
01
00X
1 10
6.111 Fall 2017
Lecture 6
8
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- how the wealth was won factors shares as market
- developing a teaching philosophy ed
- application of deep learning to algorithmic trading
- research paper effects of internet on the academic
- grade 6 history term 3 2017
- sample paper test 05 term i 2021
- grade 3 english language arts practice test
- mathematics grade 11 western cape
- information and communication technology paper 1 sample
- past paper november 2017 section 1
Related searches
- finite integral
- finite volume method cfd
- finite difference and finite element
- solidworks finite element analysis tutorial
- finite element analysis basics
- finite element method book pdf
- finite element analysis book pdf
- finite element analysis textbook pdf
- finite element structural analysis pdf
- finite element analysis
- finite element analysis tutorial pdf
- finite element analysis training