# Chapter 5_State Machines_Part 2

Views:

Category: Education

## Presentation Description

This gives the implementation of pattern detector.

## Presentation Transcript

### Chapter 5_Design of State Machines_Part 2.:

Chapter 5_Design of State Machines_Part 2. Part 2- Implementation of State Machines.

### Design & Implementation of Motor Rotation Sensing Machine.:

Design & Implementation of Motor Rotation Sensing Machine.

### Basic approach of a rotation sensing Machine:

Basic approach of a rotation sensing Machine As can seen from Figure 5 there are two Sensors 1 and 2 which are so spatially placed that they generate a square wave with 90 degree phase shift corresponding to P1 and P2. When both are ‘00’ then Negative Rotation changes this to ‘01’ and Positive Rotation changes this to ‘10’.

### Comparison of Mealy and Moore Machines while designing ‘10’ pattern detector.:

Comparison of Mealy and Moore Machines while designing ‘10’ pattern detector.

### Problem 1 : Our customer has asked for ‘10’ Sequence Detector . This should give an output HIGH only when ‘10’ sequence is detected.:

Problem 1 : Our customer has asked for ‘10’ Sequence Detector . This should give an output HIGH only when ‘10’ sequence is detected. We will design a FSM(Finite State Machine) which checks for ‘10’ pattern and when such a pattern is detected it gives an output HIGH otherwise output is maintained LOW. We can take both Mealy Machine approach as well as Moore Machine approach.

### First let us consider Mealy Machine State Diagram given on the left of Figure 6.:

First let us consider Mealy Machine State Diagram given on the left of Figure 6. Mealy Machine State Diagram lists the input/ associated_output on the state transition arcs. There are two distinct states: ‘ initial’state and ‘1’ state.

### Mealy Machine State Diagram:

Mealy Machine State Diagram When input is 0 , machine remains in ‘initial’ state. When input is 1 , output is LOW and machine makes a transition to state ‘1’. If input is again ‘1’, the pattern is ‘11’ and output remains LOW and machine continues in state ‘1’. But if instead of ‘1’ the second input is ‘0’ then we have obtained the desired pattern ‘10’. Hence output goes HIGH and machine is RESET therefore it reverts to ‘initial state’.

### Let us consider Moore Machine State Diagram given on right hand side of Figure 6.:

Let us consider Moore Machine State Diagram given on right hand side of Figure 6. A Moore Machine produces an unique output for every state irrespective of inputs. Accordingly the state diagram of the Moore Machine associates the output with its respective state in the form state-notation/output-value. State transition arrows of Moore Machine are labeled with the input value that triggers the transition.

### Moore Machine State Diagram:

Moore Machine State Diagram there are three distinct states: ‘initial’ , ‘1’ and ‘10’. In the state ‘initial’, output is LOW. If the first input is 0 , machine remains in ‘initial’ state. If the first input is 1 then this input triggers the transition to the second state ‘1’ and since the desired pattern is not achieved therefore output remains LOW but we have moved one step in the direction of desired detection. If the second input is 1, we remain in state ‘1’ and output remains LOW. We continue to remain in state ‘1’ because we can hope to detect ‘10’ pattern at the third input. But if second input is 0, we have hit the Jack Pot. Hence we move to the third state ‘10’ which corresponds to output HIGH. If the third input is 1, we revert to state ‘1’ because at fourth input = 0 we can again hit the Jack Pot. But if the third input is 0 at the fourth input we can never hit the Jack Pot hence we reset to ‘initial ‘state.

### Problem 2 : My customer has asked for ‘111’ Sequence Detector . This should give an output HIGH only when ‘111’ sequence is detected.:

Problem 2 : My customer has asked for ‘111’ Sequence Detector . This should give an output HIGH only when ‘111’ sequence is detected.

### the state diagram of a ‘111’ detector Mealy Machine:

the state diagram of a ‘111’ detector Mealy Machine This Finite State Machine has three distinct states: Initial State, Got-1 state and Got-11 state. Initial state should clearly be a reset state where input is 1 and output is 1. When first input is 0, machine remains in initial state with output LOW. When first input is 1, output remains LOW but FSM makes a transition to Got-1 state. The machine is one step nearer the Jackpot. When second input is 0, output remains LOW and machine reverts back to Initial State. When second input is 1, output remains LOW but now it is two steps nearer the Jackpot hence FSM makes a transition to Got-11 state. When third input is 0, output remains LOW and the FSM resets as there is no chance of hitting the Jackpot at the fourth input. But when third input is 1, the Jackpot is hit and output is HIGH but FSM remains at Got-11 state because at the fourth input , if 1, it can again hit the Jackpot.

### Circuit Implementation of ‘111’detector Mealy Machine:

Circuit Implementation of ‘111’detector Mealy Machine

### Timing Diagram for ‘111’ Sequence Detector. :

Timing Diagram for ‘111’ Sequence Detector.

### the operation of Mealy Machine as ‘111’ detector.:

the operation of Mealy Machine as ‘111’ detector. Initially A and B are in reset condition. Hence Qa and Qb are LOW and Qa * and Qb * (the complements) are HIGH. Initially X= 0. So initial condition is defined as X=0, Da =0,Db=0,Qa=0 , Qb =0 and Z=0. This is ‘initial state AB=00’. Next suppose X =1. This is second state ‘Got-1_AB=01’. As seen from Figure 9, Db = X.Qa *. Qb * and Da = X.Qa + X.Qb . And Z = X.Qa Hence first input HIGH makes Db HIGH but Da remains LOW. Therefore in second state we have AB=01 and Z=0.

### ‘111’ detector cont’d:

