Flip-Flops and the Art of Computer Memory

It’s a poor sort of memory that only works backwards.
~The White Queen to Alice
(Lewis Carroll, Through the Looking Glass)

Keyboard Flip-Flop
It may surprise you to learn that flip-flops are an integral part of computing. Just… not the kind of flip-flop you think. (source)

This is the fifth part in my multi-part series on how computers work. Computers are thinking machines, and the first four parts of my series have been on how we teach computers to think.  But all of this logic, electronic or otherwise, is useless unless our computers can remember what they did. After logicking something out, a computer needs to remember the result of all that logicking!

In this post, I describe how to use the logic gates described in part four to electronically implement computer memory.

This post depends heavily on my last few posts, so if you haven’t read them, you might want to.

Still here? Okay. Let’s get to it!

 How Computer Memory Should Work

Before we talk about exactly how we implement computer memory, let’s talk about what we want out of it.

In the world of Boolean logic, there is only true and false. So all we need to do is record whether the result of a calculation was either true or false. As we learned in part three, we represent true and false (called truth values) using the voltage in an electric circuit. If the voltage at the output is above +5 volts, the output is true. If it’s below +5 volts, the output is false.

So, to record whether an output was true or false, we need to make a circuit whose output can be toggled between + 5 volts and, say, 0 volts.

Logic Gate, Logic Gate

To implement this, we’ll use the logic gates we discussed in part four. Specifically, we need an electronic logic gate that implements the nor operation discussed in part two. A nor B, which is the same as not (A or B), is true if and only if neither A nor B is true. We could use other logic gates, but this one will do nicely.

As a reminder, let’s write out the truth table for the logical operations or and nor. That way, we’ll be ready to use them when we need them. Given a pair of inputs, A and B, the truth table tells us what the output will be. Each row corresponds to a given pair of inputs. The right two columns give the outputs for or and nor = not or, respectively. Here’s the table:

truth table for OR and NOR
The truth table for the logical operations “A OR B” and “A NOR B.” Each row corresponds to a different set of inputs A and B; the last two columns correspond to the appropriate outputs.

Let’s introduce a circuit symbol for the nor gate. This will be helpful when we actually draw a diagram of how to construct computer memory. Here’s the symbol we’ll use:

a nor gate
A symbol for a NOR gate. The two terminals on the left correspond to the inputs. The terminal on the right corresponds to the outputs.

Crossing the Streams

Okay, so how do we make computer memory out of this? Well, we take two nor gates, and we cross the streams…

Ghostbusters crossing the streams
Don’t cross the streams. You know, unless you have to. (Source)

We define two input variables, which we call S (standing for set) and R (standing for reset), and two output variables, which we call Q and not Q. The reasons for this peculiar naming scheme will become clear in a moment. Then we wire the output of each of our nor gates so that it feeds back into the other nor gate as an input, as shown below.

An SR latch
One kind of computer memory constructed by cross-wiring two NOR gates. We have two input variables, called S and R, and two output variables, called Q and not Q.

For reasons that will eventually become clear, this circuit is called an SR-Latch, and it’s part of a class of circuits called flip-flops. Now let’s see if we can figure out what’s going on. Assume that both S and R are false for now. And let’s assume that Q is true and not Q is (as the name suggests) false, as shown below. 

SR latch Q state
An SR latch such that the Q state is true, the NOT Q state is false, and both S and R are false. This state is self-perpetuating. Blue indicates FALSE. Red indicates TRUE.

Is this consistent with the truth table we listed above?

  • S nor Q is false, because if Q is true, then (obviously) both S and Q aren’t false. Since we gave the name “not Q” to the output of S nor Q, this means not Q must be false. That’s what we expected. Good.
  • R nor (not Q) is true, because R is false and not Q is false. The output of R nor (not Q) is the same as Q, so Q must be true. Also what we expected!

Okay, so what does this mean? It means that if we start our circuit in this state, with R and S as false, Q as true, and not Q as false, our circuit perpetuates itself in this state. Nothing changes.

Toggle Me This, Toggle Me That

Now let’s alter the state described above a little bit. Let’s change R to true. Since R is true, this changes the output of R nor (not Q) to false. So now Q is false…and since S is still false, the output of S nor Q is now true. Now our circuit looks like this:

SR_latch_not_Q_toggle
An SR latch mid-toggle. We set R to true. Immediately, Q becomes false, which causes NOT Q to become true.

And if we wait a moment further, the cross-wiring takes effect so that both inputs to R nor (not Q) are true. This doesn’t change the output, though, as shown below.

SR_latch_not_Q_toggle_2
An SR-latch mid-toggle. After NOT Q becomes true, it feeds back into the first NOR gate. Fortunately, this doesn’t seem to affect anything.

Now we can set R to false again, and Q will stay false and not Q will stay true, as shown below.

SR_latch_not_Q
An SR-latch with Q false and NOT Q true. We got to this self-sustaining state by temporarily setting R to true.

Look familiar? This is the mirror image of the state we started with! And it’s self-sustaining, just like the initial state was. With both R and S set to false, not Q will stay true as long as we like.

Although R is false now, the circuit remembers that we set it to true before! It’s not hard to convince ourselves that if we set S to first true and then false, the circuit will revert to its original configuration. This is why the circuit is called a flip-flop. It flip-flops between the two states. Here’s a nice animation of the process I stole from Wikipedia:

SR latch animation
An animation of the flip-flop process for the NOR-gate based SR-latch we talked about. In this animation, RED signifies TRUE and BLACK signifies FALSE. (source)

This is computer memory. And similar devices are behind your CPU cache and other components inside your laptop.

A Whole World of Flip-Flops

Although it’s technically correct, generally, people don’t refer to the circuit I described as a flip-flop. The things people usually refer to as flip-flops usually only change state based on some sort of timer or clock. However, the idea is essentially the same.

In general, clocks are something I didn’t touch on. Real computers use a clock to sync the flipping of memory with the computations they perform using the logic gates I talked about earlier. (Clocks can also be generated using logic gates. This is the speed of your CPU clock.) I figured I wouldn’t go into that here because it’s a bit too technical and, in my opinion, not necessary for understanding.

Next Time

We now have enough tools to understand the essentials of how a computer works. It performs logical operations using logic gates, and it remembers what it did using flip-flops. Next time, we’ll take a break from electronic computers to discuss some other ways you can make a computer. Did you know you can make a computer with gears? With ropes and pulleys? With dominoes? With card games? Find out more next time.

Further Reading

Flip-flops are the domain of electrical engineers, so there’s not much non-technical material on them. Here’s what I could find.

  • A flip-flop is a special case of a class of circuits called “bi-stable vibrators.” If you like, you can learn about them on their Wikipedia page.
  • Here’s a fairly technical video lecture on flip-flops.
  • This set of lecture notes is at about the same level as my post, but it goes into substantially more depth.
  • If you want to understand clocked flip-flops, you might start here.

Related Reading

If you liked this article, you might enjoy reading my previous entries on computing:

  • In this article, I describe the basics of Boolean logic, starting with truth tables.
  • In this article, I describe how to make composite logical statements using Boolean logic.
  • In this article, I introduce the triode vacuum tube and describe how it works.
  • In this article, I show how to use triodes to make logic gates.

If you like explanations of how hardware works, here are some similar articles:

One thought on “Flip-Flops and the Art of Computer Memory

Comments are closed.