Finite State Machines (FSM): Moore and Mealy Machines Explained

Many digital systems need to do more than simply calculate an output from an input. They must remember what happened previously and use that information to decide what to do next.

A traffic-light controller, vending machine, elevator controller, communication protocol, sequence detector, and processor control unit are all examples of systems that operate this way.

The fundamental model used to design such systems is the Finite State Machine (FSM).

A finite state machine represents a digital system using a finite number of states and defined transitions between those states. At any moment, the system occupies one state. Based on its current state and input, it determines its next state and, depending on the FSM model, its output.

The fundamental relationship is:$$\boxed{\text{Present State}+\text{Input}\rightarrow\text{Next State}}$$

This article builds on the previous discussion of sequential-circuit design and explains FSMs from fundamentals through practical design, including Moore machines, Mealy machines, state diagrams, state tables, state encoding, sequence detection, state minimization, and implementation using flip-flops.

---

1. What Is a Finite State Machine?

A Finite State Machine, or FSM, is a mathematical and hardware model used to represent a system that can exist in a finite number of distinct states.

An FSM consists primarily of:

• Inputs
• Outputs
• States
• State-transition rules
• Memory elements
• Next-state logic
• Output logic

A simplified representation is:$$\boxed{ \text{Input} + \text{Present State} \rightarrow \text{Next-State Logic} \rightarrow \text{Next State} }$$

The state is stored using flip-flops.

---

2. Why Do We Need FSMs?

Consider a traffic-light controller.

The controller cannot decide its next action based only on the current sensor input. It also needs to know what phase of the traffic cycle it is currently in.

For example:$$\text{GREEN} \rightarrow \text{YELLOW} \rightarrow \text{RED} \rightarrow \text{GREEN}$$

The controller therefore needs memory.

This is exactly the type of problem an FSM solves.

Other examples include:

• Vending machines
• Elevators
• Traffic lights
• Washing machines
• Digital locks
• Serial-data detectors
• Communication controllers
• CPU control units
• Protocol controllers

---

3. The Basic FSM Model

A synchronous FSM can be viewed as three major sections:

                    ┌─────────────────────┐
Inputs ────────────►│   Next-State Logic  │
                    └──────────┬──────────┘
                               │
                               ▼
                         ┌───────────┐
                    ┌───►│ Flip-Flops│
                    │    └─────┬─────┘
                    │          │
                    │          ▼
                    │    Present State
                    │          │
                    │          ▼
                    │    ┌─────────────┐
                    └────│ Output Logic│────► Output
                         └─────────────┘

The flip-flops provide the memory required to store the current state.

The combinational logic determines:$$Q^+=F(Q,X)$$

where:

• $Q$ = present state
• $Q^+$ = next state
• $X$ = input

For the output:$$Y=G(Q,X)$$

or:$$Y=G(Q)$$

depending on the FSM type.

---

4. What Is a State?

A state represents the condition or history of the system that is relevant to its future behavior.

For example, a vending machine might have states such as:

IDLE
COIN INSERTED
PRODUCT SELECTED
DISPENSING

These states represent what the controller currently knows about the system.

A state does not necessarily correspond to a physical component. It is an abstraction used to describe the system’s behavior.

---

5. Number of States and Flip-Flops

If an FSM has $N$ states, the number of binary state bits required with ordinary binary encoding is:$$\boxed{n=\lceil\log_2N\rceil}$$

For example, four states require:$$n=\log_2 4=2$$

Therefore:$$\boxed{2\text{ flip-flops}}$$

Six states require:$$n=\lceil\log_2 6\rceil=3$$

Therefore:$$\boxed{3\text{ flip-flops}}$$

because:$$2^3=8$$

possible binary combinations are available.

---

6. FSM State Diagram

A state diagram provides a graphical representation of the FSM.

Each state is represented by a circle, while arrows represent transitions.

For example:

       ┌─────────┐
       │   S0    │
       └────┬────┘
            │
            │ X=1
            ▼
       ┌─────────┐
       │   S1    │
       └────┬────┘
            │
            │ X=0
            ▼
       ┌─────────┐
       │   S2    │
       └─────────┘

