Micro-controllers-FSM –Finite State Machine-Tutorials and Examples-1

Tutorials Overview

Finite State Machine is a tool to model the desired behavior of a sequential system.

•The designer has to develop a finite state model of the system behavior and then designs a circuit that implements this model
•A FSM consists of several states. Inputs into the machine are combined with the current state of the machine to determine the new state or next state of the machine.
•Depending on the state of the machine, outputs are generated based on either the state or the state and inputs of the machine.

Structure

1. X represents the range of possible input values (2n) 
2. Y represents the range of output values (2m) 
3. Q represents the range of the possible states of the system (2k) 
4. Transfer functions: 

–f: X x Q -> Y
–g: X x Q -> Q

More Links:
Finite State Machine-Tutorials and Examples-2
Mealy and Moore machines
Finite State Machine-Digital Electronics
Embedded programming-Micro controller based Systems

Picture Representation:

1. FSM = (X, Y, Q, f, g) 
2. –If there is no state in the Q range (Q≡Ø, the circuitry has no history), then: 
3. g: X x Ø->Ø, there is no state transition function 
4. f: X x Ø -> Y is becoming f: X -> Y 
5. –In this case, the FSM is equivalent to an CLC 
6. FSM| Q≡Ø = CLC = (X, Y, f)

Asynchronous vs. Synchronous

1. Async FSM – the next state becomes the present state after the   delays through the delay elements 
2. Sync FSM – obtained by replacing the delay elements di with    memory elements (registers). The wi bits of the next state will be  written in the registers (memory elements) only on the clock (on  edge or level) is applied.

Sync FSM with immediate outputs



The FSM where the outputs, after they have been calculated, are used immediately (of course in the stable period of the state interval), is called an immediate state machine.

Note:
The FSM where the outputs, after they have been calculated, are used immediately (of course in the stable period of the state interval), is called an immediate state machine.

Sync FSM with delayed outputs

The next state is assigned as present state on the next clock cycle. Similarly, we can proceed with the outputs, obtaining the delayed state machine. Each bit of the output is passed through a memory element.

Note:

The next state is assigned as present state on the next clock cycle. Similarly, we can proceed with the outputs, obtaining the delayed state machine. Each bit of the output is passed through a memory element. Through this memory elements, whenever the t+1 clock cycle is applied, the values calculated by CLC (function f) for t interval are assigned to the output (Y(t+1) := Y(t) ). By doing this we can obtain outputs unaffected by combinatorial hazard.