1. Home
2. Academy
3. State Machines from Zero
4. Volume 09

9.1 Datapath plus controller (FSMD)

Big designs split into a datapath that does the work and a controller that decides, each cycle, what the datapath should do. The datapath reports back with status signals.

Two halves with two jobs

The lift in Volume 08 already had two halves. Registers held the floor and the calls; a state machine decided what to do next. This split is so common that it has a name: an FSMD, a finite state machine with a datapath.

• The datapath holds and changes data: registers, adders, comparators, counters.
• The controller is a state machine. Each cycle, it sends the datapath control signals - "load", "subtract", "clear".
• The datapath answers with status signals - "equal", "zero", "greater" - which the controller uses to choose its next state.

An example: the greatest common divisor

The greatest common divisor (GCD) of two numbers is the largest number that divides both. The GCD of 21 and 6 is 3. There is a very old method that needs only subtraction:

1. While the two numbers are different, take the smaller one away from the larger.
2. When they are equal, that number is the GCD.

For 21 and 6: 21 - 6 = 15, then 15 - 6 = 9, then 9 - 6 = 3. Now 3 and 6: 6 - 3 = 3. Both are 3, so the GCD is 3.

In hardware, the datapath needs two registers, A and B, a subtractor, and a comparator. The controller needs three states: IDLE waits for start and loads the numbers, CALC repeats the subtraction, and DONE reports the result for one cycle.

The code: two halves, side by side

module gcd (
  input  wire       clk, rst, start,
  input  wire [7:0] a_in, b_in,
  output wire [7:0] result,
  output wire       done
);
  // ------------------------------------------------ controller
  localparam [1:0] IDLE = 2'd0, CALC = 2'd1, DONE = 2'd2;
  reg  [1:0] state, next_state;
  reg        ld, sub_a, sub_b;             // control signals, to the datapath
  wire       eq, gt;                       // status signals, from the datapath

  always @(posedge clk)
    if (rst) state <= IDLE;
    else     state <= next_state;

  always @(*) begin
    next_state = state; ld = 1'b0; sub_a = 1'b0; sub_b = 1'b0;
    case (state)
      IDLE: if (start) begin ld = 1'b1; next_state = CALC; end
      CALC: if (eq)      next_state = DONE;
            else if (gt) sub_a = 1'b1;     // a > b: a = a - b
            else         sub_b = 1'b1;     // a < b: b = b - a
      DONE: next_state = IDLE;
      default: next_state = IDLE;
    endcase
  end

  // ------------------------------------------------ datapath
  reg [7:0] a, b;
  always @(posedge clk)
    if (ld) begin a <= a_in; b <= b_in; end
    else begin
      if (sub_a) a <= a - b;
      if (sub_b) b <= b - a;
    end

  assign eq     = (a == b);
  assign gt     = (a > b);
  assign result = a;
  assign done   = (state == DONE);
endmodule

The controller never touches a number, and the datapath never makes a decision. Each half is small enough to check on its own.

9.2 ASM charts

An ASM chart draws a state machine like a flowchart: a box for each state, diamonds for decisions, and ovals for the actions that happen on the way.

Why another kind of drawing?

A state diagram is perfect for a pure controller. But in an FSMD, the interesting part is often what happens to the data - "subtract b from a" - and a state diagram has no good place to write it. An ASM chart (algorithmic state machine chart) looks like a flowchart, so it reads like the method itself.

The three shapes

An action written like a ← a − b is a register transfer: at the next clock edge, register a takes the value a − b.

How to read it

Start at IDLE. Follow the arrow into the start diamond. If start is 0, the path loops back to IDLE: the machine waits. If start is 1, the path passes through the oval "ld = 1" - load the numbers - and arrives at CALC.

From CALC, the path meets the diamond a = b. If they are equal, it goes to DONE. If not, it asks a > b, and takes the matching oval - a ← a − b or b ← b − a - before returning to CALC.

The one rule of ASM charts

So the chart in Figure 9.3 says this. In each CALC cycle, look at a and b, do one subtraction, and stay in CALC. If they are equal, go to DONE instead. That is exactly what the Verilog does.

9.3 Hierarchical and nested FSMs

