Implementing Mealy and Moore Machines

Introduction

• A Mealy machine has outputs that depend on the state and input (thus, the FSM has the output written on edges)
• A Moore machine has outputs that depend on state only (thus, the FSM has the output written in the state itself)

Never fear though. Even though it may be difficult to learn how to implement Mealy and Moore machines, most people will tell you that it's a very mechanical process. That is, once you learn it, it's like following a cookbook recipe.

Of course, you might ask why you should learn how to implement Mealy and Moore machines, but we'll defer that to the next set of notes.

The Big Picture

and eventually create a black box circuit that looks like:

Recall that a sequential circuit stores state information. If we have k states, that state information requires ceil( lg( k ) ) flip flops. Since each flip flop stores one bit, then the state stores ceil( lg( k ) ) bits of information.

In fact, that information is the state label. For example, in the FSM diagram above, there's two bits used in the state, thus you have q₁q₀ = 00 to mean that some state label is 00.

The Steps

1. Create a state transition table

   This is basically a truth table that records the information of the finite state machine.

2. Decide how many flip flops you need, and what kind

   This is usually simple, because you have to encode each state of the finite state machine using ceil( lg( k ) ) bits. Or even better, someone's already given you an FSM with that information encoded.

   Choosing the kind of flip flop you want is usually an academic exercise. You'll often be told to use a certain flip flop, so you need to be able to handle the kind give.

3. Use the flip flop excitation table, to fill out the rest of the chart.

   We'll talk about the excitation table momentarily.

4. Implement the circuit using a ROM.

   Look at the diagram of the black box in the previous section. See the box inside the black box labelled combinational logic? We're using a ROM (read-only memory) to implement the combinational logic.

   Technically, a ROM is not combinational logic. It's memory, thus, it basically has flip flops in it. However, you could use gates to implement the equivalent behavior of a ROM, using sum-of-products representation.

It's like someone told you to fold a piece of paper this way, then that way, and eventually when you're done, they say congratulations, you've made a "glurble". You're happy and proud of this paper concoction you've created! "A glurble!", you exclaim.

Then you realize you have absolutely no idea what you've made. You know the steps, but you don't know why it matters.

For now, the quickest way to learn this is to follow the steps, understand how they work, and then try to get the big picture a little later.

Step 1: Create a State Transition Table

We'll implement the Moore machine shown above. The Moore machine has two bits for the state and one bit for the input.

Since the input and state variables are the truth table inputs, we list out all possibilities. There are 1 input variable plus 2 state variables = 3 truth table inputs, thus 2³ rows in the truth table.

Some Intuition: Inspecting a Row

It means we're current in state q₁q₀ = 00 and we see an input of x = 0 (at a positive edge).

Putting State Variables First

The reason for doing it in this order (as opposed to putting input variable, then state variables) is to handle every possible input per state, before moving onto the next state.

Next Small Step: Writing the Next State

For example, look at the Moore maching above. In state 00, if we see an input of a 0, then we go to state 10. In state 00, if we see an input of a 1, then we go to state 01. Let's put that information in the "truth table output" section (shown in green).

Now let's go to state 01. In state 01, if the input is 0, you stay in state 01. If it's 1, you go to state 10.

Now we go to state 10. In state 10, if we see a 0, we head to state 01. If we see a 1, we go to state 00. We fill that in.

Finally, there is no state 11. So, in that case, we don't care what happens if we are in that state. We can fill whatever we want. However, to emphasize that we don't care, we fill in the next state with d's, which indicate "don't care".

Next Small Step: Filling the Outputs

All we need to now is fill out the outputs.

Since this is a Moore machine, here are the rules for filling out the outputs. For each state, look at the output. Thus, state 00 has output z₁z₀ = 01.

State 00 is in row 0 and row 1, where q₁q₀ = 00.

State 01 has output 11. State 01 is in rows 2 and 3.

State 10 has output 11. State 01 is in rows 4 and 5.

State 11 doesn't exist, so we put "d" in rows 6 and 7 for the output columsn (in blue).

Step 2: Picking flip flops

However, in a test situation, you'll be told which flip flops to use.

We need a flip flop for each bit used in a state. There are two bits, q₁q₀, so two flip flops are needed.

Let's implement q₁ with a D flip flop, and q₀ with a T flip flop. We'll label them D₁ (to match up with q₁) and T₀ (to match up with q₀).

Step 3: Use flip flop excitation table to fill out the rest of the table.

We add two more columns to the table, D₁ and T₀.

We now look at column q₁ and q₁⁺. They've been highlighted.

These columns refer to flip flop D₁. Basically, look at each row. For example, in row 0, you see q₁ = 0 and q₁⁺ = 1. Thus, you need to make D = 1 (based on the excitation table).

In row 1, you see q₁ = 0 and q₁⁺ = 0. Thus, you need to make D = 0 (based on the excitation table).

