Finite-State Machines

Finite-State MachinesMartin SchoeberlTechnical University of DenmarkEmbedded Systems EngineeringMarch 10, 20221 / 48

OverviewI Debugging with waveformsI Fun with countersI Finite-state machinesI Collection with Vec2 / 48

Organization and Lab WorkI Labs are in B308-IT127, B308-IT017I Use both rooms, you have more space in two roomsI How did the testing lab work? Did you find both bugs?I This week the 7-segment decoderI A lot can be done with simulation and testingI But, at the end of the day I want to see a vending machinein an FPGA3 / 48

Testing with ChiselI A test containsI a device under test (DUT) andI the testing logicI Set input values with pokeI Advance the simulation with stepI Read the output values with peekI Compare the values with expectI Import following packagesimport chisel3 .import chiseltest .import org. scalatest . flatspec . AnyFlatSpec4 / 48

An Example DUTI A device-under test (DUT)I Just 2-bit AND logicclass DeviceUnderTest extends Module {val io IO(new Bundle {val a Input (UInt (2.W))val b Input (UInt (2.W))val out Output (UInt (2.W))})io.out : io.a & io.b}5 / 48

A ChiselTestI Extends class AnyFlatSpec with ChiselScalatestTesterI Has the device-under test (DUT) as parameter of thetest() functionI Test function contains the test codeI Testing code can use all features of ScalaI Is placed in src/test/scalaI Is run with sbt test6 / 48

A Simple TesterI Just using println for manual inspectionclass SimpleTest extends AnyFlatSpec withChiselScalatestTester {"DUT" should "pass" in {test(new DeviceUnderTest ) { dut dut.io.a.poke (0.U)dut.io.b.poke (1.U)dut. clock .step ()println (" Result is: " dut.io.out.peek (). toString )dut.io.a.poke (3.U)dut.io.b.poke (2.U)dut. clock .step ()println (" Result is: " dut.io.out.peek (). toString )}}}7 / 48

A Real TesterI Poke values and expect some outputclass SimpleTestExpect extends AnyFlatSpecwith ChiselScalatestTester {"DUT" should "pass" in {test(new DeviceUnderTest ) { dut dut.io.a.poke (0.U)dut.io.b.poke (1.U)dut. clock .step ()dut.io.out. expect (0.U)dut.io.a.poke (3.U)dut.io.b.poke (2.U)dut. clock .step ()dut.io.out. expect (2.U)}}}8 / 48

Generating WaveformsI Waveforms are timing diagramsI Good to see many parallel signals and registerssbt "testOnly SimpleTest -- -DwriteVcd 1"I Or setting an attribute for the test() functiontest(new DeviceUnderTest ). withAnnotations (Seq( WriteVcdAnnotation ))I IO signals and registers are dumpedI Option --debug puts all wires into the dumpI Generates a .vcd fileI Viewing with GTKWave or ModelSim9 / 48

A Self-Running CircuitI Count6 is a self-running circuitI Needs no stimuli (poke)I Just run for a few cyclestest(new Count6 ) { dut dut. clock .step (20)}10 / 48

Call the Tester for Waveform GenerationI The complete testI Note the .withAnnotations(Seq(WriteVcdAnnotation)class Count6WaveSpec extends AnyFlatSpec withChiselScalatestTester {" CountWave6 " should "pass" in {test(newCount6 ). withAnnotations (Seq( WriteVcdAnnotation )){ dut dut. clock .step (20)}}}11 / 48

Display Waveform with GTKWaveI Run the tester: sbt testI Locate the .vcd file in test run dir/.I Start GTKWaveI Open the .vcd file withI File – Open New TabI Select the circuitI Drag and drop the interesting signals12 / 48

Counters as Building BlocksI Counters are versatile toolsI Count eventsI Generate timing ticksI Generate a one-shot timer13 / 48

Counting Up and DownI Up:val cntReg RegInit (0.U(8.W))cntReg : cntReg 1.Uwhen( cntReg N) {cntReg : 0.U}I Down:val cntReg RegInit (N)cntReg : cntReg - 1.Uwhen( cntReg 0.U) {cntReg : N}14 / 48

Generating Timing with CountersI Generate a tick at a lower frequencyI We used it in Lab 1 for the blinking LEDI Use it for driving the display multiplexing at 1 kHzclockresettickcounter0120120115 / 48

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

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}17 / 48

The Slow CounterI Incremented every tickclockresettickslow cnt01218 / 48

A TimerI Like a kitchen timerI Start by loading a timeout valueI Count down till 0I Assert done when finished19 / 48

One-Shot Timer -10nextD Qcnt 0donedinloadSelect20 / 48

One-Shot Timerval cntReg RegInit (0.U(8.W))val done cntReg 0.Uval next WireDefault (0.U)when (load) {next : din} . elsewhen (! done) {next : cntReg - 1.U}cntReg : next21 / 48

A 4 Stage Shift Registerdindoutval shiftReg Reg(UInt (4.W))shiftReg : shiftReg (2, 0) ## dinval dout shiftReg (3)22 / 48

