Finite State Machine with Datapath

Finite State Machine with Datapath

Martin Schoeberl

Technical University of Denmark Embedded Systems Engineering

March 17, 2022

1 / 39

Overview

I ReviewVec

I Counter based circuits

I Finite-state machines (FSMs) I FSM with Datapath

Last Lab

I A table to describe a 7-segment decoder I Did you finish the exercises?

I Did you run it on your Basys3 board?

3 / 39

Vectors and Bundles

I You where skeptic on vectors last week I Let us repeat it today

I A vector (Vec) is an indexable collection I Similar to an array in Java

I Selecting an element for read is a mulitplexer

I Selecting an element to write is an input to a multiplexer or a register enable

I Bundles are constructs to structure data

I Similar to a class in Java or a record in C/VHDL

A Vector is a Multiplexer

I Follwing code is a 3:1 multiplexer val vec = Wire ( Vec (3 , UInt (8. W))) vec (0) := x

vec (1) := y vec (2) := z

val muxOut = vec ( select )

x

muxOut

select

y 0 1

z 2

5 / 39

A Vector of Registers

I Following code shows vectors and registers in action

val regVec = Reg ( Vec (3 , UInt (8. W))) val dout = regVec ( rdIdx )

regVec ( wrIdx ) := din

I Can you draw the schematic?

Schematic of the Reg of Vec

en en en

din dout

0 rdIdx

2 1 decoder

wrIdx

7 / 39

Generating Timing with Counters

I Generate atickat a lower frequency I We used it in Lab 1 for the blinking LED I We will use it again in next week’s lab

I Use it for driving the display multiplexing at 1 kHz

clock reset tick

counter ^{0 1 2 0 1 2 0 1}

The Tick Generation

val tickCounterReg = RegInit (0. U (32. W)) val tick = tickCounterReg === (N -1) .U tickCounterReg := tickCounterReg + 1. U when ( tick ) {

tickCounterReg := 0. U }

9 / 39

Using the Tick

I A counter running at aslower frequency I By using thetickas an enable signal

val lowFrequCntReg = RegInit (0. U (4. W)) when ( tick ) {

lowFrequCntReg := lowFrequCntReg + 1. U }

The Slow Counter

I Incremented everytick

clock reset tick

slow cnt ^{0 1 2}

11 / 39

What is the Use of This Slow Counter?

I This will be your lab exercise next week I Is a preparation for the display multiplexing

I Then you need to generate a timing of 1 kHz (1 ms)

Finite-State Machine (FSM)

I Has a register that contains the state I Has a function to computer the next state

I Depending on current state and input I Has an output depending on the state

I And maybe on the input as well

I Every synchronous circuit can be considered a finite state machine

I However, sometimes the state space is a little bit too large

13 / 39

Basic Finite-State Machine

I A state register

I Two combinational blocks I Next state logic I Output logic

in

state

nextState Next

state logic

Ouput logic out

State Diagrams are Convenient

bad event

green orange red/

ring bell bad event

clear reset

clear

I States and transitions depending on input values I Example is a simple alarm FSM

I Nice visualization

I Will not work for large FSMs

15 / 39

A Mealy FSM

I Similar to the former FSM I Output also depends in the input I Output isfaster

I Less composable as we may have combinational circles

in

state

nextState Next

state

logic Output

logic out

The Mealy FSM for the Rising Edge

I Output is also part of the transition arrows

zero one

1/1 reset

0/0

0/0 1/0

17 / 39

State Diagram for the Moore Rising Edge Detection

I We need three states

1

zero 0

puls 1

one 0 1

0 reset

0

Comparing with a Timing Diagram

I Moore is delayed by one clock cycle compared to Mealy

clock din risingEdge Mealy risingEdge Moore

19 / 39

What is Better?

I It depends ;-)

I Moore is on the save side I Moore is composable I Mealy hasfasterreaction I Both are tools in you toolbox

I Keep it simple with your vending machine and use a Moore FSM

FSM with Datapath

I A type of computing machine

