 ## Chapter 4 Algorithmic State Machines And Finite State Machines-Free PDF

• Date:15 Jan 2020
• Views:52
• Pages:80
• Size:1.14 MB

Share Pdf : Chapter 4 Algorithmic State Machines And Finite State Machines

Download and Preview : Chapter 4 Algorithmic State Machines And Finite State Machines

Report CopyRight/DMCA Form For : Chapter 4 Algorithmic State Machines And Finite State Machines

Transcription:

66 Logic and System Design, light will be green on the main road otherwise dmain 0 the traffic light will be. green on the secondary road,Figure 2 A simple Traffic Light Controller. In the flowchart a logical condition is written in each conditional vertex It is possible. to write the same logical condition in different conditional vertices A microinstruction. an operator containing one two three or more microoperations is written in each. operator vertex of the flowchart It is possible to write the same operator in different. operator vertices, If we replace logical conditions by x1 x2 xL microoperations by y1 y2 yN and. operators by Y1 Y2 YT we will get Algorithmic State Machine ASM ASM for the. flowchart in Fig 2 is shown in Fig 3,ASM vertices are connected in such a way that. 1 Inputs and outputs of the vertices are connected by arcs directed from an. output to an input each output is connected with only one input. 2 Each input is connected with at least one output. 3 Each vertex is located on at least one of the paths from vertex Begin to. vertex End Hereinafter we will not consider ASMs with subgraphs. containing an infinite cycle An example of such a subgraph with an infinite. Chapter 4 Algorithmic state machines and finite state machines 67. loop between vertices with Y1 and Y3 is shown in Fig 4 The dots in this ASM. between vertex Begin and the conditional vertex with x1 and between this. vertex and vertex End mean that ASM has other vertices on the path from. vertex Begin to vertex End The vertices in the loop are not on the path. from Begin to End, 4 One of the outputs of a conditional vertex can be connected with its input.
We will call such conditional vertices the waiting vertices since they. simulate the waiting process in the system behavior description. Figure 3 ASM for the flowchart in Fig 2,Figure 4 Subgraph with an infinite loop. 68 Logic and System Design, One more example of ASM G1 with logical conditions X x1 x7 and. microoperations Y y1 y10 is shown in Fig 5 This ASM has eight operators Y1. Y8 they are written near operator vertices, 4 1 2 Transition functions Let us discuss the paths between the vertex Begin the. vertex End and operator vertices passing only through conditional vertices We will. write such paths as follows,In such a path, xir is equal to xir if the path proceeds from the conditional vertex. with xir via output 1 and,is equal to xir if the path proceeds from the.
conditional vertex with xir via output 0 For example we have the following paths. from Yb vertex Begin in ASM G1,Yb x1x2x 3 Y6,Yb x1x 2 Y1. Yb x1x2x3 Y5,y1 y2 0 x2,y4 x4 x3 y6 y7 Y6,0 y1 y3 Y5. y5 y6 y7 Y3 x1 0 y3 y4 Y7,x6 1 y8 y9 Y4 x6,x7 1 y3 y6 y10 Y8 y6 y7 Y6. Figure 5 ASM G1, Let us match a product of variables in the path 1 from operator vertex Yi to operator. with this path from Yi to Yj For example for ASM G1 in Fig 5. 17 x4 x 1 12 x 4 14 x4 x1, If there exist H paths between Yi and Yj through the conditional vertices then.
Chapter 4 Algorithmic state machines and finite state machines 69. ij 1ij 2ij Hij, where hij h 1 H is the product for the h th path Let us call ij a transition. function from operator microinstruction Yi to operator microinstruction Yj. Note that for the path Y6Y7 operator Y7 follows operator Y6 immediately without. conditional vertices 67 1 as the product of an empty set of variables is equal to. 4 1 3 Value of ASM at the sequence of vectors Denote all possible L component. vectors of the logical conditions x1 xL by 1 2L and define the execution of an. ASM on any given sequence of vectors 1 mq beginning from the initial operator. Yb We will demonstrate this procedure by means of ASM G1 in Fig 5 and the. sequence 2 containing eight vectors 1 8,x1 x2 x3 x4 x5 x6 x7. 1 1 0 1 0 1 1 1,2 0 1 1 0 1 0 0,3 1 0 1 0 0 1 0,4 0 1 0 0 0 0 1 2. 5 1 1 0 1 1 1 0,6 1 1 0 0 1 0 1,7 0 1 1 1 0 0 0,8 0 1 0 1 0 0 1. ASM G1 in Fig 5 contains logical variables x1 x7 and operators Yb Y1 Y8 Ye Now. let us find the sequence of operators which would be implemented if we. consecutively beginning from Yb give variables the values from these vectors We. suppose that the values of logical conditions can be changed only during an execution. of operators,Step 1 Write the initial operator, Step 2 Let logical variables x1 x7 take their values from vector 1 From the set of.
the transition functions b1 b8 be we choose such a function bt that bt 1 1. In our example for the operator Yb the following transition functions are not. identically equal to zero,b5 x1 x2 x3 b6 x1 x2 x 3 b1 x1 x 2 b2 x 1. We will call such functions non trivial transition functions to distinguish them from the. trivial functions which are identically equal to zero Function ij is trivial if there is no. path from operator Yi to operator Yj In the example at this step we choose the. function b1 since only b1 is equal to one on the first vector 1. Write Y1 to the right of Yb,70 Logic and System Design. Step 3 Let x1 x7 take their values from vector 2 From the set of the transition. functions 11 18 1e we choose non trivial functions. 14 x4 x1 17 x4 x 1 12 x 4, and among them the only function 12 2 1 Write Y2 to the right of YbY1. The computational process for the given sequence of vectors may reach its end in two. 1 The final vertex End is reached In this case the last operator is Ye The. number of operators in the operator row without Yb and Ye is less or equal if. we reached the final vertex with the last vector to the number of vectors. 2 The vectors are exhausted but we have not yet reached the final vertex In this. case the number of operators in the operator row is equal to the number of. In our example we reached the final vertex End at the seventh vector. 7 0 1 1 1 0 0 0,and we get the row,Yb Y1 Y2 Y4 Y2 Y3 Y8 Ye 3. The operator row thus obtained is the value of the ASM G1 for the given sequence of. 4 2 Synthesis of Mealy FSM, We will use Algorithmic state machines to describe the behavior of digital systems.
mainly of their control units But if we must construct a logic circuit of the control. unit we should use a Finite state machine FSM We will consider methods of. synthesis of FSM Mealy Moore and their combined model implementing a given ASM. with hardly any constrains on the number of inputs outputs and states. 4 2 1 Construction of a marked ASM As an example we will use ASM G1 in Fig 6. A Mealy FSM implementing given ASM may be constructed in two stages. Stage1 Construction of a marked ASM, Stage 2 Construction of a state diagram state graph. At the first stage the inputs of vertices following operator vertices are marked by. symbols a1 a2 aM as follows, 1 Symbol a1 marks the input of the vertex following the initial vertex Begin and. the input of the final vertex End, 2 Symbols a2 aM mark the inputs of all vertices following operator vertices. 3 Vertex inputs are marked only once, 4 Inputs of different vertices except the final one are marked by different. Marked ASM G1 in Fig 6 is a result of the first step Symbols a1 a6 are used to. mark this ASM Note that we mark the inputs not only of conditional vertices but. of operator vertices as well see mark a3 at the input of the vertex with operator. Y7 It is important that each marked vertex follows an operator vertex. Chapter 4 Algorithmic state machines and finite state machines 71. Figure 6 ASM G1 marked for the Mealy FSM synthesis. 4 2 2 Transition Paths At the second stage we will consider the following paths in. the marked ASM,xmR mYg as P1,xmRm a1 P2, We call these paths transition paths Thus the path P1 proceeds from am to as am as.
is also allowed and contains only one operator vertex at the end of this path The. path P2 proceeds from am only to a1 without operator vertex Here. xmr xmr if on, the transition path we leave the conditional vertex with xmr via output 1 and. xmr x mr if we leave it via output 0 If Rm 0 on the path P1 two operator vertices. follow one after another and this path turns into,a m Yg a s. There are sixteen transition paths in the marked ASM G2 in Fig 6. a1 x1x2x3 Y5 a2 a2 x4x1 Y4 a2 a4 x5 Y3 a5 a5 x 6x7 Y8 a1. a1 x1x2x 3 Y6 a3 a2 x4x 1 Y7 a6 a4 x 5x1 Y4 a2 a5 x 6x 7 a1. a1 x1x 2 Y1 a2 a2 x 4 Y2 a4 a4 x 5x 1 Y7 a6 a6 x6 Y6 a1. a1 x 1 Y2 a4 a3 Y7 a6 a5 x6 Y4 a2 a6 x 6 Y7 a6, Note that the path a2 x4x 1 a3 doesn t correspond to the transition path P1 the. operator vertex is absent on the path and to transition path P2 it isn t a path to a1. Thus it isn t a transition path and we should go on to get the path a2 x4x 1 Y7 a6 For. the same reason paths a4 x 5x 1 a3 and a6 x 6 a3 are not the transition paths either. 72 Logic and System Design, 4 2 3 Graph of FSM Next we construct a graph state diagram of FSM Mealy with. states marks a1 aM obtained at the first stage We have six such states a1 a6. in our example Thus the FSM graph contains as many states as the number of. marks we get at the previous stage Now we should define transitions between these. FSM has a transition from state am to state as with input X am as and output Yg see. the upper subgraph in Fig 7 if in ASM there is transition path P1. xmRm Yg as, Here X am as is the product of logical conditions written in this path.
X am as xm1 xmR m, In exactly the same way for the path a mYg a s we have a transition from state am to. state as with input X am as 1 and output Yg as the product of an empty set of. variables is equal to zero If for a certain r r 1 Rm symbol xmr or x mr occurs. several times on the transition path all symbols xmr x mr but one are deleted if for a. certain r r 1 Rm both symbols xmr and x mr occur on the transition path this. path is removed In such a case X am as 0, For the second transition path P2 FSM transits from state am to the initial state a1. with input X am a1 and output Y0 see the lower subgraph in Fig 7 Y0 is the. operator containing an empty set of microoperations. Figure 7 Subgraphs for transition paths P1 and P2, As a result we obtain a Mealy FSM with as many states as the number of marks we. used to mark the ASM in Fig 6 The state diagram of the Mealy FSM is shown in Fig. Figure 8 The state diagram of the Mealy FSM, 4 2 4 How not to loose transition paths Sometimes if ASM contains many. conditional vertices it is difficult not to loose one or several transition paths Here. Chapter 4 Algorithmic state machines and finite state machines 73. we give a very simple algorithm to resolve this problem This algorithm has only. 1 Find the first transition path leaving each conditional vertex through output. 1 For subgraph of ASM in Fig 9 we will get the following first path from state. a2 x1 x2 x5 Y6 a3, 2 Invert the last non inverted variable in the previous path return to ASM and.
continue the path if it is possible leaving each conditional vertex through. output 1 To construct the second path we should invert variable x5 We. cannot continue because we reached an operator vertex. a2 x1 x2 x 5 Y2 a3, We should construct paths in the same manner until all variables in a transition path. will be inverted For our example we will get the following paths. a2 x1 x 2 x5 x6 Y3 a4 a2 x1 x 2 x 5 Y2 a3 a2 x 1 x 3 x6 Y3 a4. a2 x1 x 2 x5 x 6 x7 x4 Y5 a5 a2 x 1 x3 x7 x4 Y5 a5 a2 x 1 x 3 x 6 x7 x4 Y5 a5. a2 x1 x 2 x5 x 6 x7 x 4 Y7 a4 a2 x 1 x3 x7 x 4 Y7 a4 a2 x 1 x 3 x 6 x7 x 4 Y7 a4. a2 x1 x 2 x5 x 6 x 7 Y5 a5 a2 x 1 x3 x 7 Y5 a5 a2 x 1 x 3 x 6 x 7 Y5 a5. Figure 9 Subgraph of ASM, 4 2 5 Transition tables of Mealy FSM The graph of Mealy FSM in Fig 8 has only 6. states and 16 arcs Practically however we must construct FSMs with tens of states. and more than one two hundreds of transitions In such a case it is difficult to use a. graph so we will present it as a table Table 1 for the same Mealy FSM has five. am a current state,as a next state,X am as an input signal. Y am as an output signal,H a number of line,74 Logic and System Design. Actually immediately from ASM we should write transition paths one after another. into the transition table In Table 1 xt is used instead of x t for the inversion of xt. Now we will discuss what kind of FSM we have received Our ASM G1 in Fig 6 which. we used to construct FSM S1 in Table 1 has seven logical conditions and ten. microoperations FSM S1 has seven binary inputs in the column X am as and ten. binary outputs in the column Y am as The input signal of this FSM Fig 10 is the 7. component vector the output signal of this FSM is the 10 component vector. Table 1 Direct transition table of Mealy FSM S1,am as X am as Y am as H.
a1 a2 x1x2x3 y1y3 1,a3 x1x2 x3 y6y7 2,a2 x1 x2 y1y2 3. a4 x1 y4 4,a2 a2 x4x1 y8y9 5,a6 x4 x1 y3y4 6,a4 x4 y4 7. a3 a6 1 y3y4 8,a4 a5 x5 y5y6y7 9,a2 x5x1 y8y9 10,a6 x5 x1 y3y4 11. a5 a2 x6 y8y9 12,a1 x6x7 y3y6y10 13,a1 x6 x7 14,a6 a1 x6 y6y7 15. a6 x6 y3y4 16,Figure 10 FSM as a black box, Let us take one of the rows from Table 1 for example row 3 and look at the behavior.
of FSM presented in this row Our FSM transits from state a1 into state a2 when the. product x1 x 2 1 It is clear that such a transition takes place for any input vector in. which the first component is equal to 1 the second component is equal to 0 The. values of other components are not important Thus we can say that the third row of. for description of the behavior of control units Next we will use algorithmic state machines to design Finite State Machines FSM with hardly any constraints on the number of inputs outputs and states 4 1 Flowcharts and Algorithmic state machines 4 1 1 Example of ASM An Algorithmic state machine ASM is the directed