Part 4 - Finite State Machines

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

FSMs are a type of sequential circuit, there are two main types of FSMs, Moore and Mealy.

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$, should be equal to 1 in the clock cycle that follows the detection of the second $w = 1$
• Mealy
  • The output, $z$, should 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 types of 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

Partition

For example:

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