The arrows describe how the machine moves from one state to another.

---

7. State Transition

A state transition occurs when the system moves from its present state to a new state.

For example:$$S_0\xrightarrow{X=1}S_1$$

means that when the machine is in $S_0$ and:$$X=1$$

the next state becomes:$$S_1$$

At the next active clock edge, the flip-flops store the new state.

---

8. State Table

The same FSM can be represented using a state table.

A typical table contains:

Present State	Input	Next State	Output
$S_0$	0	$S_0$	—
$S_0$	1	$S_1$	—
$S_1$	0	$S_2$	—
$S_1$	1	$S_1$	—

The exact output column depends on whether the FSM is Moore or Mealy.

---

9. Two Major Types of FSMs

There are two classical FSM models:$$\boxed{\text{Moore Machine}}$$

and:$$\boxed{\text{Mealy Machine}}$$

The fundamental difference is how the output is generated.

---

10. Moore Machine

In a Moore machine, the output depends only on the present state.

Therefore:$$\boxed{Y=G(Q)}$$

The current input does not directly determine the output.

The output changes when the state changes.

---

11. Moore Machine Structure

Conceptually:

Input
  │
  ▼
┌─────────────────┐
│ Next-State Logic│
└────────┬────────┘
         │
         ▼
    ┌──────────┐
    │ Flip-Flops│
    └────┬─────┘
         │
         ▼
   Present State
         │
         ▼
   ┌────────────┐
   │Output Logic│
   └─────┬──────┘
         │
         ▼
       Output

The output logic receives the state but not the external input directly.

---

12. Moore State Diagram

In a Moore FSM, outputs are normally written inside the state.

For example:

┌─────────┐
│ S0 / 0  │
└─────────┘

means:$$S_0\rightarrow Y=0$$

Another state might be:

┌─────────┐
│ S1 / 1  │
└─────────┘

meaning:$$S_1\rightarrow Y=1$$

---

13. Mealy Machine

In a Mealy machine, the output depends on both the present state and the current input.

Therefore:$$\boxed{Y=G(Q,X)}$$

The output is associated with transitions rather than states.

---

14. Mealy Machine Structure

Conceptually:

                 ┌────────────────┐
Input ──────────►│ Next-State Logic│
    │            └───────┬────────┘
    │                    │
    │                    ▼
    │               ┌──────────┐
    │               │Flip-Flops│
    │               └────┬─────┘
    │                    │
    │                    ▼
    └──────────────► Output Logic ─────► Output

The output logic receives both:$$Q$$

and:$$X$$

---

15. Mealy State Diagram

For a Mealy machine, transitions are commonly labeled:$$\boxed{\text{Input}/\text{Output}}$$

For example:

S0 ─── 1/0 ───► S1

means:$$X=1$$

causes:$$S_0\rightarrow S_1$$

while:$$Y=0$$

for that transition.

---

16. Moore vs Mealy

Feature	Moore	Mealy
Output depends on	Present state	Present state + input
Equation	$Y=G(Q)$	$Y=G(Q,X)$
Output attached to	States	Transitions
Response	State dependent	Can respond directly to input
State count	May require more states	May require fewer states
Output behavior	Often easier to reason about	Can be more responsive
Typical concern	Additional states	Input-related output timing

Neither model is inherently superior. The appropriate architecture depends on the system requirements.

---

17. Simple Moore Example

Consider an FSM with two states:$$S_0$$

and:$$S_1$$

Suppose:

• $S_0$ has output $0$
• $S_1$ has output $1$

and the input $X$ controls the transition.

The state behavior could be:$$S_0,X=0\rightarrow S_0$$$$S_0,X=1\rightarrow S_1$$$$S_1,X=0\rightarrow S_0$$$$S_1,X=1\rightarrow S_1$$

The output is determined solely by the state:$$S_0\rightarrow Y=0$$$$S_1\rightarrow Y=1$$

