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

7.1 Every counter is a state machine

A counter is a state machine whose states are numbers, and whose main arrow from each state goes to the next number.

A counter, drawn as a state machine

A counter is a register that steps through numbers in order. Take a 2-bit counter with an enable input, en. When en = 1 it adds 1 at each clock edge; when en = 0 it holds its value. After 3 it wraps back to 0. Draw it the way you draw any state machine, and you get Figure 7.1.

Nothing about it is special. It has states, an input, and arrows. Its state register holds the count, and its next-state logic is an adder that works out "count plus 1".

Why nobody draws big counters

An 8-bit counter has 256 states. A 32-bit counter has over four billion. Nobody draws those diagrams. Instead, one line of Verilog describes every arrow at once:

reg [7:0] count;
always @(posedge clk)
  if (rst)     count <= 8'd0;
  else if (en) count <= count + 1;    // the next state is "this number plus 1"

When count reaches 255, adding 1 gives 256, which does not fit in 8 bits. The top bit is dropped, and the count wraps round to 0 - exactly the arrow from the last state back to the first.

Why this view is useful

Thinking of a counter as a state machine pays off when you combine the two. In sub-module 7.3, a small state machine and a counter will work together as one bigger machine. Its full memory is the named state plus the count - together called its extended state. You get the power of thousands of states while drawing only three.

7.2 Mod-N, up/down, ring and Johnson counters

Counters come in several shapes - mod-N, up/down, ring and Johnson - and each is a small change to the next-state rule.

Mod-N counters

A mod-N counter counts from 0 to N - 1 and then returns to 0. A clock that shows seconds needs a mod-60 counter; a decimal digit needs a mod-10 counter. When N is not a power of two, you must write the wrap-around yourself:

reg [3:0] digit;                          // 4 bits hold 0..15; we use 0..9
always @(posedge clk)
  if (rst)              digit <= 4'd0;
  else if (digit == 9)  digit <= 4'd0;    // the arrow from 9 back to 0
  else                  digit <= digit + 1;

Four bits can hold 16 values, so this counter has six unused codes, 10 to 15. If a glitch ever put it there, it would count on to 15 and wrap to 0 - so it recovers by itself. That is worth checking for every counter you design, as Volume 11 will show.

Up/down counters

An up/down counter has an input that chooses the direction:

always @(posedge clk)
  if (rst)     digit <= 4'd0;
  else if (up) digit <= (digit == 9) ? 4'd0 : digit + 1;    // 9 wraps to 0
  else         digit <= (digit == 0) ? 4'd9 : digit - 1;    // 0 wraps to 9

As a state diagram, every state now has two arrows out: one to the next number and one to the one before.

Ring counters

A ring counter is a shift register whose last bit feeds back into its first, with a single 1 travelling round and round. With four flip-flops it goes 0001, 0010, 0100, 1000, and back to 0001. It is exactly one-hot encoding from Volume 05, used as a counter: four flip-flops, four states, and no logic at all to decode a state.

reg [3:0] ring;
always @(posedge clk)
  if (rst) ring <= 4'b0001;                 // exactly one hot bit to start
  else     ring <= {ring[2:0], ring[3]};    // rotate: the top bit comes round to the bottom

Johnson counters

A Johnson counter is the same shift register with one inverter in the feedback: it shifts in the opposite of the top bit. You met its code in Volume 05. With four flip-flops it steps through eight states, changing one bit at a time.

reg [3:0] john;
always @(posedge clk)
  if (rst) john <= 4'b0000;
  else     john <= {john[2:0], ~john[3]};   // shift in the opposite of the top bit

Figure 7.2 shows both after reset. The ring counter's single 1 climbs up the bits like a staircase.

7.3 Timers and timeouts inside an FSM

When a state must last many clock cycles, do not add many states. Add a counter: the state machine loads it, and waits until it runs out.

The problem with time

A real traffic light shows green for, say, 30 seconds. With a 10 MHz clock, that is 300 million clock cycles. Drawing 300 million states is out of the question. Yet the machine must still know how long it has been green.

The answer: a timer beside the state machine

Split the job in two:

• A small state machine decides what to do: GREEN, YELLOW or RED.
• A timer - a counter - measures how long.

