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

13.1 Registered vs combinational outputs

An output that comes through gates after the state register arrives later in the clock cycle. An output that comes straight from a flip-flop is ready just after the clock edge, and leaves the next block almost the whole cycle.

Where the time goes

Nothing in a circuit is instant. After a rising clock edge, a flip-flop takes a moment to show its new value - its clock-to-Q delay. Then every gate that value passes through adds its own propagation delay. And the flip-flop at the end of the path needs its input steady for the setup time before the next edge. All of this must fit inside one clock period. How the period is shared out is the timing budget.

Now think about a state machine's output, and the block that receives it. Whatever time the output takes to appear is time taken away from that block.

Three kinds of output, three budgets:

• A registered output comes straight from a flip-flop. After the small clock-to-Q delay, it is ready, and the next block has almost the whole cycle.
• A decoded output - a Moore output made by gates from the state bits - arrives a little later: clock-to-Q, then the output logic.
• A Mealy output can be the worst. It depends on an input, and that input may itself come from another block's logic, arriving late in the cycle. The two delays add up.

Making an output registered

You met the method in Volume 04: decide the output from next_state, and let a flip-flop hold it.

// decoded: vend comes out of gates, after the state register
assign vend = (state == VEND);

// registered: vend comes straight out of a flip-flop, decided one cycle early
always @(posedge clk)
  if (rst) vend_r <= 1'b0;
  else     vend_r <= (next_state == VEND);

Both change at the same clock edge. But vend_r comes out of a flip-flop, so it is ready sooner, and it is clean.

13.2 Glitch-free outputs

When several state bits change at one clock edge, they never change at exactly the same instant. Gates decoding them can pass through a wrong value for a moment - a glitch - unless the output comes straight from a flip-flop.

How a glitch is born

Take a machine with the output z = Q1·Q0: z is 1 only in state 11. Now let the machine step from 01 to 10. Both bits change. In a real chip, one flip-flop is always a little faster than the other. If Q1 rises before Q0 falls, then for a moment the gates see 11 - and z flickers to 1, although the machine never visited state 11. A short false pulse like this is a glitch.

When does a glitch matter?

Not always. If z only feeds flip-flops on the same clock, the glitch is over long before the next edge, and those flip-flops never see it. A glitch does harm when something reacts to z at once:

• z drives a clock, or an asynchronous reset, of another circuit
• z is read by a circuit on a different clock
• z leaves the chip and drives another device
• z counts events, as a pulse counter would

Four ways to be glitch-free

13.3 The FSM critical path

A state machine's clock speed is limited by its loop: from the state register, through the next-state logic, and back into the state register - all within one clock period.

The loop

Every state machine has a loop at its heart. The state leaves the register, passes through the next-state logic, and must arrive back at the register's input in time for the next edge. So the clock period must be at least:

The fastest clock that satisfies this is the machine's maximum clock frequency, or fmax. The slowest path in a design is its critical path, and in a state machine it is usually this loop.

What makes the loop slow

The first two terms are fixed by the flip-flops. The one you control is the next-state logic. It grows slow when:

• many state bits must be decoded - large binary-coded machines
• long priority chains of if ... else if ... else if, where each test waits for the one before
• wide comparisons in the loop, such as timer == 1000000
• arithmetic feeds a decision, as the GCD's comparator feeds its controller in Volume 09

A worked example

Suppose each logic level - one gate on the path - takes 0.5 ns, and the clock-to-Q delay and the setup time are 0.5 ns each.

The same machine, twice as fast, only because the next-state logic is shallower. This is the real reason for the one-hot advice in Volume 05. The full set of timing equations is in the timing volume of the Verilog course.

13.4 Look-ahead and pipelined control

When a decision is too slow to make in time, make it one cycle earlier and store the answer in a flip-flop. The machine then uses a ready-made result instead of waiting for slow logic.

Deciding one cycle early

Look at a timer that ends a state when it reaches 999,999. The obvious code compares every cycle:

