Skills Built:Moore/Mealy Machine DesignState Table & Diagram ConstructionSequence Detector DesignBinary vs One-Hot Encoding

1. Intuition First: States as Circuit Memory

Consider a vending machine dispensing a $1.50 drink. It does not need to remember the serial number of every coin inserted or the history of past transactions from yesterday. It only needs to know one single summary piece of information: **how much credit is currently accumulated** ($ 0.00, $0.50,$ 1.00, or $1.50).

That stored snapshot of past history is the machine's state:

Each incoming coin is an input ( $X$ ) that transitions the machine to a new state.
Once the credit reaches $1.50, the machine activates an **output** ($ Z$) to unlatch the dispenser solenoid.
The entire operational universe of this system can be drawn on a single sheet of paper as a State Diagram consisting of circles (states) and directed arrows (transitions).

        +----------+    Coin = $0.50    +----------+    Coin = $0.50    +----------+
Reset ->|  $0.00   |------------------->|  $0.50   |------------------->|  $1.00   |
        +----------+                    +----------+                    +----------+
             ^                                                                |
             |                                                                | Coin = $0.50
             |                  Dispense Drink (Z = 1)                        v
             +----------------------------------------------------------+----------+
                                                                        |  $1.50   |
                                                                        +----------+

Moore vs. Mealy Architectures

Every synchronous Sequential Machine is categorized into one of two fundamental models:

Moore Machine: The output depends only on the current state ( $Z = g(Q)$ ).
- In a vending machine, the front-panel display says "DISPENSE" purely because the system is currently residing in the $1.50 state.
- Outputs are strictly synchronized with clock edges, eliminating combinational input glitches.
- For an $N$ -bit sequence detector, a Moore machine requires $N + 1$ states.
Mealy Machine: The output depends on both the current state and the current external input ( $Z = g(Q, X)$ ).
- The drink is released on the exact moment the final coin drops into the slot while in the $1.00 state.
- Outputs respond immediately within the clock cycle when input $X$ changes, reacting one clock cycle faster than Moore machines.
- Glitch hazard: any noise or ripple on input line $X$ propagates straight through combinational logic to output $Z$ .
- For an $N$ -bit sequence detector, a Mealy machine requires only $N$ states.

2. Formula & Unit Quick-Reference Strip

Formula & Unit Quick-Reference Strip

Next-State FunctionState vector

Q^+ = f(Q, X)

Next state Q^+ is a combinational boolean function of present state Q and primary input X.

Moore Output FunctionOutput vector

Z = g(Q)

Moore outputs depend purely on present state Q, changing only synchronously at clock edges.

Mealy Output FunctionOutput vector

Z = g(Q, X)

Mealy outputs depend on both state Q and input X, responding asynchronously to input changes.

D Flip-Flop ExcitationLogic equation

D_i = Q_i^+

D flip-flop captures its input directly on clock edge, so D input equals desired next state.

Binary State EncodingFlip-flops

n = ceil(log2 S)

Minimum flip-flop count to represent S unique states using compact binary codes.

One-Hot State EncodingFlip-flops

n = S

Uses one flip-flop per state; state bit i is HIGH only in state i, simplifying combinational logic.

101 Sequence DetectorStates (2 FFs)

S_Moore = 4, S_Mealy = 3

Overlapping 3-bit pattern requires 4 states in Moore architecture and 3 states in Mealy architecture.

3. Mathematical Derivation: 101 Moore Sequence Detector

4. Typical Bench Values & Timing Parameters

When implementing FSMs using discrete TTL/CMOS logic (e.g., 74HC74 dual D flip-flop) or FPGA register slices, timing parameters determine the maximum reliable clock frequency:

Typical Laboratory Hardware Ranges

Parameter / Part	Typical Value	Lab Range	Practical Notes
Logic Supply Voltage (V_CC)	3.3V or 5.0V DC	2.0V - 6.0V (CMOS)	Standard rail for 74HC/74HCT logic chips
Clock Frequency (f_max)	25 MHz to 100 MHz	1 MHz - 250 MHz	Depends on critical path: t_clk >= t_cq + t_comb + t_su
Clock-to-Q Delay (t_cq)	14 ns	8 ns - 30 ns	Delay from clock rising edge until Q outputs change
Setup Time (t_su)	15 ns	10 ns - 25 ns	Minimum time next-state logic D must stabilize before clock edge
Hold Time (t_h)	3 ns	0 ns - 5 ns	Time D input must remain stable after clock edge triggers
Mealy Glitch Duration (t_glitch)	2 ns to 8 ns	0.5 ns - 15 ns	Asynchronous output spikes caused by unequal input wire delays

5. Worked Engineering Examples

Example 1: Tracing the Overlapping Moore Detector

Step-by-Step Worked Problem

Trace the Moore 101 sequence detector designed in Section 3 across the serial input bitstream X = [1, 0, 1, 0, 1, 1, 0, 1] starting from initial reset state S0. Identify all clock cycles where pattern detection is declared.

Step 1: Cycle-by-cycle state transition tracing