A Shift Register with Parallel Outputq3q2q1q0serInval outReg RegInit (0.U(4.W))outReg : serIn ## outReg (3, 1)val q outReg23 / 48

A Shift Register with Parallel Loadd0loadd1loadd2loadloadd3serOut0val loadReg RegInit (0.U(4.W))when (load) {loadReg : d} otherwise {loadReg : 0.U ## loadReg (3, 1)}val serOut loadReg (0)24 / 48

A Simple CircuitI What does the following circuit?I Is this related to a finite-state machine?dinNOTANDrisingEdge25 / 48

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 large26 / 48

Basic Finite-State MachineI A state registerI Two combinational 7 / 48

State Diagrambad eventresetgreenbad eventorangered/ring bellclearclearI States and transitions depending on input valuesI Example is a simple alarm FSMI Nice visualizationI Will not work for large FSMsI Complete code in the Chisel book28 / 48

State Table for the Alarm FSMInputStateBad eventClearNext stateRing greenorangeorangeredgreenredgreen000001129 / 48

The Input and Output of the Alarm FSMI Two inputs and one outputval io IO(new Bundle {val badEvent Input (Bool ())val clear Input (Bool ())val ringBell Output (Bool ())})30 / 48

Encoding the StateI We can optimize state encodingI Two common encodings are: binary and one-hotI We leave it to the synthesize toolI Use symbolic names with an EnumI Note the number of states in the Enum constructI We use a Scala list with the :: operatorval green :: orange :: red :: Nil Enum (3)31 / 48

Start the FSMI We have a starting state on resetval stateReg RegInit ( green )32 / 48

The Next State Logicswitch ( stateReg ) {is ( green ) {when(io. badEvent ) {stateReg : orange}}is ( orange ) {when(io. badEvent ) {stateReg : red} . elsewhen (io. clear ) {stateReg : green}}is (red) {when (io. clear ) {stateReg : green}}}33 / 48

The Output Logicio. ringBell : stateReg red34 / 48

Summary on the Alarm ExampleI Three elements:1. State register2. Next state logic3. Output logicI This was a so-called Moore FSMI There is also a FSM type called Mealy machine35 / 48

A so-called Mealy FSMI Similar to the former FSMI Output also depends in the inputI It is fasterI Less composable (draw it)stateNextstatelogicinnextStateOutputlogicout36 / 48

The Mealy FSM for the Rising EdgeI That was our starting exampleI Output is also part of the transition arrows0/0reset1/01/1zeroone0/037 / 48

The Mealy SolutionI Show code from the book as it is too long for slides38 / 48

State Diagram for the Moore Rising Edge DetectionI We need three states1resetzero01puls1one00039 / 48

Comparing with a Timing DiagramI Moore is delayed one clock cycle compared to MealyclockdinrisingEdge MealyrisingEdge Moore40 / 48

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

Another Simple FSMI a FSM for a single word bufferI Just two symbols for the state machineval empty :: full :: Nil Enum (2)42 / 48

Finite State Machine for a Bufferval empty :: full :: Nil Enum (2)val stateReg RegInit ( empty )val dataReg RegInit (0.U(size.W))when( stateReg empty ) {when(io.enq. write ) {stateReg : fulldataReg : io.enq.din}}. elsewhen ( stateReg full) {when(io.deq.read) {stateReg : empty}}I A simple buffer for a bubble FIFO43 / 48

A Collection of Signals with VecI Chisel Vec is a collection of signals of the same typeI The collection can be accessed by an indexI Similar to an array in other languagesI Wrap into a Wire() for combinational logicI Wrap into a Reg() for a collection of registersval v Wire(Vec (3, UInt (4.W)))44 / 48

Using a Vecv(0) : 1.Uv(1) : 3.Uv(2) : 5.Uval idx 1.U(2.W)val a v(idx)I Reading from an Vec is a multplexerI We can put a Vec into a Regval registerFile Reg(Vec (32 , UInt (32.W)))An element of that register file is accessed with an index andused as a normal register.registerFile (idx) : dInval dOut registerFile (idx)45 / 48

Mixing Vecs and BundlesI We can freely mix bundles and vectorsI When creating a vector with a bundle type, we need topass a prototype for the vector fields. Using our Channel,which we defined above, we can create a vector ofchannels with:val vecBundle Wire(Vec (8, new Channel ()))I A bundle may as well contain a vectorclass BundleVec extends Bundle {val field UInt (8.W)val vector Vec (4, UInt (8.W))}46 / 48

Today’s LabI This is the start of group workI Please register your group hereI Binary to 7-segment decoderI First part of your vending machineI Just a single digit, only combinational logicI Use the nice tester provided to develop the circuitI Then synthesize it for the FPGAI Test with switchesI Show a TA your working designI Lab 647 / 48

SummaryI Waveform testing is the way to develop/debugI Counters are important tools, e.g., to generate timingI Finite-state machines are another tool of the tradeI Two types: Moore and MealyI A Chisel Vec is the hardware version of an array48 / 48

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