5 SEQUENTIAL CikKCurt? using Moore and Mealy State Models, Stato tate Machine Charts. syeLagus tion, ‘Algorithmic M) Representation mneration and Detect nite State Machine (FSI FSM for Sequence Ge! gasic Design Steps. Fi Minimization, Design of l ween Moore and Mi at) List the comparison bet Mealy Model Answer : S.No. i is tion of present T output a is function of present | Its output is a funel [veo J cas well as past input @ | input changes does not affect the | Input changes may affect the output output. of the circuit. ve model requires more number | It requires less number of states for jing same function. » @) | Moo: 1 vectates. for implementing same | implement function. 2) Describe about sequence detector: ‘or machine which is used to detect the desired be detected, we can draw the state diagram Answer = -e detector” is a clocked sequential circuit output = 1, whenever ‘The “sequenc binary sequence. Once we know the sequence which is to fo 1. From the state diagram, we can design the circuit. Generally it produces an it detects the desired input sequence and ‘0’ in other cases. Q3) What is state assignment? Answer + To generate the desired next state for a particular present state and Inputs, it is necessary have it Is necessary to represent states in the state specific flip-flop inputs. These flip-flop inputs functions, diagram using binary values instead of alphabets. This procedure is known as “state assignment”. Q4) Write the two basic rules for making state assignments. Answer ; Basically there are two rules for making state assignments .n should have assignment in such RULE | : ULE I: state having the same next states for a given Input condlitio way, that they can be grouped into logically adjacent cells in a K-map. Scanned with CamScannerRULE II: States that are the next states of a single state should be assigned Im such @ Way that they €an_be grouped into logically adjacent cells ina K-map Q5) Define Algorithmic State Machine (ASM) charts. Answer : The state diagrams and state tables described earlier are convenient for describing the behaviour of Finite State Machine (FSM) that have only a few inputs and outputs. For larger machines, we often use a different form of representation, known as Algorithmic State Machine (ASM) charts. 6) Compare ASM charts and state diagrams? Answer The following are the some of comparisons between ASM charts and state diagrams, (1) "ASM charts are (2) The state diagrams or bubble diagrams are compact but difficult to read i.e., sequential operations can be easily described using ASM charts as compared to state diagrams. (3) The construction of an ASM chart is more or less mechanical in nature. (Structured approach), (4) Due to it’s structured approach, the construction of ASM charts for complex system will be easier than drawing a state diagram. (5) The state box is equivalent to the state in a sequential circuit and the decision box is equivalent to the binary information written along the directed lines connected between two states. ahtly longer, Q7) Write the advantages of FSM. Answer : The advantages of Finite State Machine include the following, (1) Finite state machines are flexible. (2) Easy to move from a significant abstract to a code execution. (3) Low processor overhead. (4) Easy determination of reach ability of a state., Q2) List the disadvantages of FSM. Answer : Tne disadvantages of the finite state machine include the following, The expected character of deterministic finite state machines can be not needed in some areas like q@ computer games. (2) The implementation of huge systems using FSM Is hard for managing without any idea of design (3) Not applicable for all domains. (4)__The orders of state conversions are inflexible. Q9) What are the basic components of ASM? Answer : Following are the three basic components of ASM charts, (1) State box. (2) Decision box. (3) Conditional output box. Scanned with CamScannerSM thang se of | saventages Of ASM ch; te ‘art include the following, ¢y to understand, e have one OF More equivalent forms. my gescribe Both combinational ang a Sequential circutts, structured approach to vicy alize a sequential Problem, the ASM chart shown below, For derive the » diagram, 1/100 oft 1/10 ‘State Diagram forabove ASM Chartin fig. BI State Diagram for Scanned with CamScannera 5.1 BASIC DESIGN STEPS Q12) Explain the basic design steps for the analysis of synchronous sequantial circuit with an example Answer : The analysis of sequential circuits is used to determine the next state and output functions so 4, the behaviour of the circuit can be predicted. Analysis provides tabular descriptions of sequential circys, These are particularly useful when sequential circuits are to be designed. The suggested analysis procedure of a sequential circuit is given below, Step |: Draw the given logic schematic diagram. : Determine the excitation equations for the flip-flop control inputs,-from the logic diagram, Step Il Step Ill : Substitute the excitation equations into flip-flop characteristics equations to get transition equations. Step IV : Use the, transition equations to construct ‘a transition table. Step V : Determine the output equations. Ser VI : Add the output values to the transition table for each state (Moore model) or state/inpu jon/output table. combination (Mealy model) to create a tran: Step VII : wame the states and substitute state names for state variable combinations in the transitcw output table to get state/output table. Step VIII : Draw a state diagram corresponding to the state/output table, Scanned with CamScannerwo ' ge MACHINE , tion : When the output of i "| & sequential oA egerred aS Moore circuit op Moore ma, 6 Diagram of Moore Machine g0m sized to the clock, since the a", only when the state ch, on in Figure 2. The outp, then the output changes are only and can therefore ciybut remains stable during any input change MS Of Moore model cireuit t " : re circults, Le. Input changes do 1 behaviour than those of x0 Sult In unwanted glitches ‘ally expressed as, Moore machine can be mathematic ‘The next state is determined uniquely by the present state and present inputs. Thus, Ae + 1) = HAW, xCH} 4 The ‘Output function, Y(t) is a function of only the present state and is independent of the external input. YY) = 9f Qt} Mey Machine ‘tition : when the output of the sequential circuit depends on the present state of the flip-flop and "tHe inputs then the Sequential circuit Is referred as a Mealy circuit or Mealy machine. ck Diag 'm of Mealy Machine : The Figure 3 shows the simple block diagram of a Mealy machine. Scanned with CamScanner5.10 . DIGITAL ELECTRONICS Q(t 4 4) Inputs. QW Output decoder Next state Memory | decoder [Blea i TE Bloc Diggram of Mealy Machine ‘The output Q(t) can change at any time i.e., either the input (or) state changes, since Q(t) is a function * both. This gives rise to Y(t) an unexpected output change at T, and T, as shown in Figure 4, unwanted litches result. . To Tt T % Ts 15 col] L jc ge State A BTA T T T Input x(t) 0. H Output yy) | iL — EE Te oe] Since output Y(t) is a function of input and present state, so Y(t) changes with change in either inpt r) present state. . Mealy machine is mathematically expressed as, ) The next state Q(t + 1) is determined uniquely by the present state Q(t) and present inputs x(t Thus, At + 1) = Q(t), x(t)} Where, f = State transition function. ) The value of output function Y(t) is a function of present state Q(t) and input x(t). Y(t) = 9{Q(t), x(t)} Where, Scanned with CamScannersequential ci aa cults - (unit. yy Inputs, Outputs = Combinational logic => BESET T]_Biek Dagan Meal Sate ofa] ased on the current input: 'S as well as states, ane suitable only at positive otherwise negative a Machine can produce outputs. Thus, gam is shown Figure 2, @ of the CLK signal. the outputs The mealy state machine's state wa ate Diagram o ioe The state diagram of mealy state machine mainly includes three states namely A, B, and C, These every circle communicates with one state. Conversions \es. In the figure 2, the inputs and outputs are denoted there are two conversions from every state. se states are tagged within the circles as well as ‘mong these three states are signified by directed lint wth 0/0, 1/0, and 1/1. Based on the input value, machine is below or equivalent to the number Generally, the amount of required states in the mealy | Moore state machine for every Mealy state ‘required states in Moore state machine. There is an equal rathine, As a result, based on the necessity we can employ one of them. Voor Stare oF FSM When the outputs depend on current state: TeMaore state machine's block diagram is shown *1two parts namely combinational logic as well 25 memory. Inputs >} combinational logic 15 then the FSM can be named as Moore state machine. Figure 3. The Moore state machine block diagram consists Outputs Memory ——a aay Rare Scanned with CamScannerae $$ orig Thus, d oy a decide the next state teDending Tr this case, the current Inputs, as well as current statess oF this wll Be ApPIICDIE sing . 0 Je shown Figure 4. 19 the abo, fate the outputs. nea achine state daar? B,C, and D. the four stage, te machine nam on further states, this machine will gener after the conversion of the state, The Moore state Mm state, the diagram includes four states like a mealy stat ‘as well as individual outputs are placed in the circles. 1/0 0 [DEED ccs ofttoree Sate Machine iv In the Figure 4, there are four states, namely A, B, € & D. These states and calc ve tas are labeled inside the circles. Here, simply the input worth Is marked on every one elas 4 Includes two conversions from every state depending on the input value. Generally, the amo required alent to the required number of states in the mealy states in this machine Is greater than otherwise eq state machine, Generally, the number of required states in this machine Is more than otherwise equivalent to the required states in Mealy State Machine (MSM). For every Moore state machine, there is @ corresponding Mealy state machine. Consequently, depending on the necessity we can utilize one of them. There is an equal mealy state machine for every Moore state machine. As @ result, based on the necessity we can employ one of them. 5.3 STATE MINIMIZATION G16) Wrtie short notes on state minimization along with partitioning minimization procedure. Answer : In implementing the logic diagram from state diagram (or table) of a finite-state machine, the diagram may contain redundant states, i.e., states whose functions can be accomplished by other states. The number of memory elements required for a realization of the machine Is directly related to the number of states. Consequently, the minimization of the number of states does in many cases reduce the complexity, number of gates and flip-flops and finally the cost of the final circuit. Therefore, it is necessary to determine the different techniques for transforming a given machine into another machine which has no redundant states, so that both the machines have the same terminal behaviour i.e., same outputs and next states. Partmioninc Minmization PROCEDURE The objective of this section is to describe a procedure for determining the sets of equivalent states of @ specified machine M. The result sought is a partition on the states of M such that two states are in the same block if and only if they are equivalent. The following steps illustrate the minimization procedure: Step 1: Let us partition the states of M into subsets, such that all states in the same subset are 1- equivalent This is accomplished by placing states having identical outputs under all possible inputs in the same subset. Clearly two states which are in different subsets are ,1-distinguishable, Scanned with CamScannerrs ancpre) ee ACE) (pry Fact) ep) Fy AC) @) aD) ry he Ace mmr rhe fist partition Pe corresponds to O-distinguish at. P is obtained ee by inspecting the table and placing those states having the same outputs, yell inputs, in the same block. Thus, A, C and & are in. the same block, since their outputs under outs are 0 and 1 respectively. A similer argument pisces 8, D and F in the other block. Clearly, esablishes the sets of states which are 1-equivalent, ‘ability and it is priority to the application of any se 2: Let us obtain the partition P, whose block consists of the sets of states, which are 2-equivalent, s equivalent under any input sequences of length 2. This equivalent if and only if they are sve I, are also 1-equivalent. Consequently, accomplished by observing that two states 1+ equivalent and their 1j successors for all two states are placed in the same block of P, if and only sey are in the same block of P, and for each possible 1, and their I, - successors are also contained = of Py This step is carried out by splitting blocks of P, whenever their successors are not contained +zcommon block of P, ‘The 0 - and 1 - successors of (ACE) are (CE) and (BDF) respectively and since both are contained ‘enmon blocks of P,, the states in (ACE) are 2-equivalent and therefore (ACE) constitutes a block in Te Issuccessor of (BDF) is (DBC), since (BD) and (C) are not contained in a single block of P,, the % (BDF) must be split into (BD) and (F), so that the successors of the blocks in the required partition ‘quivalent. '® 3: In @ similar manner P, is obtained by split 1g the block (ACE) of P, into (AC) and (€) since the “utessors of A, C and E are D, B and F, which are not 2-equivaient In general, the P,,, partition is obtained from P, by placing in the same block of P,,. those states “ch are in the same block of P, and whose Ij-successors for every possible Ij are also in a common “of P,, This process places in the same block the states that are (k + 1) equivalent and in different “states that are (k + 1) distinguishable One observation fcs that, no state can belong to more than “block, since this would make It distinguishable with respect to itself. Pyaz = Py the process terminates and P, defines the sets of squint states Machine, 1.e,, all states contained In the same block of P, are equivalent, while stares Belonging Cifferent blocks aA distinguishable. P, is thus called “the equivalence partition ene eee “Cure is rejected to as the Moore reduction procedure. For machine M,, P3 Is the ed! Thence States A and C are equivalent and also B and D. For example, for k, the Scanned with CamScanner[I erie] 5.5 ALGORITHMIC STTE MACHINE CHARTS Q22) Describe about the Algorithmic State Machine (ASM) chart: Answer : The state diagrams and state tables described earlier are convenient for describing the behaviour of Finite State Machine (FSM) that have only a few Inputs and outputs. For larger machines, we often use 2 different form of representation known as Algorithmic State Machine (ASM) charts. This chart is a type of flow chart which can be used to represent the state transitions and generated outputs for an finite state machines. The ASM charts consist of three basic components, the state box, the decision box and the conditional output box. A collection of these components forms an ASM block which corresponds tc @ single state time. The events within a ASM block occur simultaneously. The overall behaviour of an ASV is then described by a collection of ASM blocks, denoting a sequence of time intervals. This collection form: the ASM chart. . State Box A rectangle represents a state of FSM and is equivalent to a node in the state diagram or row ir the state table. The Moore type outputs are listed inside the box. The state is given a symbolic nam which is placed at upper left corner of the box. The binary code assigned to the state is placed at th upper right corner as shown In Figure 1. Entry Path Xxx «State Code x <—{— State output J (Moore Type) State Name This single exit path from a state box can lead to a state box or a decision box. If it leads direct) to @ state box, then there Is an unconditional state transition upon the occurrence of the next clock period. On the other hand, if It leads to a decision box, then interrogation of the system Inputs occurs during the current state time and next state and/or present outputs of the system depends upon the status of these signals. Decision Box The basic function of a decision box Is to provide for next state alternatives and conditional ‘outputs based on the logic value of a Boolean expression involving the external input variables and stat information variables. The boolean expression appears as the entry in the decision box. Based on t! ; result of the boolean expression, there are two exit paths, one for each of the two possibilities. The ex! paths can lead to state boxes, other decision boxes or conditional output box. Scanned with CamScannerFn ae synchronous Sequential circuit 7 [Watt - vi Entry path Eonaition pression a Condition True Condition False se exit Path Exit Path a) Conomonat. Output Box bbe outputs that are dependent on one oF more inputs are listed in the box with immediate and delay path and there must be only a single The ae wenn, Coneitional output box Is used t0 descri rel as the state of the machine.-The conditional outputs operations permitted, The input to the box must be 2 conditional ext exit_path, 223) Implement ASM block ‘along with its equivalent state diagram. Answer : g of one state box and all the’ decision and conditional boxes ‘any number of output paths represented ists of one or more interconnected blocks. decision boxes and one ‘ASM block Is a diagram consistin: connected to its exit path, An ASM block has one entrance and by the structure of the decision boxes. An ASM block diagram cons! Example of an ASM block is shown in Figure 1. Associated with state T, are two conditional box. The diagram distinguishes the block with dashed lines around the entire block diagram, but this is not usvally done, since the ASM chart uniquely defines each block from its structure. A state box without any decision or conditional boxes contains a simple block. "ASM Block, Each block in the ASM block-diagram describes the state of the system durin unite the system is in state T, The same clock pulse also moves the system rete te one ttre next States, Ty, T, or T, as controlied by the binary values of & and F. controler fo one of the next ‘The ASM block diagram Is similar to 2 state diagram. Each state block Is equi a sequential ercuit. The decision box. = equivalent to the binary information written ae cane Tee that connect two states in avstate dram. AS a consequence, It is sometimes wey te comune ne rol logic. : . t Scanned with CamScannerDIGITAL ELECTRONICS, 5.26 in Figure 2. The three states or exemple, the ASM chart of Figure 1s drawn as a atate diagram I " cap tcoa orale " _ directed lines indicate the ‘ces, The are symbolized by circles with thelr binary values written Inside the circles. operations that mu conditions that determine the next state, The unconditional and conditional operations t ist be performed are not indicated In the state diagram. fe weren) JEST eT Q24) Draw ASM block diagram of Mealy and Mooro circuits. Answer : ASM Bvock Diacram oF Meaty Circurr ‘The ASM diagram and corresponding state diagram for a Mealy circuit Is presented in Fig. 1(2), (b) respectively. fj) CF (a) ASM Diagram In the ASM diagram, note that output Z Is specified in conditional output boxes, one for each stat and input combination. This corresponds to associating the output with the arcs of the state diagram: (b) Equivalent Sate Diagram Equivalent State Diagram for Mealy Circuit Scanned with CamScannergeimee ol Cirevits [Unit = V] ASM Buock Duscran oF Moore Circurr The ASM diagram and corresponding state diagram for a Moore circuit is ») respectively b) Equivalent Sate Diagram te) AEM Biegrem (b) &q a ‘ere no conditional output boxes in the ASM diagram. The outputs of a Moore circult tne state variables and are therefore specified within the state boxes in the ASM nodes of the state diagram. re that tere only tne Scanned with CamScanner