Digital Logic on the DE1-SoC (5/6): Finite state machines

You have already built circuits that remember: a flip-flop holds one bit, a register holds several, a counter holds its current count. A finite state machine (FSM) is the idea that organizes that memory into *meaningful situations*. At any moment the machine is in exactly one of a small, fixed set of states — for a traffic light, the states might be GREEN, YELLOW, and RED. The number of states is finite (hence the name), and the machine is always in precisely one of them.

An FSM is defined by three things:

- States — the finite set of situations the machine can be in. One special state is the reset state, where the machine starts.
- Transitions — the rules for moving from one state to another. On each clock edge, the machine looks at its current state and its inputs and decides which state to be in next. The transition GREEN -> YELLOW says "if you are in GREEN and the condition holds, go to YELLOW on the next edge."
- Outputs — what the machine drives on its outputs (here, the LEDs) in each situation.

The whole machine advances on the clock: at each edge it (possibly) moves to a new state based on the current state and the current inputs, and it holds that state until the next edge. Between edges it does nothing but wait — exactly the sample-and-hold behavior you saw with flip-flops, now used to step through a sequence of states.

Moore versus Mealy. FSMs come in two flavors that differ only in *where the outputs come from*:

- In a Moore machine, the outputs depend only on the current state. If you know the state, you know the outputs — the inputs do not appear in the output equation. The traffic light is Moore: when the state is RED, the red LED is on, full stop.
- In a Mealy machine, the outputs depend on the current state and the current inputs together. The same state can produce different outputs depending on what the input is doing right now. The sequence detector is Mealy: it asserts "detected" in a particular state *only when the incoming bit is also the right value*.

Moore outputs are steady for as long as you stay in a state. Mealy outputs can change the instant an input changes, even without leaving the state — which makes them quick but also potentially brief and glitchy, a point that will matter on the camera.

The standard Verilog shape of an FSM. Almost every FSM in this course is written as two or three blocks working together:

1. A state register — a clocked block (always @(posedge clock ...)) that holds the current state and, on each edge, copies in the next state. This is the only block that has memory.
2. A next-state block — a combinational block (always @(*)) that, given the current state and inputs, computes which state should come next. It must include a default (a fallback next_state = ... and a default: case) so that *every* path assigns a value; a missing default would infer an unwanted latch.
3. Output logic — either assign statements or part of a combinational block that drives the outputs from the state (Moore) or from state and inputs (Mealy).

You will see both designs in this lesson follow exactly this shape: a clocked state register, an always @(*) next-state block with a default, and output logic.

Before you build anything, one deliberate change from earlier lessons.

In Lessons 2 and 3 your flip-flops and registers used a synchronous reset: the reset was tested *inside* the clocked block, like if (!KEY[0]) Q <= 0; inside always @(posedge CLOCK_50). Because that test only runs at a clock edge, a synchronous reset takes effect only on the next rising edge — if the clock is slow, the reset waits for it.

The FSMs in this lesson use an active-low asynchronous reset instead. Look at the state register's sensitivity list:

always @(posedge slow_clk or negedge KEY[0]) begin
    if (!KEY[0]) state <= GREEN;   // asynchronous: fires the instant KEY[0] goes low
    else         state <= next_state;
end

Adding or negedge KEY[0] to the sensitivity list means the block also wakes up the instant KEY[0] goes low (the moment you press the button), not only on a slow_clk edge. So pressing KEY[0] forces the machine to its known state immediately, without waiting for the (slow) clock.

State the difference clearly:

- Synchronous reset (Lessons 2-3): takes effect only on a clock edge. Clean and predictable, but if the clock is slow you wait for the edge.
- Asynchronous reset (Lessons 5-6): takes effect immediately, the moment the reset signal asserts, regardless of the clock.

Why the change here? These FSMs run from a divided slow_clk whose edges are seconds apart. If reset were synchronous you might press KEY[0] and watch nothing happen for over a second until the next slow edge — and if the machine were stuck, that is exactly when you most want an instant escape. An asynchronous reset gives you that immediate, reliable "force back to the start" on the real board. KEY is active-low, so negedge KEY[0] is the moment you press the button and !KEY[0] is true while it is held.