When the machine enters a state, it loads the timer with that state's time. Each cycle, the timer counts down by one. When it reaches zero, it raises done, and the machine moves on. This pattern - load on entry, count down, move on done - appears in almost every real controller.

module traffic_timer (
  input  wire clk, rst,
  output wire red, yellow, green
);
  localparam [1:0] GREEN = 2'd0, YELLOW = 2'd1, RED = 2'd2;
  localparam [3:0] T_GREEN = 4'd3, T_YELLOW = 4'd1, T_RED = 4'd2;  // cycles minus 1
  reg  [1:0] state, next_state;
  reg  [3:0] timer;
  wire done = (timer == 4'd0);

  always @(posedge clk)
    if (rst) begin
      state <= GREEN;
      timer <= T_GREEN;
    end else begin
      state <= next_state;
      if (next_state != state)                      // entering a new state:
        timer <= (next_state == GREEN)  ? T_GREEN  :  //   load its time
                 (next_state == YELLOW) ? T_YELLOW : T_RED;
      else if (!done)
        timer <= timer - 1;                         // otherwise, count down
    end

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

  assign green  = (state == GREEN);
  assign yellow = (state == YELLOW);
  assign red    = (state == RED);
endmodule

The times here are tiny, so you can follow them in Figure 7.3. For a real light you would only change the numbers - and the width of the timer.

Each state lasts one cycle longer than the value loaded, because the timer spends a cycle at every value from the loaded number down to 0. That is why the code loads "cycles minus 1".

Timeouts

A timer can also guard against waiting for ever. Suppose a machine asks another block for data and waits for a reply. If that block is broken, the reply never comes, and the machine hangs. With a timeout, the machine loads a timer when it starts waiting. If the reply arrives first, all is well. If the timer runs out first, the machine gives up, reports an error, and returns to a safe state. Every machine that waits for something outside itself should have a timeout.

Slow ticks from a fast clock

A timer for 30 seconds at 10 MHz needs to count to 300 million - a 29-bit counter. Often it is neater to use a prescaler: a first counter that produces one "tick" pulse every millisecond. The timer then counts ticks, not clock cycles, and 30 seconds becomes a count of 30,000.

7.4 Switch debouncing

A mechanical switch bounces - it flickers on and off for a few milliseconds when pressed. A debouncer waits until the input has been steady long enough before believing it.

What bounce looks like

Inside a push-button, two metal contacts meet. They do not meet cleanly. They hit, spring apart, hit again, and settle - all within a few milliseconds. To a circuit that samples millions of times a second, one press looks like several quick presses. This is switch bounce. Count button presses without dealing with it, and one press may count as five.

Step 1: synchronise

A button is not connected to your clock. It can change at any instant, even right at a clock edge, which can confuse a flip-flop for a moment. So the first step is always a synchroniser: two flip-flops in a row, clocked by your clock. The reasons are explained in the Verilog course, sub-module 5.2. From here on, "raw" means the button after the synchroniser.

Step 2: the debouncer state machine

A debouncer keeps a clean output, db. It changes db only when raw has been different from db for a whole waiting time. It has four states:

• LOW - db = 0, and raw agrees.
• RISE - raw has gone to 1. Wait, and see if it stays there. db is still 0.
• HIGH - db = 1, and raw agrees.
• FALL - raw has gone to 0. Wait, and see if it stays there. db is still 1.

A counter measures the waiting time, and raises done when it is over. In the diagram, r stands for raw and d for done:

module debounce #(parameter N = 3) (          // N: cycles raw must stay steady
  input  wire clk, rst, raw,                  // raw: already synchronised
  output wire db
);
  localparam [1:0] LOW = 2'd0, RISE = 2'd1, HIGH = 2'd2, FALL = 2'd3;
  reg [1:0] state;
  reg [$clog2(N)-1:0] cnt;                    // just wide enough to count to N-1
  wire done = (cnt == N - 1);

  always @(posedge clk)
    if (rst) begin state <= LOW; cnt <= 0; end
    else case (state)
      LOW:  if (raw) begin state <= RISE; cnt <= 0; end
      RISE: if (!raw)     state <= LOW;       // it was bounce
            else if (done) state <= HIGH;     // steady long enough
            else          cnt <= cnt + 1;
      HIGH: if (!raw) begin state <= FALL; cnt <= 0; end
      FALL: if (raw)      state <= HIGH;      // it was bounce
            else if (done) state <= LOW;
            else          cnt <= cnt + 1;
    endcase

  assign db = (state == HIGH) || (state == FALL);
