B 10 B 67 Finite State Machines 128 bit word needs 8 This type of code is called a Hamming code after R Hamming who described a method for creating such codes B 10 Finite State Machines B 10 As we saw earlier digital logic systems can be classi ed as combinational or sequential Sequential systems contain state stored in memory elements internal to the system Their behavior depends both on the set of inputs supplied and on the contents of the internal memory or state of the system Thus a sequential system cannot be described with a truth table Instead a sequential system is described as a nite state machine or often just state machine A nite state machine has a set of states and two functions called the next state function and the output function The set of states correspond to all the possible values of the internal storage Thus if there are n bits of storage there are 2n states The nextstate function is a combinational function that given the inputs and the current state determines the next state of the system The output function produces a set of outputs from the current state and the inputs Figure B 10 1 shows this diagrammatically nite state machine A sequential logic function consisting of a set of inputs and outputs a next state function that maps the current state and the inputs to a new state and an output function that maps the current state and possibly the inputs to a set of asserted outputs next state function A combinational function that given the inputs and the current state determines the next state of a finite state machine Next state Current state Next state function Clock Inputs Output function Outputs FIGURE B 10 1 A state machine consists of internal storage that contains the state and two combinational functions the next state function and the output function Often the output function is restricted to take only the current state as its input this does not change the capability of a sequential machine but does affect its internals B 68 Appendix B The Basics of Logic Design The state machines we discuss here and in Chapters 5 and 6 are synchronous This means that the state changes together with the clock cycle and a new state is computed once every clock Thus the state elements are updated only on the clock edge We use this methodology in this section and throughout Chapters 5 and 6 and we do not usually show the clock explicitly We use state machines throughout Chapters 5 and 6 to control the execution of the processor and the actions of the datapath To illustrate how a nite state machine operates and is designed let s look at a simple and classic example controlling a traf c light Chapters 5 and 6 contain more detailed examples of using nite state machines to control processor execution When a nite state machine is used as a controller the output function is often restricted to depend on just the current state Such a nite state machine is called a Moore machine This is the type of nite state machine we use throughout this book If the output function can depend on both the current state and the current input the machine is called a Mealy machine These two machines are equivalent in their capabilities and one can be turned into the other mechanically The basic advantage of a Moore machine is that it can be faster while a Mealy machine may be smaller since it may need fewer states than a Moore machine In Chapter 5 we discuss the differences in more detail and show a Verilog version of nite state control using a Mealy machine Our example concerns the control of a traf c light at an intersection of a northsouth route and an east west route For simplicity we will consider only the green and red lights adding the yellow light is left for an exercise We want the lights to cycle no faster than 30 seconds in each direction so we will use a 0 033 Hz clock so that the machine cycles between states at no faster than once every 30 seconds There are two output signals NSlite When this signal is asserted the light on the north south road is green when this signal is deasserted the light on the north south road is red EWlite When this signal is asserted the light on the east west road is green when this signal is deasserted the light on the east west road is red In addition there are two inputs NScar and EWcar NScar Indicates that a car is over the detector placed in the roadbed in front of the light on the north south road going north or south EWcar Indicates that a car is over the detector placed in the roadbed in front of the light on the east west road going east or west The traf c light should change from one direction to the other only if a car is waiting to go in the other direction otherwise the light should continue to show green in the same direction as the last car that crossed the intersection B 10 B 69 Finite State Machines To implement this simple traf c light we need two states NSgreen The traf c light is green in the north south direction EWgreen The traf c light is green in the east west direction We also need to create the next state function which can be speci ed with a table Inputs Current state NScar EWcar NSgreen 0 0 Next state NSgreen NSgreen 0 1 EWgreen NSgreen 1 0 NSgreen NSgreen 1 1 EWgreen EWgreen 0 0 EWgreen EWgreen 0 1 EWgreen EWgreen 1 0 NSgreen EWgreen 1 1 NSgreen Notice that we didn t specify in the algorithm what happens when a car approaches from both directions In this case the next state function given above changes the state to ensure that a steady stream of cars from one direction cannot lock out a car in the other direction The nite state machine is completed by specifying the output function Outputs Current state NSlite EWlite NSgreen 1 0 EWgreen 0 1 Before we examine how to implement this nite state machine let s look at a graphical representation which is often used for nite state machines In this representation nodes are used to indicate states Inside the node we place a list of the outputs that are active for that state Directed arcs are used to show the next state function with labels on the arcs specifying the input condition as logic functions Figure B 10 2 shows the graphical representation for this nite state machine A nite state machine can be implemented with a register to hold the current state and a block of combinational logic that computes the next state function and the output function Figure B 10 3 shows how a nite state machine with 4 bits of state and thus up to 16 states might look To implement the nite state
View Full Document
Unlocking...