Logic Gates, Part 2: Memory and State Machines

In part 1 every circuit computed its output from its inputs alone: change the inputs, and the output follows. That is enough to add numbers, but not to count, to remember what you typed or to run a program step by step. For that, a circuit needs memory. This part shows where memory comes from, how a clock keeps it in order, and how memory and logic together become state machines. As before, every step comes with something to click.

Circuits that remember

Logic blocks come in two kinds, depending on whether they contain memory. In a combinational block the output depends only on the current input. In a block with memory, the outputs can also depend on the value stored in it, the state of the block [1]. Such blocks are called sequential: what they output depends on the whole sequence of inputs so far.

George H. Mealy put it precisely in 1955: in his model, the present output and the next state of a circuit are determined by the present input and the present state. A circuit with a single internal state is combinational, any other one is sequential [2, p. 1050]. Everything in part 1 was combinational. Test your intuition:

The SR latch

Memory needs a loop: a signal that feeds back into the gate that produced it. The simplest memory element connects two NOR gates in a ring, so that the output of each one is an input of the other. This is the SR latch, with S for set and R for reset [1].

S = 1 sets the output Q to 1, R = 1 resets it to 0. The interesting part is what happens when both are 0 again: nothing pushes the latch, and the two gates hold each other in place. The latch remembers which input was the last one. S and R must not be 1 at the same time: then both outputs are 0, and if both inputs are released at the same moment, which gate wins is a race.

Clock, latch and flip-flop

An SR latch reacts at any moment. In a larger circuit that is a problem: signals arrive at slightly different times, and until an adder has settled its outputs can be wrong, as the ripple-carry adder in part 1 shows. Synchronous circuits therefore have a clock, a signal that switches between 0 and 1 at a steady rate, and let their memory elements change only in step with it. Mealy already named the clock that supplies timing pulses as a characteristic of synchronous circuits [2, p. 1047].

Patterson and Hennessy distinguish two clocked memory elements [1]. A D latch stores its data input D: while the clock is 1, its output follows D, and while the clock is 0, it holds its value. A D flip-flop changes only at a clock edge, here the moment the clock rises from 0 to 1; at all other times D can change as it likes. A flip-flop can be built from two latches, one of them open while the clock is 0 and the other while it is 1.

This is why processors are built from flip-flops: at every clock edge all of them take their new values at the same moment, and between two edges the combinational logic has time to settle.

Registers and counters

A row of flip-flops sharing one clock is a register: it holds a number from one clock edge to the next. Connect a register to an adder that adds 1, feed the sum back into the register, and you have a counter. The adder is combinational and already shows the next value; the register is sequential and waits for the clock edge.

State machines

The counter is already a small finite-state machine: a state stored in flip-flops, and combinational logic that computes the next state from it. In general such a machine has three parts: next-state logic, which computes the next state from the state and the inputs; a state register, which stores the state; and output logic, which computes the outputs [1].

The types of machine differ in what the output logic may look at. In Edward F. Moore's machines, the present output depends only on the present state [3, p. 129]. In Mealy's model it depends on the present state and the present input [2, p. 1050]. And if there is no output logic at all, because the state bits themselves are the output, the machine is called a Medvedev machine (German: Medwedew-Automat), after Yu. T. Medvedev, who published on finite automata in 1956 [4].

Moore and Mealy

Both kinds can solve the same problems. Take a simple task: light a lamp once the input has been 1 in two clock cycles in a row. A Moore machine needs three states, “no 1 yet”, “one 1” and “two or more 1s”, and the lamp belongs to the last one. A Mealy machine manages with two states, “last input 0” and “last input 1”, because its output can look at the present input: it lights the lamp when another 1 arrives in “last input 1”.

Mealy drew his machines as state diagrams: circles for the states and arrows for the transitions, each arrow labeled with its input and output [2, p. 1052]. Below, set the input x, watch the two lamps, then clock. The Mealy output reacts as soon as x changes, the Moore output only after the next clock edge. Mealy machines therefore react sooner; Moore outputs change only with the clock, which makes them steadier.

Medvedev: the state is the output

In a Medvedev machine there is nothing between the state register and the outputs. That works whenever the outputs themselves can serve as the codes of the states. A traffic light is a good example: with one flip-flop per lamp, the state “red and yellow” is simply the code 110, and the lamps hang directly on the flip-flops. Only the next-state logic is left to design. The light below follows the German sequence: red, red and yellow, green, yellow.

Where to go from here

Registers, a clock and state machines turn the ALU from part 1 into a processor: registers hold the operands, and the control unit, which decides step by step what the processor does, is itself a state machine. How such machines are designed and timed is covered in the appendix “The Basics of Logic Design” of Patterson and Hennessy's Computer Organization and Design [1]. And how to make all of it fast, with pipelines, caches and parallel units, is the subject of Hennessy and Patterson's Computer Architecture: A Quantitative Approach [5].

Back to part 1: from a switch to an ALU.

References

1. D. A. Patterson and J. L. Hennessy, Computer Organization and Design RISC-V Edition: The Hardware/Software Interface, 2nd ed. Morgan Kaufmann (Elsevier), 2020. ISBN 978-0-12-820331-6. Appendix A: “The Basics of Logic Design.” Publisher's page
2. G. H. Mealy, “A Method for Synthesizing Sequential Circuits,” The Bell System Technical Journal, vol. 34, no. 5, pp. 1045–1079, 1955. doi:10.1002/j.1538-7305.1955.tb03788.x. Free scan at the Internet Archive
3. E. F. Moore, “Gedanken-Experiments on Sequential Machines,” in C. E. Shannon and J. McCarthy (eds.), Automata Studies (Annals of Mathematics Studies 34). Princeton University Press, 1956, pp. 129–153. doi:10.1515/9781400882618-006
4. Yu. T. Medvedev, “О классе событий, допускающих представление в конечном автомате” [On a class of events representable in a finite automaton], in Avtomaty. Moscow: Izdatel'stvo Inostrannoj Literatury, 1956, pp. 385–401. English translation in E. F. Moore (ed.), Sequential Machines: Selected Papers. Addison-Wesley, 1964. Review in The Journal of Symbolic Logic
5. J. L. Hennessy and D. A. Patterson, Computer Architecture: A Quantitative Approach, 6th ed. Morgan Kaufmann (Elsevier), 2017. ISBN 978-0-12-811905-1. Publisher's page