Chapter 10. Circuits: Memory
For a computer to be able to work interactively with a human, it must have some form of memory. In working toward this goal, we'll begin by examining a particular type of circuit called a latch.
10.1. Latches
It would be nice to have some circuit that remembers a single bit, with a single output representing this bit, and two inputs allowing us to alter the circuit's value when we choose.
We'll call the two inputs set and data. When set is 0, the circuit should do nothing except continue emitting what it remembers. But when set becomes 1, the circuit should begin remembering data's value instead.
set data memory 0 0 unchanged 0 1 unchanged 1 0 0 1 1 1
Such a circuit is called a D latch. It's called a latch because it holds a value. The D designation refers to the particular way the set and data inputs work. (In particular, D stands for Data.) In this subsection we'll see how to build such a latch.
10.1.1. SR latch
We begin by considering the following little circuit.
The OR gates with circles after them are NOR gates They're a combination of an OR gate with a NOT gate attached: Given the inputs x and y, a NOR gate outputs the value x + y.
This circuit — with its output Q going into the upper NOR gate, whose output loops back to the gate computing Q — is peculiar: We haven't seen a circuit with such loops before. This loop is what will give rise to our memory.
So what does this circuit do? We can fill out the following table for what Q this circuit will compute given various combinations of R, S, and the current value of Q. We include the current value of Q (labeled ``old Q'') among the input columns of the table because Q's value loops back as an input to one of the gates.
S R old Q new Q 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 ignore 1 1 1 ignore
To see how we arrive at this table, let's take the first row as an example, when S and R are both 0, and when Q is currently 0. In this case, the lower NOR gate must be emitting a 0, since that is what Q is. This 0, and the S input of 0, are the inputs to the upper NOR gate, so the upper NOR gate emits a 1. Tracing this around, this 1 is an input to the lower NOR gate, along with the R input of 1, so the lower NOR gate emits a 0. We can continue tracing this around, and the output of the lower NOR gate will continue being 0; thus, we write 0 for the new Q value in the first row.
Now let's say we change the S input to be 1 — this moves us to the fifth row of the table, when S is 1, R is 0, and Q is 0. Now look at the upper NOR gate: It receives the S input of 1 and the Q input of 0, so the upper gate emits 0. But this changes the output of the lower NOR gate: With the 0 input from the upper NOR gate, and the R input of 0, the lower NOR gate emits 1. Now this 1 goes up to the upper NOR gate, and, with the S input of 1, the NOR gate continues to output 0. Now the circuit is again in a stable state, but with Q now being 1. Thus a 1 is in the last column for the fifth row. We can continue this sort of analysis to complete the other five rows labeled in the above truth table.
As for the last two rows, we're simply going to avoid them. We'll assume nobody will ever set both R and S inputs to 1, since such inputs won't be useful to us.
Examining the other rows of the table, we notice that if both R and S are 0 (the first two rows), then Q remains unchanged; that is, it remembers a bit. If S is 0 and R is 1 (the third and fourth rows), then Q becomes 0 regardless of its previous value. And if S is 1 and R is 0 (the fifth and sixth rows), then Q becomes 1 regardless of its previous value. We can tabulate this as follows.
S R memory 0 0 unchanged 0 1 0 1 0 1 1 1 ignore
This circuit is called an SR latch. Again, it's a latch because it holds a bit. The S and R refer to the traditional names of the inputs. The names R and S derive from the fact that when S is 1, the remembered bit is Set to 1, and when R is 1, the remembered bit is Reset to 0.
10.1.2. D latch
With an SR latch in hand, we can build the D latch we set out to design, which you can recall has inputs of set and data. What we'll do is translate the various combinations of set and data to the required S and R inputs corresponding to desired behavior; from this, we can build a circuit incorporating an SR latch.
set data desired Q S R 0 0 old Q 0 0 0 1 old Q 0 0 1 0 0 0 1 1 1 1 1 0
For the first row of this table, we had already decided that we want the new Q to remain the same when set is 0. We've seen that the way to accomplish this using an SR latch is to set both S and R to 0. Thus, you see 0 and 0 in the last two columns of the first row. Deriving the other rows proceeds similarly.
Based on this table, we can determine that S should be set ⋅ data, while R should be set ⋅ data. We use this to build a circuit giving our desired D latch behavior.
10.2. Flip-flops
The D latch gives us the ability to remember a bit, but in practice it's more convenient to have components whose values change only at the instant that the set input changes to 1. This reduces confusion about what happens when data changes if set is still 1. Such a circuit — whose value changes only at the instant that its set input changing values — is called a flip-flop. For these circuits, we will call the set input the clock.
10.2.1. D flip-flop
Consider the following circuit, called a D flip-flop.
Notice what this circuit does to compute the set input to the D latch: It computes ck ⋅ ck. (The ck name here stands for clock.) This is weird: According to the law A ⋅ A = 0 from Boolean algebra, the AND gate would always output 0. What's the point of having a latch if its set input is always 0?
This apparent pointlessness is explained by considering the fact that gates are physical devices, and they take time to respond to inputs. To understand how this circuit really works, it's useful to look at the following illustration, called a timing diagram.
The horizontal axis represents time. The upper line of the diagram (labeled ck) indicates that ck begins at 0, then changes to 1, then back to 0, then back to 1. The first change to 1 occurs at instant a in time (diagrammed with a vertical dashed line with a label below it). Since electricity is a physical quantity, voltage cannot change instantaneously, so in this diagram each change in value is diagrammed with a slanted line.
Let's look at what happens at time a: The outputs of the NOT and AND gates do not immediately change when ck changes, because they take time to sense the change and react. The beginning of the NOT gate's reaction appears in the diagram at time b. More surprisingly, the AND gate reacts at time b, too: You can see from the diagram that between a and b, the AND gate sees a 1 from ck and a 1 from ck. The AND gate's behavior is to output a 1 in this circumstance, so at time b it begins emitting a 1. By time c, it detects that the NOT gate is now at 0, and so the AND gate's output changes back to 0. Thus, the AND gate outputs 1 for a brief instant whenever ck changes from 0 to 1.
In the flip-flop circuit, then, when ck changes from 0 to 1, the set input to the D latch instantaneously becomes 1, and the D latch will remember whatever data holds at that instant. Then its set input switches back to 0 again, so that further changes to data do not influence the latch (until, that is, ck changes from 0 to 1 in its next cycle).
In circuit diagrams, we represent the D flip-flop as follows.
The triangle is traditional way of denoting an input for which the component acts only when the input changes from 0 to 1. Notice that this component also outputs Q. The flip-flop outputs this value because it is easy to compute. (The upper NOR gate in the underlying SR latch generates it.) It's often convenient to take advantage of this additional output in circuits.
10.2.2. JK flip-flop
There are several types of flip-flops which behave in slightly different ways. The JK flip-flop is one of the more popular variations. It has three inputs called J, K, and the clock.
Its behavior is indicated by the following table.
J K new Q 0 0 old Q 0 1 0 1 0 1 1 1 old Q
Note the similarity of this table to the SR latch's table. The difference is in the final row: When both inputs to an SR latch are 1, the behavior is indeterminate; with the JK flip-flop, when both inputs are 1, the flip-flop's state toggles. Another major difference from the SR latch is not pictured in the table: As a flip-flop, its behavior changes only at the instant that its clock input changes from 0 to 1.
10.2.3. Putting it together: A counter
Suppose we want a circuit that counts how many times the user has given it a 1 bit as an input. Such a simple circuit would be useful, for example, in a turnstile to count people entering. To do this, we'll use four flip-flops, to remember the current count in binary. (Our counter will only count up to 15, the largest four-bit number, and then it will reset to 0. If we want to count higher, we would need more flip-flops.) And we'll include a four-bit adder to compute the next value for these four flip-flops. Figure 10.1 contains a diagram of our circuit.
Figure 10.1: A four-bit counter
To get a feel for how the circuit of Figure 10.1 works, suppose the in input is 0, and all the D flip-flops hold 0. Then these outputs would be fed into the four-bit adder, which also takes its other input of 0001(2), and would output 0000(2) + 0001(2) = 00001(2). The lower four bits of this output are fed into the D flip-flops' D inputs, but the flip-flops' values don't change, because their clock inputs (wired to in) are all 0. (The upper bit of the adder's output is ignored — in the circuit, we acknowledge this by representing that the output is grounded.)
When the in input changes to 1 again, then the flip-flops' values will suddenly change their remembered values to 1, and the circuit's outputs will reflect this. Also, the four-bit adder would now receive 0001 for its upper four-bit input, so that the adder would output 0001(2) + 0001(2) = 00010(2). This goes into the flip-flops, but the flip-flops values won't change again, because flip-flops change their value only at the instant that in becomes 1, and that time has long past before 0010(2) reaches them.
This last point, by the way, illustrates the point of using flip-flops instead of latches. Suppose we used latches instead. Because the set input would still be 1 at this point, the latches would begin remembering 0010(2). And this would go through the adder, and the 0011(2) would go into the latches. This would go through the adder, and 0100(2) would go into the latches. The circuit would count incredibly fast until finally set would go to 0. We wouldn't be able to predict where it stops. [In fact, since the gates aren't all identically fast, and the wires aren't all identically long, the changes in latches' values would be much more erratic.] Using flip-flops, however, the count goes up only once each time the input goes to 1.
10.3. Registers
A register is a simple device for remembering a set of bits of memory. The following is a diagram of a four-bit register.
The outputs on the right continually emit the current contents of the register. The set input, represented with a small triangle on the component's lower edge, tells the register when to alter its value. When this input changes from 0 to 1, the register changes its remembered bits to the values existing on the input bits on the register's left side.
Building a register is a straightforward task: It's just a matter of putting several D flip-flops together, sharing the same set input, as in the below diagram of a four-bit register's internals.
10.4. Memory
A 32-byte memory appears similar to a register.
The difference between this circuit and the register is the additional five input bits on the bottom, which tell the memory which address to access. The circuit output pins on the right side give the data stored at this address of memory, while the circuit input pins on the left side give the data to be stored at this address (which is actually changed when the clock input changes from 0 to 1).
Implementing the memory is a matter of using multiplexers and demultiplexers to route the inputs and outputs to the appropriate internal flip-flops. Suppose we want to build a memory of 4 bits, which has two address bits s1 and s0, a set input, as well as an input bit in and an output bit out. We would build such a circuit using four D flip-flops.
To compute the output, we feed the flip-flops' outputs into a multiplexer, using the address bits to select which of these goes to the output. Handling the process of setting the flip-flops' values is only slightly more complicated: We route the input to the D input of all the flip-flops, and we use a demultiplexer to route the set input to the flip-flops' ck inputs. Each of the D flip-flop's ck input will be 0, except for the chosen one. This flip-flop will see its ck input change from 0 to 1 whenever set changes from 0 to 1, and so this flip-flop will change its value as it ought then. [This circuit has a bug: Suppose set were 1, and the address bits change. Then the newly selected D flip-flop would see its clock input change from 0 to 1, and so it would also reset. A simple way of addressing this is to place the circuit computing set ⋅ set (this would typically be in each individual D flip-flop) before the demultiplexer; this allows replacing the D flip-flops with D latches instead.]
To inflate this circuit into 32 bits, we simply need larger multiplexers and demultiplexers (along with more flip-flops). To change this memory to hold 32 bytes instead of 32 bits, we would duplicate this circuit into eight copies, sharing the same address bits and set bit but using different input and output bits. Such a circuit is quite large; for our HYMN implementation, it constitutes the largest portion of the required gates.
In real life, memory circuits aren't implemented this way, except for small caches of memory that exist on the CPU. In fact, actual memory circuits don't use logic gates for holding data: A common technique is to use an electrical capacitor, which can hold an electrical charge for a brief moment. Since capacitors quickly lose their charge, this necessitates frequent recharging, which leads to much electrical complexity, but it requires much less circuit space, so that memory can be cheaper. The details of this are beyond the scope of this book.
Computing Systems Organization is licensed under a Creative Commons Attribution-Share Alike 3.0 License.
Based on a work at http://www.cburch.com/cs/230/cso/.