1. Home
2. Academy
3. State Machines from Zero
4. Volume 02

2.1 Moore: output depends only on the state

In a Moore machine, the outputs depend only on the current state. Each state has its own fixed outputs.

One job, two designs

All through this volume we will build the same small circuit. It watches a button, and gives a pulse - a 1 for exactly one clock cycle - each time the button goes from not pressed (0) to pressed (1). It must not keep pulsing while the button is held down. A circuit like this is called a rising-edge detector. You will find one in almost every design that reads a button or a flag.

The input is btn. The output is pulse.

The Moore way

The turnstile and the traffic light in Volume 01 had something in common. Their outputs came from the state alone. LOCKED meant locked = 1. GREEN meant the green lamp was on. A machine built this way is called a Moore machine, after Edward F. Moore, who described it in 1956.

Now think about what the edge detector must remember. It needs to tell apart three situations:

1. ZERO - the button is up. Output 0.
2. EDGE - the button has just gone down, one cycle ago. Output 1. This state exists only to make the pulse.
3. ONE - the button has been held for more than one cycle. Output 0, so there is no second pulse.

Because the output belongs to the state, a Moore diagram writes it inside the circle, under the state's name. Figure 2.1 shows the edge detector as a Moore machine.

Follow a press through the diagram. The machine sits in ZERO. The button goes down, so btn = 1, and at the next edge the machine moves to EDGE - pulse is now 1. The button is still down, so at the next edge the machine moves to ONE - pulse drops to 0. It stays in ONE until the button comes up, then returns to ZERO.

The Moore state table

In a Moore table, the output column depends only on the current state, so it is the same in every row for that state:

2.2 Mealy: output depends on state and input

In a Mealy machine, the outputs depend on the current state and on the current inputs. So the output is written on the arrow, next to the input that causes it.

A second way to make outputs

In 1955, George H. Mealy described another kind of state machine. In a Mealy machine, the output logic looks at the inputs as well as the state. The same state can then give different outputs for different inputs.

That changes what the edge detector needs to remember. It only has to know one thing: was the button down last cycle, or not? Two states are enough:

• ZERO - the button was up last cycle.
• ONE - the button was down last cycle.

The pulse comes from a simple rule: if the machine is in ZERO and btn is 1, then pulse is 1. "In ZERO" means the button was up; "btn is 1" means it is down now. Together, that is exactly a rising edge.

Outputs on the arrows

A Mealy output depends on the state and the input together - which is exactly what an arrow stands for. So a Mealy diagram labels each arrow as input / output. The label 1 / 1 means: "if btn is 1, go this way, and make pulse 1 while you do".

The Mealy table has an output column that can differ from row to row within one state:

In ZERO, pulse is 0 in one row and 1 in the other. That could never happen in a Moore table.

What changes in the hardware

Figure 2.3 puts the two kinds side by side. They are identical except for one wire.

That one extra wire gives a Mealy machine two strengths and two weaknesses:

The last row matters most. A path that goes only through gates, with no flip-flop on the way, is called a combinational path. In a Mealy machine, a change on an input races straight through to the output within the same cycle.

2.3 Seeing the difference on a waveform

On a timing diagram, a Mealy output reacts in the same clock cycle as its input. A Moore output reacts one cycle later.

Figure 2.4 runs both edge detectors on the same button press. The top half is the Moore machine from Figure 2.1. The bottom half is the Mealy machine from Figure 2.2.

Walk through it:

1. Just after edge 2, btn rises. The Mealy machine is in ZERO and now sees btn = 1, so its gates make mealy_pulse = 1 at once, in the same cycle.
2. At edge 3, both machines see btn = 1. The Mealy machine moves to ONE, so mealy_pulse drops back to 0. The Moore machine moves to EDGE, so moore_pulse rises now.
3. At edge 4, the Moore machine moves on to ONE, and moore_pulse drops back to 0.
4. At edge 6, btn has been released. Both machines return to ZERO, ready for the next press.

Both pulses are exactly one cycle long. The only difference is when they happen: the Mealy pulse comes one cycle earlier. The number of cycles a circuit takes to respond is called its latency. Here the Mealy detector has a latency of zero cycles, and the Moore detector has a latency of one.

The price of speed: glitches

Now suppose the button signal flickers for a moment, in the middle of a cycle. Perhaps a wire picked up some noise. Figure 2.5 shows what each machine does.

The flicker never lasts until a clock edge, so neither machine changes state. The Moore output comes only from the state, so it stays at 0. But the Mealy output is pulse = (state is ZERO) AND btn. The machine is in ZERO, so pulse simply copies btn - flicker and all. That short, unwanted pulse is a glitch. If pulse drives another circuit that reacts at once - a counter with its own clock, say - the glitch can do real damage.

