4.5 Why circuits need state

Why this matters

Every circuit so far computed its outputs from its inputs and nothing else, so the same inputs always gave the same outputs. A stopwatch, a score display, a traffic light and a processor all need to remember what has already happened. This section shows why an adder fed back to itself, with no register in the loop, cannot count, and which part you add to a circuit to give it a memory that steps under the control of a clock.

Learning goals

Explain why wiring an adder's output back to its own input, with no register, does not count.
Say what a clock edge is and what a register does at one.
Trace the signals of the perpetual timer through a reset and several clock cycles.
Predict the value the timer holds right after reset, and explain why it is not 0.
Decide whether a described behavior needs state.

Intuition first

Intuition

In a program, a loop that counts is easy to write, because a variable keeps its value from one pass to the next. total = total + 1 works because total is a place in memory, and the statement runs once per pass of the loop. A combinational circuit has neither of those. A wire carries whatever its gate computes from its inputs right now, so there is no place that keeps total between passes, and nothing that says when one pass ends and the next begins.

To count, a circuit needs two things. It needs a part that holds a value, and it needs a signal that says when to replace the held value with a new one. The first is a register. The second is a clock. Together they give hardware its equivalent of a loop: all the logic between the register's output and its input computes the next value, and the clock says when the register takes it.

The analogy has one limit. In a program only the statement being executed is active. In a circuit all the logic is always active, and the clock decides only when the register looks at what the logic has produced.

The things that need such a memory are everywhere: a counter, a score, the position in a sequence of steps, the last value of a button, the number of coins put in a machine so far. Each is a quantity that depends on the past and not only on what the inputs are right now.

State, clocks and registers

Section 1.4 defined sequential logic (Definition 1.4.2) as circuits that contain state: stored information about earlier inputs that can affect the outputs. In this chapter that stored information lives in registers. Two more terms are needed before the main example.

Definition 4.5.1(clock and rising edge).

A clock is a signal that alternates between 0 and 1 at a steady rate. The moment it changes from 0 to 1 is a rising edge, and the time from one rising edge to the next is one clock cycle. A synchronous circuit does its steps at rising edges.

Definition 4.5.2(register (first look)).

A register is a part that holds a number. Its output shows the number it holds. At a rising clock edge it copies its input into itself, and between rising edges it ignores its input and keeps the number. Section 4.7 builds a register from flip-flops and describes it precisely.

A circuit's state is whatever its registers hold at the moment. This is the same idea as in Section 1.4: what the registers hold is the stored information about earlier inputs. Two circuits with the same inputs can give different outputs if their states differ, which is exactly the property a table of the inputs cannot describe. A register does not have to feed back into the logic that computes its own next value. A row of registers that only pass a value along, such as the shift register of Section 4.8, holds state and is sequential too.

Combinational gates connected without feedback cannot remember earlier inputs, and a clocked register supplies controlled storage. Gates can also be wired to hold a bit without a clock edge. Section 2.7 named that kind of circuit a latch: it follows its input while an enable is on and holds its last value while the enable is off. A register is different, because it looks at its input only at a clock edge, which gives one controlled step per clock cycle. This book builds its memory from clocked registers and never uses a latch on purpose. A latch that appears by accident in SystemVerilog is a bug, and Section 5.5 shows how one arises.

The perpetual timer in three tries

Example 4.5.1(a counter that never stops).

The goal is a 4-bit number sout that is 1 after a reset and then goes up by 1 on every clock cycle, forever, wrapping from 15 to 0. The ingredients are an adder, the constant 1 and, when we need it, a way to say "start over". Each try below fixes a problem of the one before. This is the perpetual timer of Lecture 4, and the three tries are the lecture's three, with the reset multiplexer where the lecture puts it.

First try. Feed the output of an adder back into its own input and add 1 to it.

Illustration a block diagram that explains an idea; its behavior is not checked

This drawing contains a loop of gates with no register in it. It is drawn as it is and not checked; a real circuit must not have such a loop.

