FINITE STATE MACHINE: PRINCIPLE AND PRACTICE

1 CHAPTER 10 FINITE STATE machine : PRINCIPLE ANDPRACTICEA FINITE STATE machine (FSM) is a sequential circuit with random next- STATE logic. Unlikethe regular sequential circuit discussed in Chapters 8 and 9, the STATE transitions and eventsequence of an FSM do not exhibit a simple pattern. Although the basic block diagram ofan FSM is similar to that of a regular sequential circuit, its design procedure is derivation of an FSM starts with a more abstract model, such as a STATE diagram or analgorithm STATE machine (ASM) chart. Both show the interactions and transitions betweenthe internal states in graphical formats. In this chapter, we study the representation, timingand implementation issues of an FSM as well as derivation of the VHDL code. Our emphasisis on the application of an FSM as the control circuit for a large, complex system, andour discussion focuses on the issues related to this aspect. As in previous chapters, ourdiscussion is limited to the synchronous FSM, in which the STATE register is controlled by asingle global OVERVIEW OF FSMSAs its name indicates, afinite STATE machine (FSM) is a circuit with internal states .

2 Unlikethe regular sequential circuits discussed in Chapters 8 and 9, STATE transition of an FSMis more complicated and the sequence exhibits no simple, regular pattern, as in a counteror shift register. The next- STATE logic has to be constructed from scratch and is sometimesknown as random , an FSM is specified by five entities: symbolic states , input signals, outputsignals, next- STATE function and output function. A STATE specifies a unique internal conditionRTL Hardware Design Using VHDL: Coding for Efficiency, Portability, and Pong P. ChuCopyrightc 2006 John Wiley & Sons, STATE machine : PRINCIPLE AND PRACTICE dqstate registerMooreoutput logicMealy output logicMealy outputMooreoutputnext-statelogicstate_ne xtstate_reginputclkFigure diagram of an a system. As time progresses, the FSM transits from one STATE to another. The new stateis determined by the next- STATE function, which is a function of the current STATE and inputsignals. In asynchronous FSM, the transition is controlled by a clock signal and canoccur only at the triggering edge of the clock.

3 As we discussed in Section , our studystrictly follows the synchronous design methodology, and thus coverage is limited to thesynchronous output function specifies the value of the output signals. If it is afunction of the stateonly, the output is known as aMoore output. On the other hand, if it is afunction of thestate and input signals, the output is known as aMealy output. An FSM is called aMooremachineorMealy machineif it contains only Moore outputs or Mealy outputs complex FSM normally has both types of outputs. The differences and implications ofthe two types of outputs are discussed in Section block diagram of an FSM is shown in Figure It is similar to the block diagram ofa regular sequential circuit. The STATE register is the memory element that stores the STATE ofthe FSM. It is synchronized by a global clock. The next- STATE logic implements the next-statefunction, whose input is the current STATE and input signals. The output logic implementsthe output function.

4 This diagram includes both Moore output logic, whose input is thecurrent STATE , and Mealy output logic, whose input is the current STATE and input main application of an FSM is to realize operations that are performed in a sequenceof steps. A large digital system usually involves complex tasks or algorithms, which canbe expressed as a sequence of actions based on system status and external commands. AnFSM can function as the control circuit (known as thecontrol path) that coordinates andgoverns the operations of other units (known as thedata path) of the system. Our coverageof FSM focuses on this aspect. The actual construction of such systems is discussed in thenext two chapters. FSMs can also be used in many simple tasks, such as detecting a uniquepattern from an input data stream or generating a specific sequence of output FSM REPRESENTATIONThe design of an FSM normally starts with an abstract, graphic description, such as a statediagram or an ASM chart.

5 Both descriptions utilize symbolic STATE notations, show thetransition among the states and indicate the output values under various conditions. A statediagram or an ASM chart can capture all the needed information ( , STATE , input, output,next- STATE function, and output function) in a single REPRESENTATION315S0mo <= valuelogic expression / me <= valuelogic expression / me <= valuemo: Moore outputme: Mealy outputFigure for a STATE diagramA STATE diagram consists of nodes, which are drawn as circles (also known asbubbles),and one-direction transition arcs. The notation for nodes and arcs is shown in Figure a unique STATE of the FSM and it has a unique symbolic name. Anarcrepresents a transition from one STATE to another and is labeled with the condition that willcause the transition. The condition is expressed as a logic expression composed of inputsignals. An arc will be taken when the corresponding logic expression is evaluated to belogic 1 .The output values are also specified on the STATE diagram.