When one step hides a whole sequence of smaller steps, give it its own small state machine. The big machine starts it and waits for it to finish, like a program calling a function.

Machines that call machines

In Volume 08 you built a UART transmitter. It sends one byte. Now suppose a design must send a whole message - "HELLO". You could add five times as many states to the transmitter. Or you can leave the transmitter alone, and add a small parent machine that uses it, one character at a time. This is a hierarchical state machine.

The conversation between them is always the same:

1. The parent sets up the data, and raises a one-cycle start signal - here, send.
2. The child does its many-cycle job, and shows busy = 1 while it works.
3. The parent waits until the child is no longer busy, then moves on.

module send_msg (
  input  wire clk, rst, go,
  output wire tx                               // the serial line
);
  localparam [1:0] IDLE = 2'd0, LOAD = 2'd1, WAIT = 2'd2;
  reg  [1:0] state;
  reg  [2:0] idx;                              // which character, 0 to 4
  reg        send;                             // start pulse to the child
  wire       busy;                             // from the child
  reg  [7:0] ch;

  always @(*)                                  // the message, one character at a time
    case (idx)
      3'd0: ch = "H";  3'd1: ch = "E";  3'd2: ch = "L";  3'd3: ch = "L";
      default: ch = "O";
    endcase

  uart_tx #(.CPB(434)) child (.clk(clk), .rst(rst), .send(send), .data(ch),
                              .tx(tx), .busy(busy));

  always @(posedge clk) begin
    send <= 1'b0;
    if (rst) begin state <= IDLE; idx <= 3'd0; end
    else case (state)
      IDLE: if (go) begin idx <= 3'd0; state <= LOAD; end
      LOAD: begin send <= 1'b1; state <= WAIT; end            // start the child
      WAIT: if (!send && !busy) begin                          // the child has finished
              if (idx == 3'd4) state <= IDLE;
              else begin idx <= idx + 1; state <= LOAD; end
            end
    endcase
  end
endmodule

The line uart_tx #(.CPB(434)) child (...) places a copy of the Volume 08 transmitter inside this module and names it child. The transmitter is not changed at all.

The trap in WAIT

Look again at the WAIT condition: !send && !busy. Why check send?

In the first cycle of WAIT, send has only just become 1. The child sees it at the next edge, so in that first cycle the child is still idle, and busy is still 0. A parent that checked only !busy would think the child had already finished, and hurry on to the next character - while the child is only now starting on this one. A careful model of the design shows the result: the line carries "HLO", with every second character lost. The !send makes the parent wait one cycle, until busy has had time to rise.

Why not one big machine?

You could merge the parent and the child into one machine. But the states multiply: every parent state combined with every child state. A parent with 3 states and a child with 4 gives up to 12 states - and real designs have many more. This fast growth is called state explosion. Separate machines stay small, can each be tested alone, and can be reused - the same uart_tx could serve ten different parents.

9.4 Request/acknowledge handshakes

When two machines pass work between them, they use a handshake. One says "here is something", the other says "I have taken it", and neither moves on until the other has answered.

The four-phase handshake

The most robust handshake has four steps, and ends with both signals back at 0. It is called the four-phase handshake:

1. The sender puts the data out and raises req (request).
2. The receiver sees req, takes the data, and raises ack (acknowledge).
3. The sender sees ack, and lowers req.
4. The receiver sees req fall, and lowers ack. Both are at 0 again, ready for the next transfer.

Two rules make it safe. The sender must not change the data while req is 1. And the receiver takes the data exactly once per request - when req rises - not on every cycle that req is high.

// ---------- sender: IDLE -> REQ -> DROP -> IDLE
always @(posedge clk)
  if (rst) begin s_state <= IDLE; req <= 1'b0; end
  else case (s_state)
    IDLE: if (have_word) begin data <= word; req <= 1'b1; s_state <= REQ; end
    REQ:  if (ack)  begin req <= 1'b0; s_state <= DROP; end    // taken: release
    DROP: if (!ack) s_state <= IDLE;                          // handshake complete
  endcase

// ---------- receiver: WAIT -> GOT -> WAIT
always @(posedge clk)
  if (rst) begin r_state <= WAIT; ack <= 1'b0; end
  else case (r_state)
    WAIT: if (req)  begin got <= data; ack <= 1'b1; r_state <= GOT; end  // take it once
    GOT:  if (!req) begin ack <= 1'b0; r_state <= WAIT; end
  endcase

A four-phase transfer takes several cycles: here, five cycles per word. The price buys safety - each side waits for the other at every step, whatever their speeds.

The two-phase handshake

A two-phase handshake saves time by counting changes instead of levels. Every change of req - up or down - is a new request. Every change of ack answers it. When req and ack are equal, the channel is free.

It is twice as fast, but the logic must remember the last value of each signal and compare - a little harder to get right.

Valid and ready: the same-clock handshake

When both machines share one clock, there is an even faster pattern. The sender raises valid when it has data; the receiver raises ready when it can take data. The data moves in every cycle in which both are 1 - one word per cycle at full speed. This is the valid/ready handshake, used by AXI-Stream and countless internal buses. It is covered in depth in the VALID/READY handshake in the FPGA course.

9.5 FSMs across two clocks

When two machines run on different clocks, every signal passing between them must be synchronised, and a group of bits must travel with a handshake - never bit by bit.

Two clocks, one problem

A chip often has several clocks: a fast one for the processor, a slower one for a peripheral, one for each external link. All the flip-flops on one clock form a clock domain. A signal that travels from one domain to another is a clock domain crossing, or CDC.

The trouble is timing. The receiving flip-flops do not know when the signal will change, so sooner or later it changes right at their clock edge. A flip-flop caught like that may hover between 0 and 1 for a moment before it settles. This is metastability. If that half-value spreads into a state machine, the machine can jump to a wrong state - even an illegal one.

Rule 1: synchronise every single-bit signal

The cure for one bit is the two-flip-flop synchroniser from Volume 07. The first flip-flop may go metastable, but it has a whole clock cycle to settle before the second one reads it. The chance that it is still undecided a cycle later is astronomically small. The full story, with the numbers, is in metastability and MTBF in the Verilog course.

Rule 2: never synchronise a group of bits one by one

Suppose a state machine sends its 3-bit state to another domain, through three synchronisers. If the state changes from 011 to 100, all three bits change. Each synchroniser may catch its bit a cycle earlier or later than the others. So for one cycle the receiver may see 111, 000 or any other mix - a value that was never sent.

There are two safe ways to pass a group of bits:

• Gray code, when the value only ever steps to a neighbour - like a counter. Only one bit changes per step, so the receiver sees either the old value or the new one, never a mix. This is the reason for the Gray encoding in Volume 05.
• A handshake, for any data. The data travels on plain wires, held steady; only the request and the acknowledge - single bits - pass through synchronisers.

The handshake across two clocks

This is the four-phase handshake of sub-module 9.4, with one synchroniser on req and another on ack:

Each side's state machine is exactly the one from sub-module 9.4. The only change is that each side reads the other's signal through its synchroniser - so each step of the handshake takes a couple of extra cycles. That is the cost of crossing safely.

What you learned

• An FSMD splits a design into a datapath that works on data and a controller that decides; control signals go one way, status signals come back.
• An ASM chart draws a machine as a flowchart: state boxes, decision diamonds and action ovals, with one ASM block per clock cycle.
• A parent machine can start a child machine and wait for it - but must give it a cycle to start before checking busy.
• Merging machines multiplies their states; separate machines stay small and reusable.
• Four-phase handshakes are the safest, two-phase handshakes are faster, and valid/ready moves a word every cycle on one clock.
• Between clock domains, synchronise single bits, and move groups of bits with Gray code or a handshake - never bit by bit.

Key words from this volume

Every word below has a plain-English entry in the glossary.

• FSMD
• Datapath
• Control signal
• Status signal
• ASM chart
• Register transfer
• Hierarchical state machine
• State explosion
• Four-phase handshake
• Two-phase handshake
• Valid/ready handshake
• Clock domain
• Clock domain crossing (CDC)
• Metastability
• Synchroniser

Practice

CALC: if (eq || zero) next_state = DONE;     // equal, or nothing to do
      else if (gt)    sub_a = 1'b1;
      else            sub_b = 1'b1;

Interview corner

Next, Volume 10 asks a different question: is your machine as small as it could be? It shows how to find states that do the same job, and merge them.