Figure 4.5.1. The first try: an adder that adds 1 to its own output. This drawing is an illustration: the loop has no register in it, so it is drawn as it is and no tool checks its behavior.

The wire says that sout equals sout plus 1. No 4-bit number does: adding 1 to any of the sixteen values gives a different value, because 15 plus 1 wraps to 0, which is not 15. So the circuit has no value it can settle on. Beyond that, nothing in the drawing says what the first value should be, and nothing says when the next step happens.

Second try. Add a reset. A multiplexer in front of the adder passes the fed-back value while reset is 0 and the constant 0 while reset is 1.

Illustration a block diagram that explains an idea; its behavior is not checked

This drawing contains a loop of gates with no register in it. It is drawn as it is and not checked; a real circuit must not have such a loop.

Figure 4.5.2. The second try: a multiplexer in front of the adder puts 0 into it while reset is 1. The wire from the adder's output back to the multiplexer is again a loop with no register in it, so this drawing is an illustration too.

While reset is 1 the adder sees 0, so sout is 1, and that is consistent. That answers the question of the starting value. But when reset falls, we are back to the first try: sout must equal sout plus 1, and no value does. Whatever the circuit does then depends on how fast its gates are, and not on anything we can control. We still have no way to say "one step now".

Third try. Put a register on the feedback path. The adder's output goes to the register's input, and the register's output is what the multiplexer sees.

Figure 4.5.3. The third try: the register q sits on the feedback path, clocked by clk. This drawing is checked against the module below.

Now there is no loop of gates: the loop passes through the register, which breaks it in time. During a clock cycle the register's output q is a fixed number, the multiplexer and adder compute sout from it, and sout is just waiting at the register's input. At the next rising edge the register copies sout, so q takes a new value, and the cycle repeats. The register keeps the new value from going around the loop until the clock says so, and each rising edge is one pass of the loop. The reset multiplexer works as in the second try: while reset is 1 the adder sees 0.

In SystemVerilog

Here is the third try as a module. Section 4.8 explains the always_ff block in detail. For now, read it as a register: at each rising edge of clk, q takes the value of sout.

// A perpetual timer: a register on the feedback path of an adder. A mux in front of the adder sends 0 into it while reset is 1.
module timer(input logic clk, reset, output logic [3:0] sout, q);
  logic [3:0] b;

  // The adder's input: the register's value, or 0 while reset is 1.
  assign b = reset ? 4'd0 : q;

  // The adder: one more than its input. This is also what the register will capture.
  assign sout = b + 4'd1;

  // The register: it holds sout until the next rising edge.
  always_ff @(posedge clk)
    q <= sout;
endmodule

The assign statements are the multiplexer and the adder from the drawing, and b is the multiplexer's output. The only line that holds anything from one cycle to the next is the always_ff block. A test for it follows the testbench pattern that Section 4.8 describes, and every // expect: comment in it is checked against the simulation of the module (in a testbench of your own, such a comment is only a note to yourself: the simulator does not check it).

Here is a short primer for the clocked code in the rest of the chapter, with Section 4.8 giving the detail. always_ff @(posedge clk) starts a block that describes flip-flops: what it assigns is stored at each rising edge of clk. Inside it the assignment to use is <=: all the right-hand sides are read at the edge, and then all the left-hand sides change together. In most registers of this book an if (reset) inside the block gives the register its starting value. The timer above does it differently, through the multiplexer in front of the adder, as the lecture draws it. A clocked testbench makes its own clock and waits for edges with @(posedge clk): each line sets the inputs, with <=, and then waits for the edge that ends that cycle.

What the timer does after reset

At the first rising edge reset is 1. What does q hold just after that edge? 0, because reset clears the register. 1, because reset makes the adder see 0, and the register captures 0 plus 1. It is still unknown, because reset only works from the second edge on.

The waveform comes from simulating the module with a testbench that holds reset high for the first edge, lets the timer run, and later resets it again. b is the multiplexer's output and sout is the adder's. The lane for b is labeled dut.b, because b is a signal inside the module dut.

