Finite State Machines with Output (Mealy and Moore Machines)

Introduction

If a combinational logic circuit is an implementation of a Boolean function, then a sequential logic circuit can be considered an implementation of a finite state machine. There is a little more to it than that (because a sequential logic circuit can contain combinational logic circuits).

If you take a course in programming languages, you will also learn about finite state machines. Usually, you will call it a DFA (deterministic finite automata).

While finite state machines with outputs are essentially DFAs, the purpose behind them is different.

DFAs in programming languages

When you are learning about models of computation, one simple model is a deterministic finite automata or DFA for short.

Formally, the definition of a DFA is:

DFAs are used to recognize a language, L. A language is a set of strings made from characters in the input alphabet. If a language can be recognized by a DFA, it is said to have a regular grammar.

To use a DFA, you start in an initial state, and process the input string a character at a time. For example, if the input alphabet consists of "a" and "b", then a typical question is to ask whether the string "aaab" is accepted by a DFA.

To find out whether it is accepted, you start off in the state state, S. Then you process each character (first "a", then "a", then "a", and finally "b"). This may cause you to move from one state to another. After the last character is processed, if you are in a final state, then the string is in the language. Otherwise, it's not in the language.

There are some languages that can't be recognized by a DFA (for example, palindromes). Thus, a DFA, while reasonably powerful, there are other (mathematical) machines that are more powerful.

Often, tokens in programming languages can be described using a regular grammar.

FSM with output in hardware

A finite state machine with output is similar to describe formally.

The primary difference is that there is no set of final states, and that the transition function not only puts you in a new state, but also generates an output symbol.

The goal of this kind of FSM is not accepting or rejecting strings, but generating a set of outputs given a set of inputs. Recall that a black box takes in inputs, processes, and generates outputs. FSMs are one way of describing how the inputs are being processed, based on the inputs and state, to generate outputs. Thus, we're very interested in what output is generated.

In DFAs, we don't care what output is generated. We care only whether a string has been accepted by the DFA or not.

Since we're talking about circuits, the input alphabet is going to be the set of k bit bitstrings, while the output alphabet is the set of m bit bitstrings.

We'll look at this more informally, just in case you're confused.

An Example

Let's look at an example of an FSM.

Each of the circle is a state. For now, all you need to know is that, at any given moment, you are in one state. Think of this as a game, where there are circles drawn on the ground, and at any moment, you are standing in exactly one circle.

Each of the circle is given a unique binary number. The number of bits used depends on the total number of states. If there are N states, then you need ceil( lg N ) bits (the ceiling of log base 2 of N). The states are labelled with the letter q, plus subscripts. In this example, it's q1q0.

You may have k input bits. The input bits tell you which state to transition to. For example, if you have 2 input bits (x1x0), then there are four possible out going edges (x1x0 = 00, x1x0 = 01, x1x0 = 10, and x1x0 = 11). In general, there are 2k outgoing edges for k bits of input.

Thus, the number of edges depends on the number of bits used in the input.

Tracing an Example

You might be asked, what are the sequence of states and outputs, assuming you start in state 00, and have input (1, 1, 0, 0, 1).

State 00 (Start) 01 10 01 01 10
Input 1 1 0 0 1  

So, you may start in state 00, reading input 1 (see column 1 of the table), which puts you in state 01. At that point, you read in input 1 (see column 2), and go into state 10 (column 3), etc.

FSM with Outputs: Moore machines

The goal of FSMs is to describe a circuit with inputs and outputs. So far, we have inputs, that tell us which state we should go to, given some initial, start state. However, the machine generates no outputs.

We modify the FSM shown above, by adding outputs. Moore machines add outputs to each state. Thus, each state is associated with an output. When you transition into the state, the output corresponding to the state is produced. The information in the state is typically written as 01/1. 01 indicates the state, while 1 indicates the output. 01/1 is short hand for q1q0 = 01/z = 1

The number of bits in the output is arbitary, and depends on whatever your application needs. Thus, the number of bits may be less than, equal, or greater than the number of bits used to represent the state.

Let's look at an example of a Moore machine.

In this example, you see two bits for the state and two bits for the output. Thus, when you see 00/01 inside one of the circles, it is shorthand for q1q0 = 00 / z1 z0 = 01.

Tracing using Timing Diagrams

Given the Moore machine in the previous diagram, and the timing diagram below, you might be asked to determine the state and output.

The timing diagram isn't too hard to follow. Basically, you will start off in some state (let's say, 00), and draw the diagram to indicate what happens to the state (q1q0) and to the output (z1z0).

You'll notice the input does NOT change at the positive edge. That way, it's easier for you to tell the value of the input at the positive edge. To make it easier to read, I've added the value of x at the positive edge. Thus, the inputs are 1, 1, 0, 1, 1, 0.