Thus:$$\boxed{Y=Q}$$

with a suitable state encoding.

---

18. Simple Mealy Example

Suppose the same two states are used, but the output is generated when a particular input occurs.

For example:$$S_0\xrightarrow{1/1}S_1$$

Here:$$X=1$$

causes the output:$$Y=1$$

while the machine transitions to $S_1$.

The output therefore depends on both state and input.

---

19. Why Mealy Machines Can Use Fewer States

Suppose a particular output needs to occur only during a transition.

A Mealy machine can place that output directly on the transition.

A Moore machine may require a separate state to represent the output condition.

Therefore, in some designs:$$\boxed{\text{Mealy FSM}\rightarrow\text{Fewer States}}$$

But fewer states do not automatically mean a better design. Timing, output glitches, verification complexity, and implementation requirements must also be considered.

---

20. FSM Design Procedure

A professional FSM design usually follows a systematic process.

Step 1 — Define the specification

Determine:

• Inputs
• Outputs
• Required behavior
• Timing
• Reset conditions

Step 2 — Identify states

Determine what information must be remembered.

Step 3 — Choose Moore or Mealy

Decide how outputs should be generated.

Step 4 — Draw the state diagram

Define all required transitions.

Step 5 — Create the state table

Convert the diagram into a structured table.

Step 6 — Assign binary state codes

Encode each state.

Step 7 — Select flip-flops

D, JK, or T flip-flops can be used.

Step 8 — Derive next-state equations

Determine the logic required for each state bit.

Step 9 — Derive output equations

Determine the required output logic.

Step 10 — Simplify the equations

Use Boolean algebra or K-maps.

Step 11 — Implement and verify

Check every state, transition, output, reset condition, and timing requirement.

---

21. State Encoding

Suppose we have four states:$$S_0,S_1,S_2,S_3$$

One possible binary assignment is:

State	$Q_1Q_0$
$S_0$	00
$S_1$	01
$S_2$	10
$S_3$	11

The state encoding determines the values stored in the flip-flops.

Different encoding strategies can be used depending on the technology and design objectives.

---

22. Binary State Encoding

Binary encoding uses approximately:$$\boxed{\lceil\log_2N\rceil}$$

state bits for $N$ states.

For example, eight states require:$$\log_2 8=3$$

bits.

Therefore:$$\boxed{3\text{ flip-flops}}$$

can represent:$$000\text{ through }111$$

---

23. One-Hot Encoding

Another approach is one-hot encoding.

With one-hot encoding, each state is represented by a separate flip-flop.

For four states:$$S_0=0001$$$$S_1=0010$$$$S_2=0100$$$$S_3=1000$$

Therefore:$$\boxed{4\text{ states}\rightarrow4\text{ flip-flops}}$$

instead of two.

This uses more flip-flops but can simplify the next-state logic and is commonly useful in FPGA-based designs.

---

24. State Reduction

Two states may sometimes be equivalent from the external system’s perspective.

If two states produce identical outputs and equivalent future behavior for every possible input, they may be candidates for merging.

This process is called:$$\boxed{\text{State Reduction}}$$

The objective is to reduce the complexity of the FSM without changing its externally observable behavior.

---

25. Sequence Detector

One of the classic FSM applications is a sequence detector.

Suppose a serial input stream is:$$1,\ 0,\ 1$$

and the system must detect the sequence:$$\boxed{101}$$

The FSM needs to remember how much of the sequence has already been received.

Possible conceptual states are:

S0 → Nothing matched
S1 → 1 detected
S2 → 10 detected
S3 → 101 detected

When the final required bit arrives, the FSM generates a detection output.

---

26. Sequence Detector Example

Suppose the input sequence is:

1 0 1

The FSM can progress as:$$S_0 \xrightarrow{1} S_1$$

then:$$S_1 \xrightarrow{0} S_2$$

then:$$S_2 \xrightarrow{1} S_3$$

At $S_3$, the sequence:$$101$$

has been detected.

This example demonstrates why memory is required: the circuit must remember previous input bits.

---