‘111’ detector cont’d Suppose the second input is also X = 1. Now as soon as Clock appears, at the lagging edge of the Clock(since Clock has a bubble) Db=1 is entered into Db Flip Flop. Hence Qb =1 and Qb * =0. So Da = 1 and Db = 0. At the next clock A_FF is set and B_FF is reset. Therefore Third state is ‘Got-11_AB=10’. And if X continues to be HIGH then Z= 1. Thus a string ‘111’ is detected and output is HIGH.

### State Transition Table of Mealy Machine as ‘111’ string detector.:

State Transition Table of Mealy Machine as ‘111’ string detector. State X Da Db Qa│N Qa│N+1 Qb│N Qb│N+1 Z│N Initial 0 0 0 0 0 0 0 0 Got-1_AB=01 1 0 1 0 0 0 1 0 Got-11_AB=10 1 1 0 0 1 1 0 0 Got-11_AB=10 1 1 0 1 1 0 0 1

### ‘FALSE HIGH’ known as ‘OUTPUT GLITCH’.:

‘FALSE HIGH’ known as ‘OUTPUT GLITCH’. As can be seen in Figure 9 , X remains HIGH for some time when A_FF is SET and B_FF is RESET at the third Lagging Edge of the Clock. This gives a ‘FALSE HIGH’ known as ‘OUTPUT GLITCH’.

### Design of Moore Machine as ‘111’ sequence detector.:

Design of Moore Machine as ‘111’ sequence detector.

### four distinct states:

four distinct states First is the initial state/output =0 when the system is in RESET condition. Second is ‘1’/0, when a string ‘1’ is detected and output is LOW. Third is ‘11’/0 when a string ‘11’ is detected and output is still LOW. Fourth is ‘111’/1 when a string ‘111’ is detected and output is HIGH. We have hit the Jackpot. We have shown how it reverts back to a former state when 0 is inputted. This happens four times as shown by arcs.

### State Table of Moore Machine as detector of ‘111’sequence.:

State Table of Moore Machine as detector of ‘111’sequence. State description output Initial Initial/0 0 Got-1 ‘1’/0 0 Got-11 ‘11’/0 0 Got-111 ‘111’/1 1

### State Transition Table and Output Table.:

State Transition Table and Output Table. Present State Next State Output - X = 0 X = 1 Z Initial Initial Got-1 0 Got-1 Initial Got-11 0 Got-11 Initial Got-111 0 Got-111 Initial Got-111 1

### We will use J-K FF and D-FF for the implementation Moore Machine as ‘111’ string detector. Table 4 and Table 5 give the excitation table for J-K_FF and D_FF. [Q(N) is the output before the clock and Q(N+1) is the output after the clock] :

We will use J-K FF and D-FF for the implementation Moore Machine as ‘111’ string detector. Table 4 and Table 5 give the excitation table for J-K_FF and D_FF. [Q(N) is the output before the clock and Q(N+1) is the output after the clock]

### Excitation Table of J-K_FF :

Excitation Table of J-K_FF J K Q(n) Q(n+1) Comment 0 × 0 0 When J =0 then K=0 gives NO CHANGE condition and K=1 gives RESET. Hence O/P is 0 if Q(N)=0; 1 × 0 1 When J =1 then K=1 gives TOGGLE condition and K=0 gives SET. Hence O/P in either case is 1 if Q(N)=0; × 1 1 0 When K=1 then J=1 gives TOGGLE and J=0 gives RESET. Hence O/P is 0 in either case if Q(N)=1; × 0 1 1 When K=0 then J=1 gives SET and J=0 gives NO CHANGE . Hence O/P is 1 in either case if Q(N)=1;

### Excitation Table of D_FF:

Excitation Table of D_FF D Q(n) Q(n+1) 0 0 0 1 0 1 0 1 0 1 1 1

### Combined Truth Table of J-K_FF and D_FF.:

Combined Truth Table of J-K_FF and D_FF. - J K Q(N+1) D Q(N+1) No change 0 0 Q(N) 0 0 RESET 0 1 0 1 1 SET 1 0 1 TOGGLE 1 1 Q(N)*

### Excitation Table for the Moore implementation.:

Excitation Table for the Moore implementation. Present State Input Next State FF_ Inputs Output A B X A B Ja Ka Db Z 0 0 0 0 0 0 × 0 0 0 0 1 0 1 0 × 1 0 0 1 0 0 0 0 × 0 0 0 1 1 1 0 1 × 0 0 1 0 0 0 0 × 1 0 0 1 0 1 1 1 × 0 1 0 1 1 0 0 0 × 1 0 1 1 1 1 1 1 × 0 1 1

### Simplifying Table 7 using Karnaugh’s Map we get the following Logic Functions.:

Simplifying Table 7 using Karnaugh’s Map we get the following Logic Functions. Ja = X.B Ka = X* Db = X(A+B*) Z = A.B The output is a function of current state only.

### A Moore Machine Logic Circuit and FF configuration for ‘111’ sequence detector.:

A Moore Machine Logic Circuit and FF configuration for ‘111’ sequence detector.

### Timing Diagram for Moore Model of string detector.:

Timing Diagram for Moore Model of string detector.

### Conclusions of Moore Machine:

Conclusions of Moore Machine The Timing Diagram for Moore Machine is shown in Figure 12. There is no output glitch in Moore Model. This is because the output depends on clearly defined states of the Flip-Flop which are synchronized with clock. The outputs remain valid through out the logic state. State Machine implementation of string detector of any size ‘11’ or ‘111’ involves much less clock cycles as compared to the same string detector implemented on CPU of a Personal Computer. 