Popular in Course
Popular in Computer Engineering
This 8 page Class Notes was uploaded by Felton Hintz on Thursday October 29, 2015. The Class Notes belongs to CEG360 at Wright State University taught by TravisDoom in Fall. Since its upload, it has received 17 views. For similar materials see /class/231076/ceg360-wright-state-university in Computer Engineering at Wright State University.
Reviews for DigitalSystemDesign
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/29/15
Finite State Machine Design The Finite state machine design process consists of Constructing an initial state machine that realizes the design Minimizing the number of states Encoding the states Choosing the memory device to implement the state memory Implementing the nite state machine s next state and output functions Elk WP In the age of very large scale integrated circuits why should we bother to minimize a state machine implementation After all as long as the inputoutput behavior of the machine is correct it doesn t matter how it is implemented Or does it Advantages of minimum states In general you will nd it is worthwhile to implement the nite state machine in as few states as possible This usually reduces the number of gates and ip ops you need for the machine implementation For example you are given a nite state machine with 18 states thus requiring ve state ip ops If you can reduce the number of states to 16 or less you save a ip op Even if reducing the reducing the number of states is not enough to eliminate a ip op it still has advantages With fewer states you introduce more don t care conditions into the nextstate and output functions making their implementation simpler State reduction technique also allows you to be less meticulous in obtaining the initial nite state machine description If you have introduced a few redundant states you will nd and eliminate them by using the state reduction technique introduced next State Minimization State reduction identi es and combines states that have equivalent behavior Two states have equivalent behavior if for all the input combinations their outputs are the same and they change to the same or equivalent next states Algorithms for state reduction begin with the symbolic state transition table First we group together states that have same state outputs Moore machine or transition outputs mealy machine These are potentially equivalent since states cannot be equivalent if their outputs differ Next we examine the transitions to see if they go to the same next state for every input combination If they do the states are equivalent and we can combine them into a renamed new state We then update all transitions to the newly combine states We repeat this process until no additional states can be combined There are two common methods by which states can be minimized l Rowmatching method 2 Chart method Row Matching Method Let s begin our investigation of a rowmatching method with detailed example We will see how to transform an initial state diagram for a simple sequence detector into a minimized equivalent state diagram Four Bit Sequence Detector Speci cation and Initial state diagram Let s consider a sequencedetecting nite state machine with following speci cations The machine has single input X and output Z The output is asserted after each four bit input sequence if it consists of one of the binary strings 0110 or 1010 The machine returns to the reset state after each fourbit sequence will assume mealy implementation The state diagram of 4bit sequence detector is as shown below Reset 00 10 0 O 0 10 0 10 0 O O O 0 10 0 10 0 10 00 1 O O O O O O O O 0 10 00 00 10 01 10 0 10 0 0 00 10 0 1 0 There are 16 unique paths through the state diagram one for each possible 4bit pattern This requires 15 states and 30 transitions Only two of the transitions have a one output representing the accepted strings The state transition table for 4bit sequence detector is as shown below Input Sequence Present State Next state Output The above table contain one row per state with multiple next state and the outputs columns based on the input combinations It gives the same information as a table with separate rows for each state and input combination Next we examine the rows of the state transition table to nd any with identical next state and output values hence the term row matching For this nite state machine we can combine S10 and S12Lets call the new state S10 and modify all transitions to S10 and Input Sequence Present State Next State Output We continue matching rows until we can no longer combine any In the above gure S7 S8 S9 S11 S13 and S14 all have the same next state and the outputs We combine them into a renamed state S7 The table with renamed transitions is shown in the gure below Input Sequence Present State Next State Output Not011 or 101 011 or101 S7 S10 S0 S0 S0 S0 0 1 Now state S3 and S6 can be combined as can S4 and S5 We call the combined states S3 and S4 respectively The nal reduced state transition table is as shown below Input Sequence Present State Next State Output X0 X 1 X0 X1 Reset S0 S1 S2 0 0 0 S1 S3 S4 0 0 1 S2 S4 S3 0 0 00 or 11 S3 S7 S7 0 0 01 or 10 S4 S7 S10 0 0 Not011 or 101 S7 S0 S0 0 0 0110r101 S10 S0 S0 1 0 In the process we have reduced 15 states to just 7 states The reduced state diagram is as shown below Reset Chart Method The implication Chart method is a more systematic approach to nding the states that can be combined into a single reduced state Consider a Three Bit Sequence Detector Your goal is to design a binary sequence detector that will output a 1 whenever a machine has observed the serial sequence 010 or 110 at the inputs The initial table is as shown below Input Sequence Present State Next state The method operates on a data structure that enumerates all possible combinations of states taken two at a time called an implication chart SO 1 2 S3 S4 SS S6 The chart shown above is more complicated then it needs to be For example the diagonal entries are not needed since we do not need to compare a state with itself Also note that al the upper and the lower triangles of cells are symmetric The chart cell for row Si and column Sj considers the same information as that for row Sj and column Si Therefore we work with the following reduced structure SO S1 S2 S3 S4 S5 We will ll the implication chart as follows Let Xij be the cell whose row is labeled by the state Si and whose column is labeled by the state Sj If we were able to combine states Si and Sj it would imply that their next state transitions for each input combination must also be equivalent The cell contains the nextstate combinations that must be equivalent for the row and column states to be equivalent If Si and Sj have different outputs or next state behavior an X is placed in the cell This indicates that the two states can never be equivalent The implication chart for threebit sequence detector is as shown below S0 S1 S2 S3 and S5 have the same outputs and are the candidates for being combined Similarly states S4 and S6 might also be combined Any combination of states across the groups such as S1 and S4 is labeled by an X in the chart Since their outputs are different they can NEVER be equivalent To fill the chart entry for row S1 and column S0 we look at the next transition S0 goes to S1 on 0 and S2 on 1 while Sl goes to S3 and S4 respectively We will fill the chart in with SlS3 the transitions on 0 and S2S4 the transitions on lWe call this grouping implied state pairs The entry means that S0 and S1 cannot be equivalent unless S1 is equivalent to S3 and S2 is equivalent to S4The rest of the entries are filled in similarly At this point the chart contain enough information to prove that many states are NOT EQUIVALENT For example we already know that S2 and S4 cannot be equivalent since they have different output behavior Thus there is no way that S0 can be equivalent to S l Initial Entriea First Pass S1S3 S2S4 S1S5 S3S5 S2S4 S4S6 S1S0 S3S0 S5S0 S2S0 S4S0 S6S0 S1S0 S3S0 S5S0 S0S0 S2S0 S4S0 S6S0 S0S0 S0S0 S0S0 SO S1 S2 S3 S4 S5 SO S2 S3 S4 S5 The above gure contains the results of rst making pass Entry S2S0 is marked with X because the chart entry for the implied state pair S2S6 is already marked with a X Entry S3S0 is also marked because SlSO has just been marked The same is true for S5S0by the end ofthe pass the only entries not marked are S2Sl S5S3 and S6S4 We now make a second pass through the chart to see if we can add any new markings Entry S2Sl remains unmarked Nothing in the chart refuses that S3 and S5 are equivalent The same is true of S4 and S6 Continuing S3S5 and S4S6 are now obviously equivalent They have identical outputs and transfer to the same next state SO for all input combinations Since no marking have been added the algorithm stops The unmarked entries represent equivalence between the row and the column indices The nal reduced state table is as shown Input sequence Present State Next State Output X0 Xl X0 Xl Reset S0 S 1 S1 0 0 0 or 1 S1 S3 S4 0 0 00 or 10 S3 S0 S0 0 0 01 or 11 S4 S0 S0 1 0 Reference Books Contemporary Logic Design by Randy H Katz Principles of Digital Design by Daniel H Gajski Digital Logic and State Machine Design by David J Comer Modern Digital Electronics by RPJain
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'