Clock 1: Present state S0 (00), X=1 -> Next state S1 (01), Output Z=0. Clock 2: Present state S1 (01), X=0 -> Next state S2 (10), Output Z=0. Clock 3: Present state S2 (10), X=1 -> Next state S3 (11), Output Z=1 (MATCH 1! Pattern '101' completed). Clock 4: Present state S3 (11), X=0 -> Next state S2 (10) due to overlap '10', Output Z=0. Clock 5: Present state S2 (10), X=1 -> Next state S3 (11), Output Z=1 (MATCH 2! Overlapping '101' completed). Clock 6: Present state S3 (11), X=1 -> Next state S1 (01), Output Z=0. Clock 7: Present state S1 (01), X=0 -> Next state S2 (10), Output Z=0. Clock 8: Present state S2 (10), X=1 -> Next state S3 (11), Output Z=1 (MATCH 3! Pattern '101' completed).

Step 2: Verification of overlap handling

Notice clock 3 ends in '101'. When input 0 arrives at clock 4 followed by 1 at clock 5, the sequence is '1-0-1-0-1'. The second '1' of Match 1 serves as the starting bit of Match 2. An overlapping machine flags both without requiring a reset back to S0.

Example 2: Gate-Level Hardware Verification

Step-by-Step Worked Problem

Verify the excitation circuit at state S2 (Q1=1, Q0=0). When incoming bit X=1 arrives, evaluate D1, D0, and the resulting next state, confirming it transitions to S3.

Step 1: Evaluate D0 equation

From derivation: D0 = X. For X = 1, D0 = 1.

Step 2: Evaluate D1 equation

From derivation: D1 = Q0 * X' + Q1 * Q0' * X. Substituting present state Q1=1, Q0=0, and X=1: D1 = (0 * 0) + (1 * 1 * 1) = 0 + 1 = 1.

Step 3: Determine next state Q1+ Q0+

On the upcoming clock rising edge, flip-flops sample inputs: Q1+ = D1 = 1, Q0+ = D0 = 1. The resulting state vector is 11, which corresponds to state S3.

Example 3: Mealy Implementation Comparison

Step-by-Step Worked Problem

Design the 3-state Mealy equivalent for the 101 overlapping detector. Contrast state count, output timing, and glitch susceptibility against the Moore machine.

Step 1: State allocation

Mealy machines embed output onto transition arcs (X/Z). Only 3 states are required: S0: No bits matched (reset) S1: Last bit is 1 S2: Last two bits are 10 When in S2 and input X=1 arrives, pattern '101' is complete right now! The transition arc is S2 -> S1 with output Z = 1 (written as 1/1).

Step 2: Output timing difference

In the Mealy machine, Z becomes 1 immediately during clock cycle 3 as soon as input X settles to 1 (combinational path). In the Moore machine, Z becomes 1 only after clock edge 3 latches state S3. Mealy indicates detection one clock cycle earlier.

Step 3: Trade-off summary

Mealy uses fewer states (3 vs 4) and saves one state condition, but output Z depends combinationally on input line X. False pulses (glitches) on line X will immediately propagate to Z during the clock period.

6. Common Exam Traps & Where Marks Are Lost

Common Exam Traps & Where Marks Are Lost

Avoid these classic calculation errors frequently spotted on semester examination answer scripts:

Forgetting Sequence Overlap: After pattern 101 is matched, never jump straight back to reset state S0! The trailing '1' can form the first bit of the next match. Jumping to S0 misses overlapping occurrences like 10101.
Drawing Mealy Outputs Inside State Circles: Moore outputs belong inside state circles (State/Output, e.g., S3/1). Mealy outputs belong strictly on transition arrows alongside the input (Input/Output, e.g., X=1/Z=1). Mixing this up loses full marks on state diagrams.
Incomplete State Tables: Every state MUST define transitions for EVERY possible input combination (e.g., both X=0 and X=1). Leaving an input condition blank leaves the hardware undefined.
Ignoring Unused State Codes: When 3 states are encoded with 2 flip-flops (00, 01, 10), state 11 is unused. Always verify next-state logic for unused codes to ensure the circuit self-recovers and does not lock up permanently.
Confusing Present State Q with Next State Q+: Remember that flip-flop inputs D equal next state Q+ (D = Q+), NOT present state Q. Never write excitation equations in terms of Q+.
Assuming Mealy Outputs Are Clocked: Mealy outputs are combinational functions of both Q and X. They change immediately when X changes, even midway between clock ticks.

7. Interactive Logic Simulation & 'Try Breaking It'

Analyze serial sequence detection, clock timing, and state transitions using the logic analyzer below:

[Simulator "logic-analyzer" not found in registry]

Try Breaking It: Predict Before You Test

Feed the stream 10101 into the Moore detector and predict how many matches it reports. Then change the transition arrow from S3 on X=0 so it returns to S0 instead of S2, and predict again.

8. Parametrised Practice Problem

Test your sequential design mastery with custom sequence detection parameters:

Parametrised Practice Problem

Thévenin Equivalent of a Loaded Voltage Divider

A 18 V DC voltage source powers a divider with R1 = 50 Ω and R2 = 20 Ω. Calculate the open-circuit Thévenin voltage V_th (in Volts) appearing across terminals of R2.

Progressive Hints:

9. Unit Mastery Quiz

5-Question Mastery Check

Unit Quiz: Finite State Machines

Q1.In which finite state machine architecture do outputs depend solely on the present state?

Q2.What is the minimum number of flip-flops required to implement an FSM with 5 distinct states using standard binary encoding?

Q3.When can the output of an asynchronous Mealy machine change?

Q4.An overlapping sequence detector for pattern '101' receives the input stream 1010101. How many detections are registered?

Q5.How many flip-flops are required to implement a 6-state FSM using one-hot state encoding?

0 of 5 answered