Let's look at the timing diagram at the first positive edge (drawn with a vertical line). Before the first edge, the state, q1q0 = 00. The input is 1. This should put us in state 01 (i.e., q1q0 = 00), which outputs 11 (i.e., z1z0 = 11).

You have to read down the columns. The first column says that the machine is in state 00, with output 01. The second column says that the machine is in state 01, with output 11. The reason the second column says that is due to the input, x, read in at the first positive edge. The input x is 1, which caused the FSM to move from state 00 to state 01.

The value of the state and output are placed in the middle, but the really, it's the dark line that tells you when this happens. The state and output changes value on the positive edge (technically, it takes a small, but finite amount of time after the positive edge for the state and output to finally settle down, but we'll draw the diagrams as if it happens instantaneously---even though it doesn't).

Here's the rest of the timing diagram.

FSM with Outputs: Mealy machines

A Moore machine has outputs that are a function of state. That is, z = f( qk-1,..., q0 ).

A Mealy machine has outputs that are a function of state and input, that is That is, z = f( qk-1,..., q0, xm-1,..., x0 ).

We usually indicate that the output is depedent on current state and input by drawing the output on the edge. In the example below, look at the edge from state 00 to state 01. This edge has the value 1/1. This means, that if you are in state 00, and you see an input of 1, then you output a 1, and transition to state 01.

Thus, 1/1 is short hand for x = 1 / z = 1.

Here's a sample Mealy machine.

One thing you will notice is the numbering of the states. Usually, if there are 3 states, we number them 00, 01, and 10, since those are the first 3 UB numbers. However, given that we're using two bits, we can, in principle, pick any 3 of the 4 possible 2-bit numbers.

One reason we might want to pick something else besides 00, 01, and 10 is because implementing an FSM with minimal gates often involves picking the correct state numbering. Thus, if you're careful which state is numbered, say, 00, 01, and 11, you may be able to create a circuit that has fewer gates.

However, minimization of the circuit based on well-chosen state numberings is outside the scope of the course. We only pick the state numberings just to make a note that this could happen, but we won't take advantage of this fact.

Another interesting point to observe is how a Mealy machine differs from a Moore. Already we said that a Mealy machine's output may depend on both the values of state and input variables. We can see this in the example. Look at the edge from 00 to 01.

This edge says that if a 1 is input, we will transition to state 01 and output a 1. Now look at the loop in state 01. This says that if the input is 1, we will loop back to state 01, and output a 0.

So, in the first case, going to state 01 outputs a 1, whereas in the second case, going to state 01 outputs a 0. In a Moore machine, this would not happen. The output depends only on the state you transition into, not how you got into that state.

Tracing using Timing Diagrams

To see how the previous Mealy machine behaves, we can use timing diagrams. We'll use the same input as before.

The following timing diagram shows what happens to the state (q1q0) and to the output (z).

Just to see what happens. Initially, we're in state 00, with an output of 0. It doesn't terribly matter what the initial output is. Unlike the Moore machine, a Mealy machine's output doesn't depend on the current state.

In state 00, we see an input of a 1. This takes us to state 01, with an output of 1. If you read the second column of numbers, you see 0 and a 1 (which is state 01), followed by a 1 (which is the output).

Equivalence of Mealy and Moore machines

We have two ways to describe a FSM: Mealy and Moore machines. A mathematician might ask: are the two machines equivalent?

Initially, you might think not. A Mealy machine can have its output depend on both input and state. Thus, if we ignore the state, we should be able to convert a Moore machine to a Mealy machine.

It's not so easy to see that you can convert an arbitrary Mealy machine to a Moore machine.

It turns out that the two machines are equivalent. What does that mean? It means that given a Moore machine, you can create a Mealy machine, such that if both machines are fed the same sequence of inputs, they will both produce the same sequence of outputs. You can also convert from a Mealy machine to its equivalent Moore machine, and again generate the same outputs given the same sequence of inputs.

Actually, to be precise we must ignore one fact about Moore machines. Moore machines generate output even if no input has been read in. So, if you ignore this initial output of the Moore machine, you can convert between one machine and the other.

The actual algorithm is beyond the scope of the course. However, the basic idea of converting a Mealy machine to a Moore machine is to increase the number of states. Roughly speaking, if you have a Mealy machine with N states, and there are k bits of input, you may need up to 2kN states in the equivalent Moore machine.

Effectively, the new states record information about how that state was reached.

Summary

Finite state machines are one way of describing the behavior of a circuit with state. Think of it as a very crude programming language, which takes inputs, and uses those inputs and the state to compute outputs, and also to determine what state to transition into.

CPUs use finite state machines as control units to sychronize the fetch, execute, decode cycle. These machines can be rather sophisticated, however, programs exists to convert the finite state machine into actual flip flops and logic gates.