UART receiver state machine

How it works, edge by edge

The reset is released at tick 2, and at tick 3 rx falls: the start bit. rx is the line itself and changes between edges; the machine sees it at the next rising edge, and at edge 0 it takes the arrow from IDLE to START on !rx.

To fit a frame into four clock periods, tick stays high from edge 0 on, as if every clock were the middle of a bit. On a real line it comes once per bit period, many clocks apart, and the machine simply waits in each state between ticks.

At edge 1 START checks the line in the middle of the start bit: it is still low, so the start bit was real and the machine enters DATA. Straight away shift goes high, a whole period before the edge that shifts: a Mealy output follows the arrow that would fire, and in DATA with tick high that is the loop that shifts a bit in. At edge 2 it does, and last rises: in this short frame that was the only data bit.

Now both conditions out of DATA are true: tick && last to STOP, and tick round the loop. The first has priority 1, so it is the one selected, and shift falls at once, a period before the edge: Mealy outputs follow the selected arrow, not every true condition. At edge 3 the machine enters STOP, where the script pauses. That edge was the middle of the stop bit, and STOP reads the line at its very next edge, still inside the stop bit. The line is high, so the arrow back to IDLE on rx is the one that would fire, and done is high.

Framing error leaves rx low through the stop bit: the other arrow from STOP fires, and err reports it on the way back to IDLE. False start lets rx go high again before the middle of the start bit; at the next tick START sees it and goes back to IDLE.

The code

// The control state machine of a UART receiver; the counters are outside it.
// tick marks the middle of each bit, last that the final data bit is in, rx is
// the line. STOP is entered mid stop bit and reads rx at its first edge.
//
// Reset style for this module: asynchronous, active low. One style per page,
// stated up front, so nothing on the page has to be read twice.
module uart_rx (
    input  logic clk,
    input  logic rst_n,
    input  logic rx,
    input  logic tick,
    input  logic last,
    output logic busy,
    output logic shift,
    output logic done,
    output logic err
);

  typedef enum logic [1:0] {
    IDLE  = 2'd0,
    START = 2'd1,
    DATA  = 2'd2,
    STOP  = 2'd3
  } state_t;

  state_t state, next;

  // The state register: the only flip-flops in the module.
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      state <= IDLE;
    end else begin
      state <= next;
    end
  end

  // Next state, and the Mealy outputs: they belong to a transition, so they
  // are driven where the transition is chosen. Every default is assigned
  // first, so no branch can leave a latch behind.
  always_comb begin
    next  = state;
    shift = 1'b0;
    done  = 1'b0;
    err   = 1'b0;
    unique case (state)
      IDLE: begin
        if (!rx) next = START;
      end
      START: begin
        if (tick && !rx) next = DATA;
        else if (tick && rx) next = IDLE;
      end
      DATA: begin
        if (tick && last) next = STOP;  // priority 1
        else if (tick) begin  // priority 2
          next  = DATA;
          shift = 1'b1;
        end
      end
      STOP: begin
        if (rx) begin
          next = IDLE;
          done = 1'b1;
        end else if (!rx) begin
          next = IDLE;
          err  = 1'b1;
        end
      end
      default: next = IDLE;
    endcase
  end

  // Moore output: busy is a function of the state alone.
  always_comb begin
    busy = 1'b0;
    unique case (state)
      START:   busy = 1'b1;
      DATA:    busy = 1'b1;
      STOP:    busy = 1'b1;
      default: busy = 1'b0;
    endcase
  end

endmodule

The reset style is stated at the top: asynchronous, active low. The Mealy outputs are driven in the next-state block, where the arrow they belong to is chosen: each gets its default at the top, and the branch that takes the arrow sets it. busy belongs to the states alone, so it has an output block of its own. No output is driven from two blocks. The FSM viewer draws a state machine of your own from its code, its Mealy outputs on its arrows as here.

The two arrows out of DATA are an if and an else if, in the order of their priorities, which the comments on those lines record. The order is the whole of the priority: it is what makes the loop on tick the second choice.

Synthesis result

Yosys's generic synthesis turns uart_rx.sv into 21 cells, 2 of them flip-flops. The cells are Yosys's own gate library, not an FPGA's or a standard-cell library's: the count measures the logic, not the area of any chip.

The code gives state a 2-bit encoding, and these numbers keep it. Left to its fsm pass, Yosys re-encodes it one-hot: 4 flip-flops, 22 cells in all.

Lint by Verilator 5.052, the testbench by Icarus Verilog 13.0, synthesis by Yosys 0.66.

Icarus replayed this page's three scenarios on this code, and all 1,062 values the waveform draws match.

Pitfalls

A Mealy output lasts as long as its condition. done and err are high for the one period the machine spends in STOP, before the edge that returns to IDLE. Whatever consumes them has to sample them at that edge, on the same clock.

Reading the stop bit a bit late. STOP is entered on the tick in the middle of the stop bit, and it reads rx at its next edge rather than waiting for another tick. Waiting would read the line a whole bit period later, which on a busy line is the next frame's start bit: a false framing error, and the start bit gone.

Priority by position. Swap the two DATA lines and the arrow to STOP can never be taken: whenever tick && last is true, tick is true too, and the loop is tried first. The machine shifts on every tick and never reaches STOP. Nothing in the syntax says the order matters.

rx is asynchronous. In the figure it changes between edges and is sampled at the next one. In silicon, a line from outside the chip goes through a synchronizer before a state machine reads it.