6 The Moore output is a functionof STATE and thus is naturally placed inside the STATE bubble. On the other hand, the Mealyoutput depends on both STATE and input and thus is placed under the condition expression ofthe transition arcs. To reduce the clutter, we list only the output signals that are activatedor asserted. An output signal will assume the default, unasserted value (notdon t-care) ifit is not listed inside the STATE bubble or under the logic expression of an arc. We use thefollowing notation for an asserted output value:signal_name <= asserted value;In general, an asserted signal will be logic 1 unless specified STATE diagram can best be explained by an example. Figure shows the statediagram of a hypothetical memory controller FSM. The controller is between a processorand a memory chip, interpreting commands from the processor and then generating a controlsequence accordingly. The commands,mem,rwandburst, from the processor constitutethe input signals of the FSM.

7 Thememsignal is asserted to high when a memory access isrequired. Therwsignal indicates the type of memory access, and its value can be either 1 or 0 , for memory read and memory write respectively. Theburstsignal is for a specialmode of a memory read operation. If it is asserted, four consecutive read operations willbe performed. The memory chip has two control signals,oe(for output enable) andwe(for write enable), which need to be asserted during the memory read and memory writerespectively. The two output signals of the FSM,oeandwe, are connected to the memorychip s control signals. For comparison purpose, we also add an artificial Mealy outputsignal,weme, to the STATE , the FSM is in theidlestate, waiting for thememcommand from the asserted, the FSM examines the value ofrwand moves to either theread1state or thewritestate. These input conditions can be formalized to logic expressions, asshown in the transition arcs from theidlestate: mem : represents that no memory operation is STATE machine : PRINCIPLE AND PRACTICE Figure diagram of a memory controller REPRESENTATION317 mem rw: represents that a memory read operation is required.

8 Mem rw : represents that a memory write operation is results of these logic expressions are checked at the rising edge of the clock. If themem expression is true ( ,memis 0 ), the FSM stays in theidlestate. If themem rwexpression is true ( , bothmemandrware 1 ), the FSM moves to theread1state. Onceit is there, theoesignal is activated, as indicated in the STATE bubble. On the other hand, ifthemem rw expression is true ( ,memis 1 andrwis 0 ), the FSM moves to thewritestate and activates the FSM reaches theread1state, theburstsignal is examined at the next risingedge of the clock. If it is 1 , the FSM will go throughread2,read3andread4states inthe next three clock cycles and then return to theidlestate. Otherwise, the FSM returnsto theidlestate. We use the notation to represent the always true condition. Afterthe FSM reaches thewritestate, it will return to theidlestate at the next rising edge ofthe is asserted only when the FSM is in theidlestate and themem rw expression is true.

9 It will be deactivated when the FSM moves away from theidlestate( , to thewritestate). It is a Mealy output since its value depends on the STATE and theinput signals ( ,memandrw).In PRACTICE , we usually want to force an FSM into an initial STATE during system initial-ization. It is frequently done by an asynchronous reset signal, similar to the asynchronousreset signal used in a register of a regular sequential circuit. Sometimes a solid dot isused to indicate this transition, as shown in Figure This transition is only for systeminitialization and has no effect on normal FSM ASM chartAnalgorithmic STATE machine (ASM) chart is an alternative method for representing anFSM. Although an ASM chart contains the same amount of information as a STATE diagram,it is more descriptive. We can use an ASM chart to specify the complex sequencing ofevents involving commands (input) and actions (output), which is the hallmark of complexalgorithms. An ASM chart representation can easily be transformed to VHDL code.

10 It canalso be extended to describe FSMD (FSM with a data path), which is discussed in the nexttwo ASM chart is constructed of a network of ASM blocks. AnASM blockconsists ofone STATE box and an optional network of decision boxes and conditional output boxes. Atypical ASM block is shown in Figure Thestate box, as its name indicates, representsa STATE in an FSM. It is identified by a symbolic STATE name on the top left corner of the statebox. The action or output listed inside the box describes the desired output signal valueswhen the FSM enters this STATE . Since the outputs rely on the STATE only, they correspond tothe Moore outputs of the FSM. To reduce the clutter, we list only signals that are activatedor asserted. An output signal will assume the default, unasserted value if it is not listedinside the box. We use the same notation for an asserted output signal:signal_name <= asserted value;Again, we assume that an asserted signal will be logic 1 unless specified boxtests an input condition to determine the exit path of the current ASMblock.