FSM design: Mealy and Moore

Why it exists

Counters have a fixed sequence of states. Most real controllers, however, must react to inputs: a vending machine, a traffic-light controller, a protocol decoder, the control unit of a processor. A finite state machine (FSM) is the general model: a set of states, an input, and rules that give the next state and the output. In hardware it is flip-flops (the state) plus combinational logic (the next-state and output functions), all on a clock. This is the last link between the memory elements of this subject and the machines of the theory of computation. GATE asks you to analyse a given circuit, to design a detector, to say whether a machine is Moore or Mealy, to reduce the number of states, and to compute the clock period.

Prerequisites

You need flip-flop excitation from flip-flop conversion, and minimisation from Karnaugh maps.

Precise definitions

Finite state machine (synchronous sequential circuit). State register of $n$ flip-flops (up to $2^n$ states), a next-state function $Q^+ = \delta(Q, X)$ of the present state $Q$ and input $X$, and an output function. All flip-flops share one clock, so the state changes only at clock edges.

Moore machine. The output depends only on the present state: $Z = \lambda(Q)$. In a diagram the output is written inside the state and the edges carry the input.

Mealy machine. The output depends on the present state and the present input: $Z = \lambda(Q, X)$. In a diagram each edge is labelled input/output.

State diagram and state table. The diagram draws states as circles and transitions as arrows. The state table lists, for every present state and input, the next state and output. They contain the same information.

Analysis procedure. From a circuit: (1) write the flip-flop input equations and the output equations; (2) use the characteristic equations of the flip-flops to get the next-state equations; (3) build the state table; (4) draw the diagram; (5) describe what the machine does.

Design procedure.

1. Understand the specification and draw a state diagram (decide Moore or Mealy).
2. Make the state table.
3. Reduce the number of states (merge equivalent states).
4. Choose a state assignment (binary codes for the states).
5. Choose the flip-flop type and use its excitation table to get the input equations; get the output equations; unused codes are don't cares.
6. Minimise, draw the circuit and check the unused states.

State reduction (equivalent states). Two states are equivalent if no input sequence can tell them apart: they have the same output (Moore) or the same outputs on each input (Mealy), and their next states are equivalent for every input. Reduction is by partition refinement: start with the states grouped by output, then split a group whenever two of its states go to different groups on some input, until nothing splits. The groups that remain are the states of the minimal machine. For $k$ states you need $\lceil \log_2 k \rceil$ flip-flops, so fewer states can save flip-flops.

State assignment. Any distinct binary codes work, but the codes affect the cost of the equations. Common choices are binary (fewest flip-flops), Gray-like (adjacent states differ in one bit) and one-hot (one flip-flop per state, simplest logic).

Clock period. In a single-clock design the signal launched by one flip-flop must reach the next one before the next edge:

$T_{clk} \ge t_{cq} + t_{logic} + t_{su} \;(+\; \text{skew}),\qquad f_{max} = 1/T_{clk},$

where $t_{cq}$ is the clock-to-output delay, $t_{logic}$ the delay of the slowest path of the next-state logic and $t_{su}$ the setup time. The hold condition says the fastest path must not be too fast: $t_{cq,min} + t_{logic,min} \ge t_{hold} + \text{skew}$. A hold violation cannot be repaired by slowing the clock.

How it works

Step through a Mealy detector for the pattern 101 (overlapping occurrences allowed). The output edge is labelled input/output; the output is 1 on the transition that completes the pattern.

The Moore machine needs one more state, because the output belongs to the state: the state D means "101 has just been seen".

The time difference between them is the main practical point: with the same input the Mealy output appears in the cycle in which the last bit is applied, while the Moore output appears one clock edge later.

A machine that is not a detector: read a binary number most significant bit first and say whether it is divisible by 3. The state is the remainder, and reading a bit $b$ turns the value $v$ into $2v + b$, so the new remainder is $(2r + b) \bmod 3$.

Worked examples

#include <stdio.h>
#include <string.h>
 
/* Mealy detector for 101 (overlap), states S0=0 S1=1 S2=2: returns output, updates state */
static int mealy_step(int *s, int x) {
    int z = (*s == 2 && x == 1);
    static const int next[3][2] = { { 0, 1 }, { 2, 1 }, { 0, 1 } };
    *s = next[*s][x];
    return z;
}
 