// slow: a 20-bit compare sits in the state machine's loop
wire done = (count == 20'd999_999);

// fast: compare one cycle early, and keep the answer in a flip-flop
reg done_r;
always @(posedge clk)
  if (rst) done_r <= 1'b0;
  else     done_r <= (count == 20'd999_998);   // 1 exactly while count is 999_999

If the count goes up by one each cycle, then one cycle after it equals 999,998, it equals 999,999. So done_r, registered from the earlier compare, is 1 in exactly the same cycle as done. But done_r comes straight from a flip-flop: the 20-bit compare has moved out of the loop into a cycle of its own. This trick is called look-ahead.

The registered outputs of Volume 04 - decided from next_state - are the same idea applied to the outputs: look one cycle ahead, and store the answer.

Control that travels with the data

In a pipeline, a piece of data moves through several stages, one stage per cycle, with registers between them. The controller must tell each stage what to do when the data reaches it, not when the data starts. So the control signals are delayed through their own chain of registers, one per stage, and travel alongside the data.

13.5 FSMs on FPGA vs ASIC

The best way to build a state machine depends on the target. An FPGA has flip-flops to spare and counts logic in levels of look-up tables. On an ASIC, every flip-flop costs area and power.

On an FPGA

An FPGA's logic is built from look-up tables, or LUTs: tiny memories that can hold any function of their inputs - typically up to six. Each LUT sits beside one or more flip-flops. The architecture is explained in the FPGA course.

What this means for state machines:

• Flip-flops are almost free. They are there whether you use them or not, so one-hot costs little.
• Speed is counted in LUT levels. A next-state function of six inputs or fewer fits in one LUT. One-hot keeps most next-state functions that small.
• The tools help. FPGA synthesis tools usually re-encode state machines as one-hot by themselves (Volume 05).
• Flip-flops start known. After an FPGA is loaded, its flip-flops hold known starting values. Some designs rely on this instead of a reset - a habit to use with care, because a reset may still be needed later.

On an ASIC

An ASIC is built from standard cells - gates and flip-flops from the chip maker's library, as the ASIC course shows. There:

• A flip-flop is several times the size of a simple gate, and it uses power on every clock edge. For small machines, binary or Gray encoding usually wins.
• Power matters. An idle machine's clock can be switched off - clock gating - so its flip-flops stop using power.
• Testing is built in. Chips are tested after they are made by linking the flip-flops into long shift registers, called scan chains. Every state register takes part, so the design must not depend on tricks that scan would break.

Side by side

What you learned

• Every path must fit in the clock period: clock-to-Q, then logic, then the next flip-flop's setup time.
• Registered outputs are ready just after the edge and never glitch; decoded and Mealy outputs arrive later.
• Glitches come from state bits changing at slightly different moments; they matter when something reacts at once.
• A state machine's fmax is set by its loop: clock-to-Q + next-state logic + setup. Shallower logic means a faster clock.
• Look-ahead makes a decision one cycle early and stores it in a flip-flop, moving slow logic out of the loop.
• FPGAs favour one-hot and count LUT levels; ASICs pay for every flip-flop, and use clock gating and scan.

Key words from this volume

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

• Clock-to-Q delay
• Propagation delay
• Setup time
• Timing budget
• Registered output
• Glitch
• Maximum clock frequency (fmax)
• Critical path
• Logic level
• Look-ahead
• Pipeline
• Look-up table (LUT)
• Standard cell
• Clock gating
• Scan chain

Practice

always @(posedge clk)
  if (rst)             count <= 0;
  else if (load)       count <= load_value;
  else if (count != 0) count <= count - 1;

always @(posedge clk)
  if (rst)       zero_r <= 1'b1;
  else if (load) zero_r <= (load_value == 0);
  else           zero_r <= (count <= 1);

Interview corner

Next, Volume 14 gathers the whole course onto one page, with solved design problems, concept questions, spot-the-bug drills and flashcards, ready for exams and interviews.