Saturday 7 February 2015

State machines – a practical perspective


Hi friends, until now, we have learned how to write the RTL. We have also learned that RTL is the building block of digital system design. A well-written verilog code represents the complete system. We can also say that the verilog code represents the state machine of the system. But what is a state machine? As per the definition, a state machine consists of a set of states, a start state, an input and a transfer function that maps inputs and current state to next state. State machine designing is the heart of digital system design. All digital systems are state machines. We have learned how to write the RTL with the example of a clock as a system. In this post, we will discuss the state machines from a different perspective and try to build out understanding by representing our own clock as a state machine.

As we just discussed, each digital system is a state machine. It has an initial state, gets some inputs, moves to other states and provides some outputs. For example, consider a processor. Initially, it is in reset state. When reset is asserted, it comes out of reset state into stop/run state as described by a set of inputs defining mode of operation. It also fetches instructions from cache/RAM. This state can be termed as instruction fetching state. It goes into interrupted state upon receiving a request from a peripheral. In all these states, the processor also produces some outputs representing its states.


What corresponds a state in a digital design?  Each design is composed of a set of registers whose value is updated on every clock edge. Each edge corresponds to a state. The inputs/outpus and logic gates between registers ensure that the design state is updated every time a clock edge is encountered. All the registers have setup and hold checks that have to be met in order to ensure that the data is transferred appropriately between registers and right data is captured at every clock edge. Figure 1 below shows the state map for a design consisting of all positive edge-triggered registers. As is obvious, all the registers values are updated at each positive clock edge, hence, we say that the state machine updated its state at each positive clock edge.  In other words, we can say that at each clock edge, the state machine makes decisions based upon its inputs and present state and moves to next state.

In a digital design, each clock edge brings a change in state of state machine.
Figure 1: Each clock edge corresponds to a state.

Digital clock as a state machine: We just discussed a simple example of a processor as a state machine. Now, let us discuss our own clock as a state machine. Repeating here the definition of a state machine, a state machine consists of a set of states, a start state, an input and a transfer function that maps inputs and current state to next state. Figure 1 below shows the block diagram of our digital clock. As is shown, it consists of

i)                    An up counter
ii)                   Different sets of registers (hour registers, minute registers and seconds registers)
iii)                 A group of adders and
iv)                 A control FSM.

Let us explore different aspects of our digital clock state machine.

State: A particular configuration of the different registers and control FSM represents a state of our state machine. The different states may be:

i)                    RESET state
ii)                   RUNNING state
iii)                 STOP state

Start State: The start state of our machine is either 00:00:00 (when the clock goes into RESET state) or REF_TIME (when REF_TIME input is provided).

Inputs: The inputs to our digital clock state machine are:
i)                    RESET and other control signals
ii)                   REF_TIME

Transfer function: The transfer function here is the condition that updates the state of our state machine. In other words, if RESET is asserted, output goes to zero, otherwise it increments by 1 second.

Outputs: The output here is the time that is displayed on the screen of the digital clock.

A digital clock might be thought to be composed of a set of registers and some counters, adders and a control logic.
Figure 2: Digital clock block digram


Now, let us proceed towards getting the state diagram for our digital clock state machine, which is as shown below in figure 2. We can consider it as a state machine consisting of three states.
  1. RESET state: When RESET input is asserted, the time goes to 00:00:00. As long as RESET input remains asserted, the state machine remains into RESET state.
  2. RUN state: This is the normal state of our digital clock state machine. The output is the current time; i.e. current state of registers.
  3. REF_IN state: When REF_IN input changes, the clock state machine output changes and becomes equal to REF_IN input applied. And the very next cycle, it returns to RUN state.


The state machine for digital clock consists of reset state, current state and an initial state.
Figure 3: State machine corresponding to digital clock


Thus, in this post, we have discussed about how a state machine should be looked upon from a practical perspective and illustrated the same by considering a digital clock as a state machine. Stay tuned and learn with fun.