2.4 Converting Mealy to Moore and back

Any Mealy machine can be rebuilt as a Moore machine that gives the same outputs one cycle later, and any Moore machine can be rebuilt as a Mealy machine.

You do not have to choose the type before you start. You can design in whichever form feels natural, then convert. The conversion is a fixed recipe, and it explains exactly why the two types differ.

Mealy to Moore: split the states

In a Moore machine every state has one fixed output. So look at each Mealy state, and at the outputs on the arrows that enter it. If they all carry the same output, the state can keep it. If they carry different outputs, the state must be split into copies - one per output value.

1. List each state, and the output value on every arrow that enters it.
2. If all those outputs are equal, keep the state and give it that output.
3. If they differ, make one copy of the state for each output value.
4. Each old arrow now points to the copy whose output matches the arrow's output.
5. Give every copy the same outgoing arrows as the original state had.

Let us convert the Mealy edge detector from Figure 2.2:

ONE splits into a copy with output 1 and a copy with output 0. Call the first copy EDGE and keep the name ONE for the second. The arrow ZERO --1 / 1--> ONE now goes to EDGE, and the loop ONE --1 / 0--> ONE goes to the copy named ONE. Both copies keep ONE's outgoing arrows: on btn = 1 go to ONE, and on btn = 0 go to ZERO.

The result has three states - ZERO, EDGE and ONE - with exactly the arrows of Figure 2.1. The recipe has rebuilt, step by step, the Moore machine we designed by hand.

Moore to Mealy: move each output onto the arrows

Going the other way is simpler. Keep all the states. Then, on every arrow, write the output of the state the arrow points to. Here is the Moore edge detector from Figure 2.1, converted:

Now look at EDGE and ONE. On btn = 0 both go to ZERO with output 0. On btn = 1 both go to ONE with output 0. They behave exactly alike, so they can be merged into one state. Merge them, and you get the two-state Mealy machine of Figure 2.2. Finding states that behave alike, and merging them, is called state minimisation - it has a whole volume of its own, Volume 10.

2.5 Medvedev, and choosing the right type

A Medvedev machine is a Moore machine whose outputs are the state bits themselves, with no output logic at all.

Outputs with no logic

A Moore machine still needs output logic: gates that turn the state bits into outputs. Sometimes you can remove even those gates. If you choose the state's bit patterns cleverly, the state is the output. A machine like this is called a Medvedev machine.

Take the traffic light from Volume 01. It has three states and three lamps. Give it a state register of three flip-flops, one per lamp, and choose these bit patterns:

Now wire each flip-flop straight to its lamp, as in Figure 2.6. There is nothing left to decode.

A Medvedev machine has the cleanest possible outputs. They change exactly at the clock edge, together, and they can never glitch - there are no gates in between to cause one. The price is that the outputs choose your state encoding for you, and that may cost extra flip-flops. Three flip-flops for three states is more than the two a counting code would need.

Choosing the right type

Some simple rules to start with:

• Start with Moore. It is predictable, it is easy to test, and its outputs are steady between clock edges.
• Use Mealy when you need the answer in the same cycle, such as a "ready" reply that another block is waiting for. Do this only when the inputs are clean, clocked signals.
• Use Medvedev, or a registered output, when a glitch would cause harm - for example, an output that leaves the chip, or one that another clock domain will read.

What you learned

• A Moore machine's outputs depend only on the state. Its diagram writes outputs inside the states.
• A Mealy machine's outputs depend on the state and the inputs. Its diagram writes input / output on the arrows.
• A Mealy output reacts in the same cycle as its input, one cycle before a Moore output - but it can pass on glitches.
• Mealy to Moore: split each state by the outputs on its entering arrows. Moore to Mealy: write each destination's output on the arrow.
• A Medvedev machine uses the state bits as the outputs, so it needs no output logic and never glitches.
• Start with Moore; use Mealy for same-cycle replies; use Medvedev or registered outputs where glitches would harm.

Key words from this volume

Every word below has a plain-English entry in the glossary.

• Pulse
• Edge detector
• Moore machine
• Mealy machine
• Combinational path
• Latency
• Glitch
• Registered output
• Medvedev machine

Practice

Interview corner

reg btn_prev;                        // the state: btn one cycle ago
always @(posedge clk)
  btn_prev <= btn;                   // remember this cycle's value
assign pulse = btn & ~btn_prev;      // 1 only when btn is 1 now and was 0 before

Next, Volume 03 takes a state machine all the way down to gates and flip-flops, by hand - the skill behind every state machine question in a written exam.