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.

2 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. 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.

3 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.

4 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. 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.

5 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.

6 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.

7 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. 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.

8 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. 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.

9 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.

10 The commands,mem,rwandburst, from the processor constitutethe input signals of the FSM. 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.