Skip to main content

Finite State Machine

Definition

A machine consisting of a set of states, a start state, an input, and a transition function that maps input and current states to a next state. Machine begins in the start state with an input. It changes to new states depending on the transition function. The transition function depends on current states and inputs. The output of the machine depends on input and/or current state.

There are two types of FSMs which are popularly used in the digital design. They are
  • Moore machine
  • Mealy machine
Moore machine

In Moore machine the output depends only on current state.The advantage of the Moore model is a simplification of the behavior.

Mealy machine

In Mealy machine the output depend on both current state and input.The advantage of the Mealy model is that it may lead to reduction of the number of states.

In both models the next state depends on current state and input. Some times designers use mixed models. States will be encoded for representing a particular state.

Representation of a FSM

A FSM can be represented in two forms:
  • Graph Notation
  • State Transition Table
Graph Notation
  • In this representation every state is a node. A node is represented using a circular shape and the state code is written within the circular shape.
  • The state transitions are represented by an edge with arrow head. The tail of the edge shows current state and arrow points to next state, depending on the input and current state. The state transition condition is written on the edge.
  • The initial/start state is sometime represented by a double lined circular shape, or a different colour shade.
The following image shows the way of graph notation of FSM. The codes 00 and 11 are the state codes. 00 is the value of initial/starting/reset state. The machine will start with 00 state. If the machine is reseted then the next state will be 00 state.


State Transition Table

The State Transition Table has the following columns:
  • Current State: Contains current state code
  • Input: Input values of the FSM
  • Next State: Contains the next state code
  • Output: Expected output values
An example of state transition table is shown below.


Mealy FSM

In Mealy machine the output depend on both current state and input.The advantage of the Mealy model is that it may lead to reduction of the number of states.


The block diagram of the Mealy FSM is shown above. The output function depends on input also. The current state function updates the current state register (number of bits depends on state encoding used).


The above FSM shows an example of a Mealy FSM, the text on the arrow lines show (condition)/(output). 'a' is the input and 'x' is the output.

Moore FSM

In Moore machine the output depends only on current state.The advantage of the Moore model is a simplification of the behavior.


The above figure shows the block diagram of a Moore FSM. The output function doesn't depend on input. The current state function updates the current state register.


The above FSM shows an example of a Moore FSM. 'a' is the input. Inside every circle the text is (State code)/(output). Here there is only one output, in state '11' the output is '1'.

In both the FSMs the reset signal will change the contents of current state register to initial/reset state.

State Encoding

In a FSM design each state is represented by a binary code, which are used to identify the state of the machine. These codes are the possible values of the state register. The process of assigning the binary codes to each state is known as state encoding.
The choice of encoding plays a key role in the FSM design. It influences the complexity, size, power consumption, speed of the design. If the encoding is such that the transitions of flip-flops (of state register) are minimized then the power will be saved. The timing of the machine are often affected by the choice of encoding.
The choice of encoding depends on the type of technology used like ASIC, FPGA, CPLD etc. and also the design specifications.

State encoding techniques

The following are the most common state encoding techniques used.
  • Binary encoding
  • One-hot encoding
  • Gray encoding
In the following explanation assume that there are N number of states in the FSM.

Binary encoding

The code of a state is simply a binary number. The number of bits is equal to log2(N) rounded to next natural number. Suppose N = 6, then the number of bits are 3, and the state codes are:
S0 - 000
S1 - 001
S2 - 010
S3 - 011
S4 - 100
S5 - 101

One-hot encoding
In one-hot encoding only one bit of the state vector is asserted for any given state. All other state bits are zero. Thus if there are N states then N state flip-flops are required. As only one bit remains logic high and rest are logic low, it is called as One-hot encoding. If N = 5, then the number of bits (flip-flops) required are 5, and the state codes are:
S0 - 00001
S1 - 00010
S2 - 00100
S3 - 01000
S4 - 10000

To know more about one-hot encoding click here.

Gray encoding
Gray encoding uses the Gray codes, also known as reflected binary codes, to represent states, where two successive codes differ in only one digit. This helps is reducing the number of transition of the flip-flops outputs. The number of bits is equal to log2(N) rounded to next natural number. If N = 4, then 2 flip-flops are required and the state codes are:
S0 - 00
S1 - 01
S2 - 11
S3 - 10

Designing a FSM is the most common and challenging task for every digital logic designer. One of the key factors for optimizing a FSM design is the choice of state coding, which influences the complexity of the logic functions, the hardware costs of the circuits, timing issues, power usage, etc. There are several options like binary encoding, gray encoding, one-hot encoding, etc. The choice of the designer depends on the factors like technology, design specifications, etc.

Comments

Popular posts from this blog

Digital Design Interview Questions - All in 1

1. How do you convert a XOR gate into a buffer and a inverter (Use only one XOR gate for each)?
Answer



2. Implement an 2-input AND gate using a 2x1 mux.
Answer



3. What is a multiplexer?
Answer

A multiplexer is a combinational circuit which selects one of many input signals and directs to the only output.

4. What is a ring counter?
Answer

A ring counter is a type of counter composed of a circular shift register. The output of the last shift register is fed to the input of the first register. For example, in a 4-register counter, with initial register values of 1100, the repeating pattern is: 1100, 0110, 0011, 1001, 1100, so on.

5. Compare and Contrast Synchronous and Asynchronous reset.
Answer

Synchronous reset logic will synthesize to smaller flip-flops, particularly if the reset is gated with the logic generating the d-input. But in such a case, the combinational logic gate count grows, so the overall gate count savings may not be that significant. The clock works as a filter for small reset gl…

Setup and Hold TIme

Every flip-flop has restrictive time regions around the active clock edge in which input should not change. We call them restrictive because any change in the input in this regions the output may be the expected one (*see below). It may be derived from either the old input, the new input, or even in between the two. Here we define, two very important terms in the digital clocking. Setup and Hold time.
The setup time is the interval before the clock where the data must be held stable.The hold time is the interval after the clock where the data must be held stable. Hold time can be negative, which means the data can change slightly before the clock edge and still be properly captured. Most of the current day flip-flops has zero or negative hold time.


In the above figure, the shaded region is the restricted region. The shaded region is divided into two parts by the dashed line. The left hand side part of shaded region is the setup time period and the right hand side part is the hold time…

Gate-Level Modeling

>> Introduction
>> Gate Primitives
>> Delays
>> Examples


Introduction

In Verilog HDL a module can be defined using various levels of abstraction. There are four levels of abstraction in verilog. They are:
Behavioral or algorithmic level: This is the highest level of abstraction. A module can be implemented in terms of the design algorithm. The designer no need to have any knowledge of hardware implementation.Data flow level: In this level the module is designed by specifying the data flow. Designer must how data flows between various registers of the design.Gate level: The module is implemented in terms of logic gates and interconnections between these gates. Designer should know the gate-level diagram of the design.Switch level: This is the lowest level of abstraction. The design is implemented using switches/transistors. Designer requires the knowledge of switch-level implementation details.
Gate-level modeling is virtually the lowest-level of abstraction, because t…