Time in ps; one column is 50 ps.

Figure 4.5.4. The timer from reset. The values are in decimal.

Read Figure 4.5.4 from left to right. Before the first rising edge, reset is 1, b is 0 and sout is already 1, because gates respond without waiting for a clock. But q is hatched: the register has not captured anything yet, so its value is unknown. At the first rising edge, the register captures sout, which is 1, and q becomes 1. At that same instant the testbench makes reset fall, so b becomes the new q, 1, and sout becomes 2. From then on, each rising edge captures the sout that the cycle before it produced: q is 2, 3, 4, 5 and 6 at the next five edges, and b is always q while reset is 0, with sout one above it.

So after reset q is 4'd1, and never 0. This is easy to take for a mistake and "fix" by moving the multiplexer, but the circuit is right: reset decides what the adder is given, and the register stores the sum. Exercise 4.5.3 asks for a version that is 0 after reset. The reset multiplexer in front of the adder is the lecture's way of drawing the timer, and it is a synchronous reset in the sense of Section 4.7, since it acts through a register at an edge. It is not the pattern to copy for a design of your own. The usual pattern is the if (reset) of Section 4.7 and 4.8, which loads a chosen value straight into the register.

Time in ps; one column is 50 ps.

Figure 4.5.5. The second reset in the same run. reset rises at the edge at 650, and the register captures 1 at the edge at 750.

The second figure shows the middle of the run. reset rises at the instant of the rising edge at 650. The register does not react at that edge: it captures the value sout had before the edge, 7, which the adder computed while reset was still 0. (The testbench writes reset with <=, and a simulator counts that as a change just after the edge, as Section 4.7 explains.) So q becomes 7, as in a normal count. Right after the edge b drops to 0 and sout to 1, because reset is now 1. At the next edge, at 750, the register captures that 1, and q becomes 1. reset falls at that same edge, so the count resumes: 2, 3 and 4 at the next three edges. In no cycle does q change in the middle of a clock cycle, even though reset, b and sout change at the rising edge or just after it. Only rising edges change q.

Pitfalls

Common pitfall

Expecting q to be 0 after reset in this timer. Reset forces the adder's input to 0, so the register captures 1.
Thinking that wiring an adder's output back to its own input counts. Without a register, that loop has no value it can settle on, and nothing says when a step happens.
Expecting a register's output to move whenever its input moves. It changes only at a rising edge, and between edges it keeps its value whatever its input does.
Drawing q changing the moment reset rises. A synchronous reset takes effect at the next rising edge, where the register captures what the adder produced under reset.
Reading the hatched part of a waveform as 0. Before the first edge the register's value is unknown, and the simulator draws that as hatching.

Check your understanding

Take the quiz (3 questions)

Why does the first try, an adder fed from its own output, not work as a timer? No number equals itself plus 1, so the loop has no value to settle on. An adder cannot add the constant 1. It counts, but too fast to see.

In the second reset of the timer, reset rises at the instant of a rising edge and q is 7 at that edge. When does q next change, and to what? Immediately, to 0. At the next rising edge, to 1. At the next rising edge, to 0.

At the edge where reset rises, the register captures 7, the value sout had just before the edge. During the next cycle the multiplexer gives the adder 0, so sout is 1, and the following edge captures it. q never changes between edges.

Which of these systems needs state? A decoder that turns a 4-bit code into the segments of a digit. A circuit that says whether at least two of three switches are up. A lamp that changes from off to on or on to off each time a button is pressed.

Exercises

Exercise 4.5.1

The figure shows the clock and reset for a stretch of the timer's run. Just before the first rising edge shown, at 650, q is 6. In this simulation an input that changes at an edge is drawn changing at that edge, and the simulator counts it as changing just after it, so the register sees the value the input had before the edge (Section 4.7). Work out b, sout and q in every cycle.

Time in ps; one column is 50 ps.

Figure 4.5.6. The question: only the clock and reset.

Hint

