Finite state machines

Finite State Machines (FSM)
Finite State Machines (FSMs) are a useful abstraction for sequential circuits with centralized states of operation. At each clock edge, combinational logic computes outputs and next state as a function of inputs and present state. Finite-state machines provide a simple computational model with many applications. It is a circuit with internal states.

<
Fig1: Diagram of Finite State Machines (FSM)

Finite State Machine Entities
Finite State Machine is specified by five entities:
1. Symbolic states
2. Input signals
3. Output signals
4. next-state functions
5. Output functions

A state specifies a unique internal condition of a system. As time progresses, finite state machine transits from one state to another. The new state is determined by the Next-State function, which is a function of the current state, and input signals. In a synchronous finite state machine, the transition is controlled by a clock signal, and can occur only at the triggering edge of the clock. The ouput function specifies the values of the output signals. If it is the function of a state only, it is called Moore output, while if it is a function of the state and input signal, the output is known as Mealy Output.

Applications of Finite State Machine
1. It is significant for understanding the decision making logic as well as the control of digital systems.
2.  Used for sequential logic roles.
3. Used by software developers to summarize the performance of a difficult system.
4. For problem solving in different fields like mathematics, games, linguistics and artificial intelligence.
5. Network protocols 
6.  Construction of Vending machines, traffic lights, controllers in CPU, text parsing
7. Recognition of speech and language processing

ADVANTAGES OF FINITE STATE MACHINE
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.

LIMITATIONS  OF FINITE STATE MACHINE
1. The expected character of deterministic finite  state machines may not be needed in some areas like computer games.
2. The implementation of huge systems using finite state machine could be very difficult without a knowledge of design.
3. Not applicable for all domains
4. The order of state conversion are inflexible.

TYPES OF FINITE STATE MACHINE
These are basically two:

1. Mealy State Machine:  This is a finite-state-machine whose output values are determined both by its current state and the current inputs. It is also often used for transducer.  It is names after Mealy George H. Mealy (1965). The block diagram of Mealy state machine consist of combinational logic and memory. The memory can be used to provide some of the previous outputs as combinational logic inputs.

Fig 2: Block Diagram of Mealy state machine

Fig 3: State diagram of Mealy state machine

2. Moore State Machine: This is a finite-state-machine, whose output values are determined solely by its current state. The block diagram of Moore state machine consist of combinational logic and memory.

Fig 4: Block Diagram of Moore state machine

Fig 5: State diagram of Moore state machine

Moore machines may be safer to use, because they change states on the clock edge (if you are using DFF logic for present and next state), whereas Mealy machines are faster, because the state is dependent on the input. Thus, the state can change asynchronously. This comes down to predictability vs raw speed.

TERMINOLOGIES

A level-to-pulse converter: This produces a single cycle pulse each time its input goes high. Its a synchronous rising-edge detector.

Fig 6: Moore FSM circuit implementation of level-to-pulse converter:

Transducer:  A device that converts variations in a physical quantity, such as pressure or brightness into an electrical signal or vice versa. It Maps input sequences to output sequences.  Transducers can also be seen as an electronic device that converts energy from one for to another. Simple examples includes: microphones, loudspeakers, thermometers, position and pressure sensors, and antenna

Transducer efficiency is defined as the ratio of the power output in the desired form to the total power input. Mathematically, if P represents the total power input and Q represents the power output in the desired form, then the efficiency E, as a ratio between 0 and 1, is given by:

E=Q/P
.

State Transition Graph:  This is a graph consisting of circles to represent states and directed line segments to represent transitions between states.
Turing machine: a finite-state controller with a movable read/write head on an unbounded storage tape.  it is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules.  It was named after Alan Turing (1936). Despite, its simplicity, Turing machine can simulate any computer algorithm, no matter how complicated it is.

An Edge-Detector:

The function of an edge detector is to detect transitions between two symbols in the input sequence, say 0 and 1. It does this by outputting 0 as long as the most recent input symbol is the same as the previous one. However, when the most recent one differs from the previous one, it outputs a 1. By convention, the edge detector always outputs 0 after reading the very first symbol.

Finite-state machines VS Turing machine

Finite-state machines also called finite-state automata (singular: automaton) or just finite automata are much more restrictive in their capabilities than Turing machines. For example, we can show that it is not possible for a finite-state machine to determine whether the input consists of a prime number of symbols. Much simpler languages, such as the sequences of well-balanced parenthesis strings, also cannot be recognized by finite-state machines. One way to view the finite-state machine model as a more restrictive Turing machine is to separate the input and output halves of the tapes.

State Transition Diagram:  State transition diagram is a useful Finite State Machine representation and design aid. A state transition diagram is a directed graph which can be constructed as follows:

-there is a node for each state in Q, which is represented by the circle.
- there is directed edge from node q to node p labeled a if &9q,a0=p
- in the start state, there is an arrow with no source.
-Accepting states of final states are indicated by a double circle.

Fig 7: State Transition diagram

Arcs leaving a state are mutually exclusive, i.e., for any combination input values theres at most one applicable arc.
Arcs leaving a state are collectively exhaustive, i.e., for any combination of input values theres at least one applicable arc.
So for each state: for any combination of input values theres exactly one applicable arc
Often a starting state is specified
Each state specifies values for all outputs

Modeling the Behavior of Finite-State Machines

There are several different notations we can use to capture the behavior of finite-state machines. These include:

As a functional program mapping one list into another.

As a restricted imperative program, reading input a single character at a time and producing output a single character at a time.

As a feedback system :  Through representation of functions as a table and representation of functions by a directed labeled graph

NOTE

Homomorphism is a structure-preserving map between two algebraic structures of the same type.