Your first FSM is a traffic-light controller. It has three states and steps through them in a fixed cycle, holding each light for a set number of ticks:

GREEN -> YELLOW -> RED -> GREEN -> ...

The wiring is LEDR[0] = green, LEDR[1] = yellow, LEDR[2] = red, and KEY[0] = reset (active-low) which returns the machine to GREEN. The machine is clocked from a divided slow_clk: each slow_clk edge is one tick, about 0.33 s with this divider.

This is a Moore machine. The output logic at the bottom is

assign LEDR[0] = (state == GREEN);
assign LEDR[1] = (state == YELLOW);
assign LEDR[2] = (state == RED);

Every LED is a function of the state alone — no input appears. Knowing the state tells you exactly which light is on. That is the defining property of a Moore machine.

Two separate registers do two separate jobs. Read the state register carefully, because it contains *two* pieces of memory that are easy to confuse:

- state (a reg [1:0]) holds which light is currently on — GREEN, YELLOW, or RED. This is the FSM state.
- timer (a reg [2:0]) is a separate dwell counter that counts down how many ticks remain in the current light. While timer is greater than zero it just decrements (timer <= timer - 1) and the state does not change. Only when timer reaches 0 does the machine advance to next_state and reload timer for the new light.

So the state register holds *which* light is on, and the timer counts *how long* it stays on. They are different registers with different purposes; the timer is what makes each light dwell instead of flashing past in one tick.

The actual dwell times, from the code. When the machine enters each state it reloads timer, and counting from the loaded value down to 0 inclusive gives the number of ticks:

- GREEN loads timer = 3 and counts 3, 2, 1, 0 -> 4 ticks (about 1.33 s).
- YELLOW loads timer = 1 and counts 1, 0 -> 2 ticks (about 0.67 s).
- RED loads timer = 3 -> 4 ticks (about 1.33 s).

One full cycle is therefore 4 + 2 + 4 = 10 ticks, roughly 10 x 0.33 s = 3.3 s end to end.

Here is the complete module. The divider produces slow_clk; the state register (with asynchronous reset) advances the light when the dwell timer expires; the always @(*) block computes the next light; and the three assign lines are the Moore output logic.

