State Machine Design

Lets consider some sample problems which are best solved by State Machine designs...

1. If we have to design a digital logic to detect the sequence "10" in the input bit-stream ...
2. If Master M wants to communicate with Slave S, then Slave S can recognize the
    Master A out of many  masters by detecting some pattern.
    Let that pattern be Hex "F687" ...
3. If we have to detect the Even/odd No. of 1's in the input bit stream ...
4. If we have say, 5-bit input data and we have to detect the event -> " When the Sum
    of the 5-bit input data  is divisible by 5/7/9 etc "
5. State machines can also be used to generate source data at a rate, such that it is stable for at least
    1 complete cycle of the destination clock

There can be many such Problems in Real Chips which are resolved using State Machine design concepts only or In-addition to other concepts ....

Now, The question is .......

How State Machine design is done ?

1. Step 1 is to identify the No. of states that will be required to implement a state machine.
    This will depend on the kind of state machine you are going to build. For e.g. for
    detecting a sequence of  bits like "10" in the input bit-stream,
    How many states you will require ........?
    ....................................
    ..................................
    Think about it  ...........
     ..................................
     Think, if you can implement with lesser No. of states
     ...................................
     ..................................
2.  Now start from first state. This be the state when system starts after reset.
     Let first state name be = initial
     Conside both 1 and 0 inputs at this state and decide what should happen
     on receiving both the inputs respectively.
     In General, If we are moving closer to fully detect the pattern (means if we have 
     partially detected some part [few bit(s))of the full pattern] then we have to 
     move to the next state, otherwise we have to either stay at the same stay or we 
     have to move back to one state up OR 2 states up OR 3 states up depending on 
     the complete  pattern to be detected. 
    Few examples and some practice will clear this concept concisely.

     Another important aspect of the state machine design is whether we want the 
     output (to indicate PATTERN DETECTED ) to be High during transition b/w
     particular states or just For a particular State.
     This leads us to 2 types of state machines - Mealy OR Moore respectively.
      .........................
      Can you try to find which type of state machine will have more states ?
      ...........................
      ...........................
     
       For the pattern "10" detection, Below is our first state machine :

      Similarly, You can try creating Both Mealy and Moore machines for the examples
      given at the beginning of this topic.
      ## Remember Practice makes the man perfect

       Lets have some more discussion on these two types of state machines ::

       Mealy Machine ::

       - In a Mealy machine, the outputs are a function of the present state and the
          value of the inputs as shown in figure above.
ƒ       - Accordingly, the outputs may change  asynchronously in response to any
         change in the inputs .
          Why Asynchronously ? Think ...........
          Can you think of the kind of the Circuit the mealy machine will have ?
           .....................................

        Moore Machine ::

        - In a Moore machine the outputs depend only on the present state as shown in
           figure below.
        - More states than mealy but output is Synchronous with state

Quests to think about ........

          1. How can we map the states with the actual digital logic design elements ?
          2. Does more states means more logic is reqd. ?