27. Overlapping Sequence Detection

An advanced sequence detector may allow overlapping patterns.

For example:

10101

contains overlapping occurrences of:$$101$$

The FSM must determine whether part of the detected sequence can simultaneously serve as the beginning of another sequence.

This requires carefully designed state transitions.

It is an excellent example of why state diagrams are useful.

---

28. FSMs and Flip-Flops

The FSM’s state is physically stored using flip-flops.

Suppose an FSM requires two state bits:$$Q_1,Q_0$$

Then two flip-flops store the present state.

The combinational logic calculates:$$Q_1^+$$

and:$$Q_0^+$$

before the next active clock edge.

At the clock edge:$$(Q_1,Q_0) \rightarrow (Q_1^+,Q_0^+)$$

The process repeats every clock cycle.

---

29. FSM Using D Flip-Flops

D flip-flops are especially convenient for FSM implementation.

Since:$$\boxed{D=Q^+}$$

the next-state equations directly become the D inputs.

For a two-bit FSM:$$D_1=Q_1^+$$$$D_0=Q_0^+$$

The implementation therefore becomes:

Next-State Logic
      │
      ├────► D1 ──► Flip-Flop ──► Q1
      │
      └────► D0 ──► Flip-Flop ──► Q0

---

30. FSM Using JK Flip-Flops

JK flip-flops can also implement FSMs.

The required $J$ and $K$ values are determined using the JK excitation table.

Q	$Q^+$	J	K
0	0	0	X
0	1	1	X
1	0	X	1
1	1	X	0

The designer uses this table to determine the logic driving each JK input.

---

31. FSM Using T Flip-Flops

For T flip-flops:$$\boxed{T=Q\oplus Q^+}$$

Therefore, once the desired transition is known:$$T_0=Q_0\oplus Q_0^+$$$$T_1=Q_1\oplus Q_1^+$$

This provides the required toggle logic.

---

32. Output Logic

The output equations depend on the FSM model.

Moore

$$\boxed{Y=G(Q)}$$

Mealy

$$\boxed{Y=G(Q,X)}$$

For multiple outputs:$$Y_1=G_1(Q,X)$$$$Y_2=G_2(Q,X)$$

and so on.

---

33. Reset in an FSM

An FSM should normally have a defined starting state.

For example:$$\boxed{RESET\rightarrow S_0}$$

If the system powers up in an unintended state, its behavior may become unpredictable.

Reset ensures that the machine starts from a known condition.

---

34. Unused States

Suppose an FSM has six valid states but uses three flip-flops.

Three flip-flops provide:$$2^3=8$$

possible binary states.

Therefore:$$8-6=2$$

states are unused.

The designer should decide what happens if the machine enters one of these states.

A robust FSM can be designed so that an unused state transitions back to a valid state.

---

35. Synchronous FSM Timing

A typical synchronous FSM operates in this cycle:$$\boxed{ \text{Clock Edge} \rightarrow \text{State Update} \rightarrow \text{Combinational Evaluation} \rightarrow \text{Next State Ready} \rightarrow \text{Next Clock Edge} }$$

The combinational logic must settle sufficiently before the next sampling edge.

A simplified timing requirement is:$$\boxed{ T_{CLK} \geq t_{CQ} + t_{logic} + t_{setup} }$$

Real implementations additionally consider clock skew, jitter, routing delays, and timing margins.

---

36. FSM vs Counter

Counters are themselves sequential circuits, but not every FSM is a counter.

A binary counter follows a numerical sequence:$$000\rightarrow001\rightarrow010\rightarrow011\rightarrow\cdots$$

An FSM can follow an arbitrary sequence based on inputs.

For example:$$S_0\rightarrow S_2\rightarrow S_1\rightarrow S_3$$

The transition may depend on external conditions.

Therefore:$$\boxed{\text{Every counter is a sequential system, but an FSM is much more general.}}$$

---

37. FSM Applications

FSMs are fundamental to many digital systems.

Control Units

Processors use control logic to coordinate operations.

Communication Protocols