I Consists of a finite-state machine (FSM) and a datapath I The FSM is the master (the controller) of the datapath I The datapath has computing elements

I E.g., adder, incrementer, constants, multiplexers, ...

I The datapath has storage elements (registers) I E.g., sum of money payed, count of something, ...

21 / 39

FSM-Datapath Interaction

I The FSM controls the datapath I For example, add 2 to the sum I By controlling multiplexers

I For example, select how much to add I Not adding means selecting 0 to add I Which value goes where

I The FSM logic also depends on datapath output

I Is there enough money payed to release a can of soda?

I FSM and datapath interact

Popcount Example

I An FSMD that computes the popcount I Also called the Hamming weight I Compute the number of ‘1’s in a word I Input is the data word

I Output is the count

I Code available atPopCount.scala

23 / 39

Popcount Block Diagram

dinValid popCntValid

FSM

din popCnt

popCntReady dinReady

Datapath

Popcount Connection

I Inputdinand outputpopCount I Both connected to the datapath I We need some handshaking I For data input and for count

output

dinValid popCntValid

FSM

din popCnt

popCntReady dinReady

Datapath

25 / 39

Popcount Handshake

I We use a ready-valid handshake I When data is available valid is

asserted

I When the receiver can accept data ready is asserted

I Transfer takes place when both are asserted

I Draw the ready/valid handshake on the black board

dinValid popCntValid

FSM

din popCnt

popCntReady dinReady

Datapath

The FSM

Count Idle

Done

Valid

Finished Result read

I A Very Simple FSM

I Two transitions depend on input/output handshake I One transition on the datapath output

27 / 39

The Datapath

+ din shf

0 0

cnt count

Let’s Explore the Code

I InPopCount.scala

29 / 39

Usage of an FSMD

I Maybe the main part your vending machine is an FSMD?

Functions

I Circuits can be encapsulated in functions I Eachfunction callgenerates hardware I A function is defined withdefname I Similar to methods in Java

I Simple functions can be a single line

def adder( v1 : UInt , v2 : UInt ) = v1 + v2 val add1 = adder (a , b)

val add2 = adder (c , d)

31 / 39

More Function Examples

I Functions can also contain registers

def addSub( add : Bool , a: UInt , b: UInt ) = Mux (add , a + b , a - b)

val res = addSub ( cond , a , b)

def rising(d: Bool ) = d && ! RegNext (d) val edge = rising ( cond )

The Counter as a Function

I Longer functions in curly brackets I Last value is the return value

def counter(n: UInt ) = {

val cntReg = RegInit (0. U (8. W)) cntReg := cntReg + 1. U

when ( cntReg === n) { cntReg := 0. U }

cntReg }

val counter100 = counter (100. U)

33 / 39

Functional Abstraction

I Functions for repeated pieces of logic I May contain state

I Functions may returnhardware I More lightweight than aModule

Parameterization

class ParamChannel(n: Int ) extends Bundle { val data = Input ( UInt (n.W))

val ready = Output ( Bool () ) val valid = Input ( Bool () ) }

val ch32 = new ParamChannel (32)

I Bundles and modules can be parametrized I Pass a parameter in the constructor

35 / 39

A Module with a Parameter

class ParamAdder(n: Int ) extends Module { val io = IO (new Bundle {

val a = Input ( UInt (n.W)) val b = Input ( UInt (n.W)) val c = Output ( UInt (n.W)) })

io .c := io .a + io .b }

I Parameter can also be a Chisel type

Use the Parameter

val add8 = Module (new ParamAdder (8) ) val add16 = Module (new ParamAdder (16) )

I Can be used for the display multiplexing configuration I Different maximum value for the counter for the simulation

and for the FPGA

37 / 39

Today’s Lab

I Paper & pencil exercises I Exercises on FSMs I From the Dally book

I Just sketch the Chisel code I On paper or in a plain text editor

I As usual, show and discuss your solution with a TA

Summary

I Counters are used to generate timing

I An FSM can control a datapath, which is an FSMD I An FSMD is a computing machine

I Functions to structure your code

39 / 39