endmodule

Two new pieces of Verilog appear here. #(parameter N = 3) makes N a parameter - a constant you can change each time you use the module. And $clog2(N) works out how many bits are needed to count up to N - 1.

Figure 7.5 shows the debouncer with N = 3, meeting a press and a release that both bounce.

In a real design, the waiting time is about 10 ms, which covers the bounce of almost any switch. With a 50 MHz clock, that is N = 500,000, and $clog2 gives the counter 19 bits.

7.5 Pulse generators and edge detectors

Edge detectors, one-shots and pulse stretchers are tiny state machines - often just a flip-flop or two - that turn levels into pulses and pulses into levels.

Edge detectors, again

You built the rising-edge detector in Volume 02: remember the input's last value in a flip-flop, and compare. Its cousins take one line each:

reg prev;
always @(posedge clk) prev <= in;          // the input one cycle ago
assign rise = in & ~prev;                  // 0 then 1
assign fall = ~in & prev;                  // 1 then 0
assign both = in ^ prev;                   // any change

Each gives a pulse exactly one cycle long - the kind of pulse a counter wants to see.

One-shots

A one-shot answers a trigger with one pulse of a chosen length, however long the trigger lasts. It is a two-state machine with a timer: IDLE waits for the trigger, and PULSE holds the output at 1 until the timer runs out. It is the traffic-light timer idea in its smallest form.

Pulse stretchers

A pulse stretcher does the opposite: it takes a pulse one cycle long and makes it last N cycles. You need one when a slower circuit must see the pulse, or when a one-cycle pulse should light an LED long enough for a person to notice.

Putting them together: counting button presses

Here is a common chain, built only from pieces in this volume. Each block has one job:

module press_counter (
  input  wire       clk, rst, button,
  output reg  [7:0] presses
);
  reg  [1:0] sync;                                  // 1. synchroniser
  always @(posedge clk) sync <= {sync[0], button};

  wire db;                                          // 2. debouncer, about 10 ms at 50 MHz
  debounce #(.N(500000)) u_db (.clk(clk), .rst(rst), .raw(sync[1]), .db(db));

  reg db_prev;                                      // 3. edge detector
  always @(posedge clk) db_prev <= db;
  wire press = db & ~db_prev;

  always @(posedge clk)                             // 4. counter
    if (rst)        presses <= 8'd0;
    else if (press) presses <= presses + 1;
endmodule

#(.N(500000)) sets the debouncer's parameter for this one use. The same debounce module, used in simulation with a small N, runs thousands of times faster.

What you learned

• A counter is a state machine whose states are numbers; count <= count + 1 describes every arrow at once.
• A mod-N counter needs its wrap-around written in; up/down counters have two arrows out of each state.
• Ring counters (n states) and Johnson counters (2n states) are shift registers fed back on themselves.
• A timer lets a state last many cycles: load on entry, count down, move on done - and load "cycles minus 1".
• Every machine that waits for the outside world needs a timeout.
• A debouncer changes its output only after the input has stayed steady for the whole waiting time.
• Synchronise, then debounce, then detect edges - in that order.

Key words from this volume

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

• Counter
• Enable
• Extended state
• Mod-N counter
• Up/down counter
• Ring counter
• Johnson counter
• Timer
• Timeout
• Prescaler
• Switch bounce
• Synchroniser
• Debouncer
• Parameter
• One-shot
• Pulse stretcher

Practice

reg [2:0] count;
always @(posedge clk)
  if (rst)                     count <= 3'd0;
  else if (en && count == 5)   count <= 3'd0;
  else if (en)                 count <= count + 1;

Interview corner

Next, Volume 08 builds six complete controllers from real products - a traffic light, a vending machine, a lift, a serial port and more - using everything so far.