STLD SHORT QUESTION

 WRITE THE SOLUTION FOR THESE QUESTION AND SUBMIT BEFORE LAB INTERNAL EXAMS. THESE QUESTIONS WILL BE ASKED FOR VIVA VOCE

FINATE STATE MACHINES

 

Finite State Machines are the fundamental building blocks of various digital and computing systems. They provide a systematic approach to model the behavior of sequential circuits. They also help to control various processes in digital systems.

Read this chapter to learn the components, types, advantages, and applications of finite state machines.

What is a Finite State Machine?

A Finite State Machine (FSM) is a mathematical model that is used to explain and understand the behavior of a digital  system. More specifically, it is a structured and systematic model that helps to understand the behavior of a sequential circuit that exists in a finite number of states at a given point of time.

In more simple words, a synchronous sequential circuit is also called as Finite State Machine FSM, if it has a finite number of states.

The transition of these finite states takes place based on the internal or external inputs that results in the predictable and systematic changes in the behavior of the system.

Components of a Finite State Machine

A typical finite state machine consists of the following main components −

Finite States

The finite states are nothing but the distinct modes or conditions in the given system. Each of these finite states represents a specific behavior. In digital system representation, these finite states are generally represented through symbols or labels.

States represent the different conditions or situations in which the system can exist. Each state defines a specific behavior of the system. The FSM can be in only one state at a time, and the total number of states is finite. States are represented as circles in diagrams and stored in memory elements (flip-flops). Example: Red, Yellow, Green lights in a traffic controller.

State Transitions

In terms of finite state machines, the state transition can be defined as the change from one state to another. This change in state or state transition takes placed based on some specific inputs or conditions. These state transitions are generally triggered by events which are associated with some rules or conditions and determine the next state of the system.

A state transition is the change from one state to another based on input conditions. These transitions are shown by directed arrows in the state diagram. Each arrow is labeled with input/output values depending on the FSM type (Mealy or Moore). Example: If input=1, the machine moves from state A to B; if input=0, it remains in A.

State Diagram

The state transition and the behavior of a finite state machine can be represented in a graphical form that is known as state diagram of the finite state machine.

Inputs

The inputs to the finite state machines are the external signals that trigger the state transitions in the system. These inputs are to be entered into the finite state machine by using sensors, user input devices like mic, keyboard, etc.

Inputs are external signals that control the state transitions of the FSM. They decide which next state the FSM should move to. Inputs can come from sensors, switches, or other circuits. Example: In an elevator, inputs are floor buttons or door sensors. 

Outputs

The results produced by the system as per the inputs and current states are known as outputs. These outputs of the system can be used to trigger events, control actuators, or to provide feedback to the external environment.

Outputs are the responses produced by the FSM based on its current state and inputs. Outputs may drive actuators, LEDs, or control signals. In Mealy machines, outputs depend on state + input; in Moore machines, outputs depend only on state. Example: A vending machine outputs 'dispense item' when correct coins are inserted.

In digital hardware, FSMs also include the following supporting components: Memory Elements (Flip-Flops): Store the current state of the FSM and update at each clock pulse. Combinational Logic: Generates next state and output based on current state and input. Clock Signal: Synchronizes state transitions at each clock edge. Reset Signal: Initializes the FSM to a known starting state when powered on

Types of Finite State Machine

There are two types of finite state machines namely,

• Mealy State Machine
• Moore State Machine

Let us now discuss these two types of finite state machines in detail.

Mealy State Machine

A Finite State Machine is said to be a Mealy state machine, if its outputs depend on both present inputs & present states. The block diagram of the Mealy state machine is shown in the following figure −

As shown in the figure, there are two main parts presents in the Mealy state machine. Those are combinational logic circuit and memory element. The memory element is useful to provide some part of previous outputs and present states as inputs to the combinational logic circuit.

Based on the present inputs and present states, the Mealy state machine produces outputs. Therefore, the outputs will be valid only at positive or negative transition of the clock signal.

State Diagram of Mealy State Machine

The state diagram of Mealy state machine is shown in the following figure.

In the above figure, there are three states, namely A, B and C. These states are labelled inside the circles and each circle corresponds to one state. State transitions between these states are represented with directed lines. Here, 0 / 0, 1 / 0 and 1 / 1 denote the input / output. In the above figure, there are two state transitions from each state based on the value of input.

In general, the number of states required in Mealy state machine is less than or equal to the number of states required in Moore state machine. There is an equivalent Moore state machine for each Mealy state machine.

Moore State Machine

A Finite State Machine is said to be a Moore state machine, if its outputs depend only on the present states.

The block diagram of the Moore state machine is shown in the following figure −

As shown in above figure, there are two parts presents in a Moore state machine. Those are combinational logic and memory. In this case, the present inputs and present states determine the next states. So, based on next states, Moore state machine produces the outputs. Therefore, the outputs will be valid only after transition of the state.

State Diagram of Moore State Machine

The state diagram of Moore state machine is shown in the following figure −

In the above figure, there are four states, namely A, B, C, and D. These states and the respective outputs are labelled inside the circles. Here, only the input value is labeled on each transition. In the above figure, there are two transitions from each state based on the value of input.

In general, the number of states required in Moore state machine is more than or equal to the number of states required in Mealy state machine. There is an equivalent Mealy state machine for each Moore state machine. So, based on the requirement we can use one of them.

Advantages of Finite State Machine

The Finite State Machines have several advantages in the field of digital electronics. All these advantages make them a crucial tool for modeling and implementing various digital systems. Some key advantages of Finite State Machines are listed below −

• Finite state machines provide a simple and systematic way to model and understand the behavior of digital systems with discrete finite states and transitions between them.
• Finite state machines support modular designs that help to breakdown the complex digital systems into smaller components. Each component of the finite state machine can represent a specific task of the entire system. This allows for easier design, testing, and maintenance.
• Finite state machines provide ease in terms of scalability that allows for addition of new states and transitions, and logics to the existing system without altering its fundamental structure or operation. This becomes essential when the system requirement evolve or expand.
• Fundamentally, finite state machines have a deterministic or predictable behavior. That means, we can easily determine the next state of the system from its current state and the inputs. This predictable behavior helps us to ensure the reliable and consistent operation of the system. It also makes the finite state machines best suited for real-time and safety-critical applications.
• Finite state machines are considered highly efficient in terms of both hardware and software implementations, as they require minimal hardware and software resources such as logic gates, memory, and other processing resources.
• Finite state machines support parallelism. This technology allows the occurrence of multiple states and state transitions simultaneously within the system. It also optimizes the performance and improves the responsiveness of the system.
• Finite state machines are versatile tools in the field of digital electronics and computer science, as they find their applications in various fields such as digital system design, control system design, software development, development of artificial intelligence, etc.

Applications of Finite State Machine

In the field of digital electronics and computer science, the finite state machines are used in various applications due to their ability to model sequential logic systems effectively. Here are some examples of applications of finite state machines −

• Finite state machines are commonly used in designing and implementation of different types of sequential logic circuits, such as digital counters, timers, control units, etc.
• Finite state machines are used in digital control systems to control and regulate the behavior of complex automated systems, like robots, industrial control and automation systems, etc.
• Finite state machines are used in the implementation of communication protocols like network protocols and state-based digital systems like data transmission and protocol converters.
• Finite state machines are also used in the field of software development to model and define the behavior of state-based systems in applications, to create user interfaces, to implement game mechanics, and to develop workflow management systems.