/* the same machine as a circuit: state bits P Q, D1 = X'Q, D0 = X, Z = X P */
static int mealy_circuit(int *p, int *q, int x) {
    int z = x && *p;
    int d1 = !x && *q, d0 = x;
    *p = d1;
    *q = d0;
    return z;
}
 
/* Moore detector: A=0 B=1 C=2 D=3, output 1 only in D */
static int moore_step(int *s, int x) {
    static const int next[4][2] = { { 0, 1 }, { 2, 1 }, { 0, 3 }, { 2, 1 } };
    *s = next[*s][x];
    return *s == 3;
}
 
/* divisible by 3: state = remainder */
static int div3_step(int *r, int x) {
    *r = (2 * *r + x) % 3;
    return *r == 0;
}
 
int main(void) {
    const char *in = "10101101";
    int s = 0, p = 0, q = 0, m = 0;
    char a[16], b[16], c[16];
    for (size_t i = 0; i < strlen(in); i++) {
        int x = in[i] - '0';
        a[i] = (char)('0' + mealy_step(&s, x));
        b[i] = (char)('0' + mealy_circuit(&p, &q, x));
        c[i] = (char)('0' + moore_step(&m, x));
    }
    a[strlen(in)] = b[strlen(in)] = c[strlen(in)] = 0;
    printf("input        %s\nMealy table  %s\nMealy gates  %s\nMoore        %s\n", in, a, b, c);
    int bad = 0, strings = 0;
    for (int len = 1; len <= 10; len++)
        for (int v = 0; v < (1 << len); v++) {
            int s1 = 0, p1 = 0, q1 = 0, m1 = 0, r = 0;
            int last3 = 0;
            for (int i = len - 1; i >= 0; i--) {
                int x = (v >> i) & 1;
                int z1 = mealy_step(&s1, x), z2 = mealy_circuit(&p1, &q1, x), z3 = moore_step(&m1, x);
                last3 = ((last3 << 1) | x) & 7;
                int seen = (len - i >= 3) && last3 == 5;
                bad += z1 != seen || z2 != seen || z3 != seen;
                div3_step(&r, x);
            }
            bad += r != v % 3;
            strings++;
        }
    printf("machines wrong on %d of %d strings\n", bad, strings);
    int r = 0;
    printf("divisible by 3 on 1100101:");
    int val = 0;
    for (const char *t = "1100101"; *t; t++) {
        val = 2 * val + (*t - '0');
        printf(" %d%s", val, div3_step(&r, *t - '0') ? "*" : "");
    }
    printf("\n");
    double tcq = 2, tlogic = 5, tsu = 1;
    printf("clock period at least %.0f ns, frequency at most %.0f MHz\n", tcq + tlogic + tsu, 1000 / (tcq + tlogic + tsu));
    return 0;
}

input        10101101
Mealy table  00101001
Mealy gates  00101001
Moore        00101001
machines wrong on 0 of 2046 strings
divisible by 3 on 1100101: 1 3* 6* 12* 25 50 101
clock period at least 8 ns, frequency at most 125 MHz

Cheat box

Traps and GATE patterns

Connections

A counter is a state machine without inputs, and a shift register with a combinational function is a feedback machine. The memory elements are the flip-flops, and the next-state logic is designed with the excitation tables of the previous page. In Theory of Computation the same object appears as a DFA, with a Moore machine as a DFA with outputs, and the control unit of the processor is an FSM that steps through the instruction cycle.

PYQs

Consider a 2-bit saturating up/down counter that
performs the saturating up count when the input P
is 0, and the saturating down count when P is 1. The
Next State table of the counter is as shown. The
counter is built as a synchronous sequential circuit
using D flip-flops.

Input
Current
State
Next
State
P
Q1
Q1
+
Q0
+
0
0
0
0
1
0
0
1
1
0
0
1
0
1
1
0
1
1
1
1
1
0
0
0
0
1
0
1
0
0
1
1
0
0
1
1
1
1
1
0

We want to design a synchronous counter that
counts the sequence 0-1-0-2-0-3 and then repeats.
The minimum number of J-K flip-flops required to
implement this counter is __________.

Consider the following circuit

The flip-flops are positive edge triggered s. Each
state is designated as a two-bit string . Let the initial
state be The state transition sequence is

Self-check

Revision card

References