FSMs can represent protocol states such as:$$IDLE\rightarrowSTART\rightarrowDATA\rightarrowSTOP$$

Traffic Controllers

States represent:$$GREEN,\ YELLOW,\ RED$$

Vending Machines

States represent inserted money, selection, dispensing and change.

Sequence Detectors

FSMs recognize specific binary patterns.

Embedded Controllers

FSMs control the behavior of hardware devices.

---

38. Common FSM Design Mistakes

Mistake 1 — Missing a transition

Every relevant state/input combination should have defined behavior.

Mistake 2 — Confusing Moore and Mealy outputs

Remember:$$\boxed{Moore:Y=G(Q)}$$$$\boxed{Mealy:Y=G(Q,X)}$$

Mistake 3 — Forgetting reset

An FSM should normally have a defined startup state.

Mistake 4 — Ignoring unused states

Unused binary combinations should be handled deliberately.

Mistake 5 — Incorrect state encoding

The assigned binary values must be used consistently throughout the state table and equations.

Mistake 6 — Ignoring timing

A logically correct FSM can still fail if its timing constraints are violated.

---

39. Professional FSM Design Workflow

The entire process can be summarized as:

SYSTEM REQUIREMENT
        ↓
INPUTS + OUTPUTS
        ↓
DEFINE STATES
        ↓
CHOOSE MOORE / MEALY
        ↓
STATE DIAGRAM
        ↓
STATE TABLE
        ↓
STATE ENCODING
        ↓
SELECT FLIP-FLOPS
        ↓
EXCITATION TABLE
        ↓
NEXT-STATE EQUATIONS
        ↓
OUTPUT EQUATIONS
        ↓
LOGIC SIMPLIFICATION
        ↓
HARDWARE IMPLEMENTATION
        ↓
TIMING ANALYSIS
        ↓
VERIFICATION

This workflow converts a high-level behavioral requirement into an implementable sequential digital circuit.

---

40. Important FSM Equations

General Next-State Function

$$\boxed{Q^+=F(Q,X)}$$

Moore Output

$$\boxed{Y=G(Q)}$$

Mealy Output

$$\boxed{Y=G(Q,X)}$$

Required Binary State Bits

$$\boxed{n=\lceil\log_2N\rceil}$$

D Flip-Flop

$$\boxed{D=Q^+}$$

T Flip-Flop

$$\boxed{T=Q\oplus Q^+}$$

JK Flip-Flop

$$\boxed{Q^+=J\overline Q+\overline KQ}$$

Typical Clock Constraint

$$\boxed{ T_{CLK}\geq t_{CQ}+t_{logic}+t_{setup} }$$

---

41. Quick Revision

What is an FSM?

A sequential model containing a finite number of states and defined transitions.

What stores the state?

Flip-flops or other memory elements.

What determines the next state?

The next-state combinational logic.

What is a Moore machine?

An FSM where:$$Y=G(Q)$$

What is a Mealy machine?

An FSM where:$$Y=G(Q,X)$$

How many flip-flops are needed for $N$ binary-encoded states?

$$\boxed{\lceil\log_2N\rceil}$$

What is state reduction?

Combining equivalent states while preserving the external behavior of the FSM.

---

Conclusion

Finite State Machines provide a systematic way to design digital systems that must remember, make decisions, and respond according to their previous history.

The central concept is:$$\boxed{ \text{Present State}+\text{Input} \rightarrow \text{Next State} }$$

The state is stored in flip-flops, while combinational logic determines the next state and output.

The two fundamental FSM models are:$$\boxed{\text{Moore: }Y=G(Q)}$$

and:$$\boxed{\text{Mealy: }Y=G(Q,X)}$$

Once state diagrams, state tables, state encoding and next-state equations become familiar, you can design much more complex digital controllers—from simple sequence detectors to processor control units.

Next in the series: Memory in Digital Electronics — RAM, ROM, SRAM, DRAM, EEPROM, Memory Organization and Addressing, where we move from flip-flop-level storage to practical semiconductor memory systems.