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

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download