Part 4 - Finite State Machines

Posted on Jan 31, 2023
(Last updated: May 26, 2024)

In the last part we covered sequential circuits, in this part we’ll cover Finite State Machines.

FSMs are type of sequential circuits, there are two main type of FSMs, Moore and Mealy.

  • Moore FSMs
    • Outputs depends only on the state.
  • Mealy FSMs
    • Outputs depend on both state and primary inputs.

1-1 Detector

A 1-1 detector, generates an output, $z = 1$, whenever the input, $w$ is 1 twice in a row (clock cycles).

  • Moore
    • The output, $z$, be equal to 1 in the clock cycle that follows the detection of the second $w = 1$
  • Mealy
    • The output, $z$, be equal to 1 in the same clock cycle when the second, $w = 1$ is detected.

Since the state table for the Mealy type will be shorter, since we have fewer states. The end result will result in a simpler circuit. But remember that they do not have the same logical function!

Most of the tasks can be realized by Moore-type FSM, as well as by Mealy-type FSM, although these two type FSMs don’t have the exact same logic function

Compared to Moore-type FSMs, Mealy-type FSMs have the following features:

  • Fewer states;
  • Quicker response;
  • Usually, simpler circuit implementation;
  • But, sometimes longer critical path, all the way from input to output (v.s. Moore: from state registers to output)
      • one solution: registered outputs in Mealy

State Assignments

Some state assignments are better than others. The state assignment influences the complexity of the state machine.

The combinational logic required in the state machine design is dependent on the state assignment.

Types of state assignment

  • Binary encoding: $2^N$ states $\rightarrow N$ Flip-Flops
  • Gray-code encoding: $2^N$ states $\rightarrow N$ Flip-Flops
  • One-hot encoding: $N$ states $\rightarrow N$ Flip-Flops

State minimization

Two states $S_i$ and $S_j$ are said to be equivalent if and only if for every possible input sequence, the same output sequence will be produced regardless of whether $S_i$ or $S_j$ is the initial state.

Partition

A partition consists of one or more blocks, where each block comprises a subset of states that maybe equivalent, but the states in a given block are definitely not equivalent to the states in other blocks.

For example: $$ P_2 = (ABD)(CEFG) $$

Here, $(ABD)$ and $(CEFG)$ are “blocks”.