Finite State Machine With Datapath

Finite State Machine with DatapathMartin SchoeberlTechnical University of DenmarkEmbedded Systems EngineeringMarch 17, 20221 / 39

OverviewI Review VecI Counter based circuitsI Finite-state machines (FSMs)I FSM with Datapath2 / 39

Last LabI A table to describe a 7-segment decoderI Did you finish the exercises?I Did you run it on your Basys3 board?3 / 39

Vectors and BundlesI You where skeptic on vectors last weekI Let us repeat it todayI A vector (Vec) is an indexable collectionI Similar to an array in JavaI Selecting an element for read is a mulitplexerI Selecting an element to write is an input to a multiplexer ora register enableI Bundles are constructs to structure dataI Similar to a class in Java or a record in C/VHDL4 / 39

A Vector is a MultiplexerI Follwing code is a 3:1 multiplexerval vec Wire(Vec (3, UInt (8.W)))vec (0) : xvec (1) : yvec (2) : zval muxOut vec( select )selectx0y1z2muxOut5 / 39

A Vector of RegistersI Following code shows vectors and registers in actionval regVec Reg(Vec (3, UInt (8.W)))val dout regVec ( rdIdx )regVec ( wrIdx ) : dinI Can you draw the schematic?6 / 39

Schematic of the Reg of VecenrdIdxwrIdxdecoderendin01dout2en7 / 39

Generating Timing with CountersI Generate a tick at a lower frequencyI We used it in Lab 1 for the blinking LEDI We will use it again in next week’s labI Use it for driving the display multiplexing at 1 kHzclockresettickcounter012012018 / 39

The Tick Generationval tickCounterReg RegInit (0.U(32.W))val tick tickCounterReg (N -1).UtickCounterReg : tickCounterReg 1.Uwhen (tick) {tickCounterReg : 0.U}9 / 39

Using the TickI A counter running at a slower frequencyI By using the tick as an enable signalval lowFrequCntReg RegInit (0.U(4.W))when (tick) {lowFrequCntReg : lowFrequCntReg 1.U}10 / 39

The Slow CounterI Incremented every tickclockresettickslow cnt01211 / 39

What is the Use of This Slow Counter?I This will be your lab exercise next weekI Is a preparation for the display multiplexingI Then you need to generate a timing of 1 kHz (1 ms)12 / 39

Finite-State Machine (FSM)I Has a register that contains the stateI Has a function to computer the next stateI Depending on current state and inputI Has an output depending on the stateI And maybe on the input as wellI Every synchronous circuit can be considered a finite statemachineI However, sometimes the state space is a little bit too large13 / 39

Basic Finite-State MachineI A state registerI Two combinational blocksI Next state logicI Output logicstateNextstatelogicnextStateOuputlogicoutin14 / 39

State Diagrams are Convenientbad eventresetgreenbad eventorangered/ring bellclearclearI States and transitions depending on input valuesI Example is a simple alarm FSMI Nice visualizationI Will not work for large FSMs15 / 39

A Mealy FSMI Similar to the former FSMI Output also depends in the inputI Output is fasterI Less composable as we may have combinational t16 / 39

The Mealy FSM for the Rising EdgeI Output is also part of the transition arrows0/0reset1/01/1zeroone0/017 / 39

State Diagram for the Moore Rising Edge DetectionI We need three states1resetzero01puls1one00018 / 39

Comparing with a Timing DiagramI Moore is delayed by one clock cycle compared to MealyclockdinrisingEdge MealyrisingEdge Moore19 / 39

What is Better?I It depends ;-)I Moore is on the save sideI Moore is composableI Mealy has faster reactionI Both are tools in you toolboxI Keep it simple with your vending machine and use a MooreFSM20 / 39

FSM with DatapathI A type of computing machineI Consists of a finite-state machine (FSM) and a datapathI The FSM is the master (the controller) of the datapathI The datapath has computing elementsI 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 InteractionI The FSM controls the datapathI For example, add 2 to the sumI By controlling multiplexersI For example, select how much to addI Not adding means selecting 0 to addI Which value goes whereI The FSM logic also depends on datapath outputI Is there enough money payed to release a can of soda?I FSM and datapath interact22 / 39

Popcount ExampleI An FSMD that computes the popcountI Also called the Hamming weightI Compute the number of ‘1’s in a wordI Input is the data wordI Output is the countI Code available at PopCount.scala23 / 39

Popcount Block pCntReadypopCnt24 / 39

Popcount ConnectionI Input din and output popCountI Both connected to the datapathI We need some handshakingI For data input and for thpopCntReadypopCnt25 / 39

Popcount HandshakeI We use a ready-valid handshakeI When data is available valid isassertedI When the receiver can acceptdata ready is assertedI Transfer takes place when bothare assertedI Draw the ready/valid handshakeon the black ntReadypopCnt26 / 39

The FSMIdleValidResult readDoneCountFinishedI A Very Simple FSMI Two transitions depend on input/output handshakeI One transition on the datapath output27 / 39

The Datapath0din0shfcntcount 28 / 39

Let’s Explore the CodeI In PopCount.scala29 / 39

Usage of an FSMDI Maybe the main part your vending machine is an FSMD?30 / 39

FunctionsI Circuits can be encapsulated in functionsI Each function call generates hardwareI A function is defined with def nameI Similar to methods in JavaI Simple functions can be a single linedef adder (v1: UInt , v2: UInt) v1 v2val add1 adder (a, b)val add2 adder (c, d)31 / 39

More Function ExamplesI Functions can also contain registersdef 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)32 / 39

The Counter as a FunctionI Longer functions in curly bracketsI Last value is the return valuedef counter (n: UInt) {val cntReg RegInit (0.U(8.W))cntReg : cntReg 1.Uwhen( cntReg n) {cntReg : 0.U}cntReg}val counter100 counter (100. U)33 / 39

Functional AbstractionI Functions for repeated pieces of logicI May contain stateI Functions may return hardwareI More lightweight than a Module34 / 39

Parameterizationclassvalvalval}ParamChannel (n: Int) extends Bundle {data Input (UInt(n.W))ready Output (Bool ())valid Input (Bool ())val ch32 new ParamChannel (32)I Bundles and modules can be parametrizedI Pass a parameter in the constructor35 / 39

A Module with a Parameterclass 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 type36 / 39

Use the Parameterval add8 Module (new ParamAdder (8))val add16 Module (new ParamAdder (16))I Can be used for the display multiplexing configurationI Different maximum value for the counter for the simulationand for the FPGA37 / 39

Today’s LabI Paper & pencil exercisesI Exercises on FSMsI From the Dally bookI Just sketch the Chisel codeI On paper or in a plain text editorI As usual, show and discuss your solution with a TA38 / 39

SummaryI Counters are used to generate timingI An FSM can control a datapath, which is an FSMDI An FSMD is a computing machineI Functions to structure your code39 / 39

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, somet