Section 8 − FSMD Page 1 of 68.1 Register-Transfer Design ModelEvery digital design consists of a control unit and a datapath.Datapath inputsSelectorRegisterRFMemoryBus1Bus2*, /ALUBus3DatapathDatapath outputsRegisterControl inputsControl outputsNext-statelogicOutputlogicStateregisterDQDQDQControl UnitControlsignalsStatussignalsIn the FSM model, each state assigns values to a set of datapath control signals which completely specifies thebehavior of the datapath.However, when there are too many control signals it is difficult to realize what and how the datapath will operate.(See figure 7.30)To improve on the FSM model, we use variable assignment statements to indicate changes in variable values storedin the datapath.An FSMD (FSM with datapath) is a FSM model with assignment statements added to each state.Formally, a finite-state machine with datapath is a 6-tuple defined as follows:P = <S, s0, I ∪ STAT, O ∪ A, f, h>compare: FSM is defined as P = <S, s0, I, O, f, h>where:• S = {s0, …, sm} is a finite set of states• s0 is the reset state.• I = {ij} is a set of primary input values.• STAT = {Rel(a, b) : a, b ∈ EXP} is a set of status signals as logical relations between two expressionsfrom the set EXP.• EXP = {f(x,y,z,…) : x,y,z,… ∈ VAR} is a set of expressions.• VAR is a set of storage variables.• O = {ok} is a set of primary output values.• A = {x ⇐ e : x ∈ VAR, e ∈ EXP} is a set of storage assignments.• f is a state transition function that maps a cross product of S and I ∪ STAT into S.• h is the output function that maps a cross product of S and I ∪ STAT into O ∪ A for Mealy models or Sinto O ∪ A for Moore models.Section 8 − FSMD Page 2 of 6So instead of a separate next-state table and output table, we combine the two to give us a “next-state and outputtable with variable assignments.”Next StateStart, Data=0ControlOutputDatapathOutputCurrentState00 01 10 11 Done OutputDatapath Variabless0s0 s0 s1 s10 Zs1s2 s2 s2 s20 Z Data = Inputs2s3 s3 s3 s30 Z Ocount = 0s3s4 s4 s4 s40 Z Mask = 1s4s5 s5 s5 s50 Z Temp = Data AND Masks5s6 s6 s6 s60 Z Ocount = Ocount + Temps6s4 s7 s4 s70 Z Data = Data >> 1s7s0 s0 s0 s01 OcountFigure 8.3 (b) State and output table with variable assignments –FSMD specification of one’s counter.We assume that variables retain their old values if no new value is specified in a particular state.• Note that although expression evaluation is performed in one state, the new variable value could not beused until the next state at the earliest.Similarly, we do not have to specify the next state for every control input and every status signal, but only for thosethat affect the next state selection.• Thus, we can simplify the next-state column by specifying in each state only the condition and the nextstate that the control unit will enter if the condition is true.We can also use assignment statements for datapath and control unit output ports.• Unlike variables in the datapath, output ports do not retain their value beyond the present state since thevalues are not stored in registers or memory.From the above observations, we obtain a reduced table called a state-action table for specifying FSMDs.Next State Control and Datapath ActionsCurrentStateCondition, State Condition, Actionss0==10,1,0sStartsStart==ZOutputDone 0s1s2Data = Inputs2s3Ocount = 0s3s4Mask = 1s4s5Temp = Data AND Masks5s6Ocount = Ocount + Temps6=≠74,0,0sDatasDataData = Data >> 1s7s0==OcountOutputDone 1Figure 8.3 (c) State-action table – FSMD specification of one’s counter.Section 8 − FSMD Page 3 of 68.3 Algorithmic-state machine (ASM) chartASM chart is an alternative graphic form for specifying FSMDs and are equivalent to the state-action tables.Name Definition Example CommentState box(Unconditionalassignment)Unconditionalvariable and outputassignmentStatenameStatecodeTemp = Temp AND MaskS3011Each state isindicated by a statebox.Contains the set ofunconditionalassignments tovariables and outputports in thedatapath.Decision box01Condition01Data = 0To select specificactions in thedatapath and thenext state.Condition box(Conditionalassignment)ConditionalvariableassignmentOcount = Ocount + 1Variable or outputassignments that areexecuted underconditions specifiedby one or moredecision boxes.ASM blockData = InputDone = 0start = 101Each ASM blockdescribes theoperations executedin one state.This is equivalent toa row in the state-action table.Section 8 − FSMD Page 4 of 6Data = Inputs1Ocount = 0s2Mask = 1s3Temp = Data AND Masks4Done = 0start = 001s0000Data = Data >> 1Data = 010s6Ocount = Ocount + Temps5Done = 0Output = Ocounts7Figure 8.5 ASM chart for one’s counter.Example 8.1 Redesign the one’s counter using a custom datapath.Solution.• Need only two variables: Data and Ocount.• Need only two operations: shift the value in Data, and increment the value in Ocount.• In the state-based (Moore) version of the FSMD:• all the variable assignments must be executed unconditionally in a state and only next states are to beselected conditionally.• has six states → more state registers → next-state logic more complex.• output logic is simpler since it is dependent only on the present state.• In the input-based (Mealy) version of the FSMD:• the variable assignments can be executed conditionally together with the conditional selection of nextstates.• has four states → simpler next-state logic.• output logic is more complex since it includes external and internal conditions.Section 8 − FSMD Page 5 of 6State-base (Moore)Data = InputOcount = 0s1Done = 0start = 001s0000Ocount = Ocount + 1s3Done = 1Output = Ocounts5DataLSB01s2010Data = Data >> 1Data = 010s4Figure 8.6 (a) State-based (Moore) ASM chart.Next State Control and Datapath ActionsCurrent StateQ2Q1Q0 NameCondition, State Condition, Actions0 0 0 s0==10,1,0sStartsStart==ZOutputDone 00 0 1 s1s2==0OcountInputData0 1 0 s2==43,0,1sDatasDataLSBLSB0 1 1 s3s4Ocount = Ocount +11 0 0 s4=≠52,0,0sDatasDataData = Data >> 11 0 1 s5s0==OcountOutputDone 1Figure 8.7 (a) State-based state-action table for the one’s counter.QQ'DClk222QQ'DClk111QQ'DClk000StartShift Right wParallel LoadS1S0Up/downcounterELoadD"0""0"DataLSBData = 0InputOuputDoneOuput enableOutputlogicDatapathNext-state