But recall that the D excitation table basically said D = Q⁺. So, all we have to do is to copy the q₁⁺ columns over to D₁.

Now we focus on columns q₀ and q₀⁺.

Now look at row 0. We have q₀ = 0 and q₀⁺ = 0. The T flip flop excitation says that T must hold (i.e., T = 0) for that to happen.

Now look at row 1. We have q₀ = 0 and q₀⁺ = 1. The T flip flop excitation says that T must toggle (i.e., T = 1) for that to happen.

In fact, for each row, all you do is ask, are the values in the two columns the same? If so, set T = 0. If not, set T = 1.

So, we fill out the rest of the column accordingly.

Step 4: Implement the Circuit Using a ROM

Thus, if we have a 3-bit ROM, then the addresses are 3 bits each. If the input is 000_two, then we get the contents of ROM at memory address M[000].

To implement the circuit, we're going to have as many address bits in the ROM as we do truth table inputs. The number of truth table inputs is the sum of the number of state variables and the input variables. This is also the number of rows in our table, which is 8.

The number of bits at each memory address is the sum of the output variables, plus the number of flip flops. So, that's 2 output variables (z₁z₀) and 2 flip flops (D₁T₀). Thus, at each address, there's 4 bits.

This is really the easy part of the circuit design. We will merely copy all columns in blue to the ROM. And we're done.

Here's the final diagram.

A few comments about the diagram above, in particular, the ROM.

• Label the address bits A₂A₁A₀. Don't leave them out.
• Make sure you hook up the wires to the address bits correctly. Order matters! q₁ hooks up to A₂. q₀ hooks up to A₁. x hooks up to A₀. They are in that order, because the truth table inputs are listed in that order.
• Label addresses 000 through 111. Don't leave it blank!
• Label the columns correctly: z₁, z₀, D₀, T₀.
• Don't add additional bits to the ROM. In particular, don't add the next state.
• Feedback D₁ and T₀ from the ROM output to the flip flop inputs.
• Leave the don't cares as they are. Notice that we copy the d's, instead of giving them values. You should do the same.
• Circle the input, x, so I know it's coming from outside the black box.
• Square the outputs, z₁z₀, so I know it's going outside the black box.
• Add the steenkin' clock!

Does it work?

In particular, z₁z₀ = 01 which is the output you get in state 00. D₁ = 1 causes q₁ to be 1 at the next positive edge. T₁ = 0 causes q₀ to stay at 0 at the next positive edge.

Thus, at the next positive edge, q₁q₀ = 10, which is the state we expect. If we're now in q₁q₀ = 00, on an input of 1, then we expect to be in state q₁q₀ = 10, at the next positive edge.

When the next positive edge occurs, and we're in state 01, then if x is still 0, then the address bits are AA₁A₀ = 100, which selects address 100.

This selects the 4 bit value at adress 100: z₁z₀D₁T₀ = 1101.

Thus, the output is now 11, which is the output you expect for state 10.

Try another state and another input to convince yourself this circuit works.

Practice make perfect

Mealy Machines

Recall from the Moore machine, you look at the current state, and then check what the output is from the FSM, and then copy the output bits for each occurrence of that state.

Here's an example of a Mealy machine. Notice the outputs are on the edges.

Here's the table. We've filled in the don't cares for rows 4 and 5, which correspond to state 10, which doesn't exist.

Now, suppose you are in state 00, and see an input of a 0 (i.e., q₁q₀ = 00 and x = 0). At the next positive edge, you will go transition to state 11, and output a 1 (i.e., q₁q₀ = 11 and z = 1).

Suppose you are in state 00, and see an input of a 1 (i.e., q₁q₀ = 00 and x = 1). At the next positive edge, you will transition to state 01, and output a 1 (i.e., q₁q₀ = 01 and z = 1).

We can fill that information out in the table.

As an exercise, you can fill out the rest of the chart yourself.

After that, the same steps are followed. Pick the flip flops, use the flip flop excitation table, and draw the circuit.

Being Careful with Moore machines

Do we Need a ROM?

The ROM is convenient so we can design this part in a hurry, but in principle, all it takes is writing a sum of products expression for each of the columns.

The purpose of the ROM (or the circuit that would go in the place of the ROM) is to generate the correct control signals to the flip flops (using feedback) to get to the next state at the next positive clock edge, as well as to generate the output of the circuit.

Summary

However, it does take practice to be able to do it reasonably fast, and is difficult to understand conceptually, at least, at first. You should trace out a few steps just to convince yourself of how it behaves. There is a subtle difference in the behavior of the implementation of a Mealy and Moore machine. Tracing out a few steps can show the differences more clearly.

Usually, it's harder to understand why the circuit does the right thing (i.e., implements the FSM) than it is to know how to build it. Certainly, you should devote time to both understanding why this technique works, as well as mastering the technique.

Web Accessibility