// Lesson 5 - Exercise 3-A: traffic light controller (Moore FSM)
// KEY[0]=reset (active-low, returns to GREEN). LEDR[0]=green, LEDR[1]=yellow, LEDR[2]=red.
// Dwell times: GREEN = 4 ticks, YELLOW = 2 ticks, RED = 4 ticks (one tick = one slow_clk edge, ~0.33 s).
// This FSM uses active-low ASYNCHRONOUS reset in the state register so KEY[0] forces GREEN immediately.
module leds_mirror(CLOCK_50, KEY, LEDR);
    input        CLOCK_50;
    input  [3:0] KEY;       // KEY[0] = reset_n
    output [9:0] LEDR;

    localparam GREEN = 2'd0, YELLOW = 2'd1, RED = 2'd2;

    localparam [24:0] DIV = 25'd16_666_666;   // slow_clk edge ~every 0.33 s
    reg [24:0] div;
    reg        slow_clk;
    always @(posedge CLOCK_50) begin
        if (!KEY[0]) begin div <= 0; slow_clk <= 0; end
        else if (div == DIV) begin div <= 0; slow_clk <= ~slow_clk; end
        else div <= div + 1'b1;
    end

    reg [1:0] state, next_state;
    reg [2:0] timer;
    always @(posedge slow_clk or negedge KEY[0]) begin
        if (!KEY[0]) begin state <= GREEN; timer <= 3'd3; end
        else if (timer == 3'd0) begin
            state <= next_state;
            case (next_state)
                GREEN:   timer <= 3'd3;   // 4 ticks (3,2,1,0)
                YELLOW:  timer <= 3'd1;   // 2 ticks
                RED:     timer <= 3'd3;   // 4 ticks
                default: timer <= 3'd3;
            endcase
        end else timer <= timer - 1'b1;
    end

    always @(*) begin
        case (state)
            GREEN:   next_state = YELLOW;
            YELLOW:  next_state = RED;
            RED:     next_state = GREEN;
            default: next_state = GREEN;
        endcase
    end

    assign LEDR[0]   = (state == GREEN);
    assign LEDR[1]   = (state == YELLOW);
    assign LEDR[2]   = (state == RED);
    assign LEDR[9:3] = 7'b0;
endmodule

Now build the traffic light on the real DE1-SoC, time each phase, and then change it.

Upload your evidence. Watch for the YELLOW phase, capture a camera screenshot at a moment when LEDR[1] (yellow) is lit while LEDR[0] (green) and LEDR[2] (red) are off, and attach it below.

Now make two changes to the design.

(Modify) Change the dwell times. Edit the timer reload values so the cycle is GREEN = 6 ticks, YELLOW = 2 ticks, RED = 6 ticks. Remember the timer counts from its loaded value down to 0 inclusive, so N ticks means loading N - 1: load 5 for GREEN, 1 for YELLOW, and 5 for RED (in both the case inside the state register and the reset line if a state's reset value changes). Synthesize, Upload, and confirm the new timings on the camera. Then work out the new total cycle length in ticks.

(Add) A flashing-red state. Add a fourth state, FLASH_RED, that the machine enters after RED (so the cycle becomes GREEN -> YELLOW -> RED -> FLASH_RED -> GREEN). In FLASH_RED, the red LED should toggle on and off for a few ticks (for example, blink for 4 ticks) and then the machine returns to GREEN. Hints: widen state/next_state to hold a fourth value, add FLASH_RED to the localparam list and to the next-state case, give it a dwell in the timer case, and drive LEDR[2] in FLASH_RED from a bit that flips each tick (for instance, the low bit of the timer) instead of a steady 1. Synthesize, Upload, and confirm the red LED blinks in the new phase before the light returns to green.

Your second FSM watches a stream of bits arriving one per clock tick on SW[0] and lights an LED whenever it has just seen the pattern 1011. This is a Mealy machine: it asserts "detected" in a particular state *only when the incoming bit is also correct*, so the output depends on state and input together.

The wiring is SW[0] = the serial input bit, KEY[0] = reset (active-low), LEDR[0] = detected, and LEDR[4:1] = the current state shown one-hot (one LED per state) so you can watch the machine move. The machine is clocked from a divided slow_clk whose rising edge — one tick — happens about every 1.33 s with this divider.

The states. The detector remembers how much of 1011 it has matched so far:

- S0 — nothing matched yet (the reset state).
- S1 — the last bit was 1 (matched 1).
- S2 — matched 10.
- S3 — matched 101.
- S4 — matched the full 1011. From here the machine can still start a new match, which is what makes overlapping detections work (the trailing 1 of one 1011 can be the leading 1 of the next).

On each tick, the next-state block looks at the current state and the bit on SW[0] and moves accordingly. The detect output is asserted inside S3 only when the incoming bit is 1 (because 101 followed by 1 completes 1011) — that is the Mealy output, asserted from state and input.

Why we latch the output — read this carefully. The raw Mealy detect signal is high for only one tick. On a fast clock that pulse would be invisible; even on this slow clock, a single ~1.33 s flash is easy to miss on a remote camera if you blink or the frame lands wrong. So this design does not wire detect straight to the LED. Instead it latches the detection: a separate detected_latch register is set to 1 when detect fires and stays set until you press reset. LEDR[0] shows that latch, so once 1011 is detected the LED comes on and *stays on* until KEY[0]. This is a deliberate design choice for remote viewing: a one-tick pulse is unreliable to capture, so we convert the brief event into a steady, latched indication.

Here is the complete module. Note the two-block shape: a combinational always @(*) computes next_state and the Mealy detect, and a clocked always @(posedge slow_clk or negedge KEY[0]) holds the state and the latch (with asynchronous reset).

// Lesson 5 - Exercise 3-B: "1011" sequence detector (Mealy FSM) with a latched detect LED
// SW[0]=serial input bit. KEY[0]=reset (active-low). LEDR[0]=detected (LATCHED until reset).
// LEDR[4:1]=current state (one-hot) for debugging.
// Feed a bit: set SW[0], wait one slow-clock tick (~1.33 s), change SW[0], wait again, ...
// The Mealy "detected" pulse is one tick long, so we latch it into LEDR[0] for a remote camera.
module leds_mirror(CLOCK_50, KEY, SW, LEDR);
    input        CLOCK_50;
    input  [3:0] KEY;       // KEY[0] = reset_n
    input  [9:0] SW;        // SW[0] = serial input
    output [9:0] LEDR;

    localparam [26:0] DIV = 27'd33_333_333;
    reg [26:0] div;
    reg        slow_clk;
    always @(posedge CLOCK_50) begin
        if (!KEY[0]) begin div <= 0; slow_clk <= 0; end
        else if (div == DIV) begin div <= 0; slow_clk <= ~slow_clk; end
        else div <= div + 1'b1;
    end

    localparam S0=3'd0, S1=3'd1, S2=3'd2, S3=3'd3, S4=3'd4;
    reg [2:0] state, next_state;
    reg       detect;
    always @(*) begin
        next_state = S0;
        detect     = 1'b0;
        case (state)
            S0: next_state = SW[0] ? S1 : S0;
            S1: next_state = SW[0] ? S1 : S2;          // extra 1s keep us at "got 1"
            S2: next_state = SW[0] ? S3 : S0;
            S3: if (SW[0]) begin next_state = S4; detect = 1'b1; end  // 1011 complete (Mealy output)
                else        next_state = S2;            // overlap: "...10" seen again
            S4: next_state = SW[0] ? S1 : S0;
            default: next_state = S0;
        endcase
    end

    reg detected_latch;
    always @(posedge slow_clk or negedge KEY[0]) begin
        if (!KEY[0]) begin state <= S0; detected_latch <= 1'b0; end
        else begin
            state <= next_state;
            if (detect) detected_latch <= 1'b1;   // stays lit until you press reset
        end
    end

    assign LEDR[0]   = detected_latch;
    assign LEDR[4:1] = (state==S0) ? 4'b0001 :
                       (state==S1) ? 4'b0010 :
                       (state==S2) ? 4'b0100 :
                       (state==S3) ? 4'b1000 : 4'b0000;   // S4 shown as 0000
    assign LEDR[9:5] = 5'b0;
endmodule

Now build the detector and feed it bits by hand. How to feed one bit: set SW[0] to the bit value, then wait one full slow-clock tick (about 1.33 s) so the machine samples it on the next rising edge, then change SW[0] to the next bit and wait again. Watch LEDR[4:1] to follow the state as you go.

Upload your evidence. After feeding 1, 0, 1, 1, LEDR[0] (detected) latches on and stays lit until reset — a steady state you can photograph. Capture a camera screenshot showing LEDR[0] latched on, and attach it below.

Now modify the detector.

(Modify) Detect 101 instead of 1011. First draw the new state diagram on paper: you need states for "nothing matched," "matched 1," and "matched 10," and the detect output should fire when, in the "matched 10" state, the next bit is 1 (completing 101). Think about overlap: after detecting 101, the trailing 1 can be the start of the next 101. Then edit the Verilog — you can drop S4, retarget the transitions so detect is asserted on the 10-then-1 step, and keep the latch and the one-hot state display. Synthesize, Upload, and confirm that feeding 1, 0, 1 latches LEDR[0].

You built two finite state machines on the real DE1-SoC: a Moore traffic-light controller, whose outputs depend on the state alone and which steps GREEN -> YELLOW -> RED on a dwell timer; and a Mealy 1011 sequence detector, whose detect output depends on the state and the input together. You used the standard FSM shape — a clocked state register, a combinational next-state block with a default, and output logic — and an active-low asynchronous reset that forces a known state immediately. You also saw why a one-tick output is latched so a remote camera can catch it.