b is 0 whenever reset is 1 and is q otherwise. sout is always b plus 1, and q changes only at a rising edge, to the value sout had just before it.

Solution

Take the edges one at a time, using the value each signal had just before the edge.

Before 650: reset is 0, so b is q = 6 and sout is 7.
Edge at 650: reset was 0, so the register captures sout = 7, and q is 7 from here. reset rises at this edge, so right after it b is 0 and sout is 1.
Edge at 750: reset was 1, so the register captures sout = 1, and q is 1. reset falls at this edge, so b is 1 and sout is 2.
Edge at 850: the register captures 2. b is 2 and sout is 3.
Edge at 950: the register captures 3. b is 3 and sout is 4.
Edge at 1050: the register captures 4. b is 4 and sout is 5.

Time in ps; one column is 50 ps.

Figure 4.5.7. The answer, from the simulation of the timer.

Tags: Warm-upWaveformsSequential logic

Exercise 4.5.2

In the second try of the timer, reset is 1 and then falls. What is sout while reset is 1, and what is the problem once it falls? Why does the third try not have that problem?

Hint

Write down the equation that the loop imposes on sout in each case, and ask whether any 4-bit value satisfies it.

Solution

While reset is 1 the multiplexer gives the adder 0, so sout is 0 plus 1, which is 1. That is a consistent value, so the circuit has something to settle on.

When reset falls, the multiplexer passes sout back to the adder, and the loop requires sout to be sout plus 1. No value satisfies that, since adding 1 always changes a 4-bit number. The circuit has no steady output, and what it does depends on the gate delays.

In the third try the multiplexer sees the register's output q, which is a fixed number during a clock cycle, so sout is q plus 1, an ordinary calculation with one answer. The loop is broken in time: the new sout reaches q only at the next rising edge.

Tags: StandardSequential logic

Exercise 4.5.3

Change the timer so that q is 0, and not 1, right after the edge that sees reset at 1, and then counts 1, 2, 3 and so on. Draw the block diagram.

Hint

Where in the loop does the 0 have to be inserted for the register to capture 0? In the original, the multiplexer is in front of the adder.

Solution

For the register to capture 0 at a reset edge, the 0 has to be at the register's input. So the multiplexer moves to the other side of the adder: the adder computes q plus 1 all the time, and the multiplexer chooses between that sum and the constant 0, with reset as its select. Its output goes to the register.

Figure 4.5.8. The timer with the reset multiplexer between the adder and the register. This drawing is checked against the module below.

// A timer whose register is 0 after reset: the reset mux sits between the adder and the register, so the register captures 0 while reset is 1.
module timer_zero(input logic clk, reset, output logic [3:0] q);
  logic [3:0] sum;

  assign sum = q + 4'd1;

  always_ff @(posedge clk)
    if (reset) q <= 4'd0;
    else q <= sum;
endmodule

The simulation shows the difference. Compare q with the one in Figure 4.5.4: after the edge that sees reset at 1 it is 0, and the first count after reset is 1, one cycle later.

Time in ps; one column is 50 ps.

Figure 4.5.9. The modified timer, with its own testbench. sum is the adder's output.

Tags: StandardRegisters and countersSequential logic

Exercise 4.5.4

For each system, say whether its output can be computed from its current inputs alone, or whether it needs state, and say what it would have to remember.

A circuit that shows a decimal digit, 0 to 9, on a seven-segment display.
A circuit that lights a lamp when a safe's door has been opened three times in a row without the code.
A circuit that outputs the sum of two 8-bit numbers.
A circuit that outputs 1 on the clock cycle after its input was 1.

Hint

Ask whether two moments with the same input values could need different outputs. If so, something about the past makes the difference.

Solution

No state. The segments are a function of the digit.
State. The same input, a wrong attempt, gives the output "off" for the first two attempts and "on" for the third, so the circuit must remember how many wrong attempts in a row it has seen so far.
No state. The sum is a function of the two numbers.
State. The input at the previous cycle is gone by the time the output is needed, so the circuit must remember that one bit.

Tags: Warm-upSequential logic