Flip-Flops Are Easy

This post is written for my DigiPen?classmates.

First let me clarify some of the notations used in the diagrams in this post:
A* means “NOT A”, or “A inverted/toggled”.
AB means “A AND B”.
A + B means “A OR B”.

So, for instance, (A + B)(C + D) means “(A OR B) AND (C OR D)”.

RS Flip-Flops

Remember in CS 100/101, we’ve learned this fundamental type of flip-flip, the RS flip-flop.



And here’s the truth table of the flip-flip.

D Flip-Flops

When attached to an extra stage of gates, the RS flip-flop becomes a D flip-flop. Instead of feeding in A (Set) and B (Reset), now we feed in D (Data) and E (Enable). In other words, when E is zero, then the output remains the last value of D it “remembers”, or “latched”. When E is one, the output “follows” whatever value is fed into D. It’s easy to verify that.

Now, the problem is, how on earth can we come up with this extra stage of gates? It seems Prof. Duba just came up with it and drew it on the whiteboard without even explaining how he did it. Well, it’s actually very simple. There is a systematic way of putting gates together so they form a circuit that satisfies any given truth table.

First let’s look at the simplest case: a truth table with two variables, A and B, and an output, where only one combination of A and B generates an output of one.

Here’s how to determine the logic representation: the output is always of the form AB; however, if the output of one corresponds to an input variable of zero, invert that variable. In this case, an output of one corresponds to A = 0 and B = 1, so the logic representation of the output in terms of the inputs is (A*)B. Again, this is easy to verify. Below is what this circuit looks like.

Now let’s take a look at another truth table.

This time the output corresponds to A = 0 and B = 0, so the output is (A*)(B*). Below is what the corresponding circuit is like.

So, how about this truth table?

Looks like there are two combinations of inputs that result in an output of one. Actually, this table is the previous two tables OR-ed together. So, the output in terms of inputs is the previous two representations OR-ed together: (A*)(B*) + (A*)B. So is the corresponding circuit (The As and Bs from both circuits are merged together. This circuit is in effect no more than ORing together the outputs of the two circuits.):

Do you get the idea of how to systematically deduct the logic representation given whatever truth table? All you have to do is OR together each individual AND-term obtained from tables with a single output of one. In fact, this type of logic representation is called “Sum of Products (SOP)”. There is another type of representation called “Products of Sum (POS)”, but that is another story.

Okay, back to the D flip-flop. We want the flip-flip to hold (A = 0, B = 0) the output value whenever E is zero. And we want the output to follow D if E is one; that is, if D is one, then A = 1, and B = 0; if D is zero, then A = 0, and B = 1.

Here’s the truth table of D and E as variables and A as output.

Here’s the truth table of A as output.

And here’s the truth table of B as output.

From the first table we get this circuit.

And this is the circuit for the second table.

Now by merging these two circuits and the RS flip-flip together, we get what Duba got!

Mystery solved 🙂

[Edit]

I think I’ll elaborate more on the intermediary steps between ORing together these two circuits:

into this:

First you start off by simply ORing the outputs of the two circuits together.

Then extend both As and merge them together. Note the split occurs after the inverter, so that the two AND gates are still fed with A*.

Next, merge the B inputs together. Notice that the split occurs before the interver, so that two different B inputs can be fed to two different AND gates.

Finally, by rearranging the wires, we can get the circuit obtained earlier. Actually, the last circuit (the one above) was cleaner…I have no idea how the hell I ended up with this circuit.

About Allen Chou

Physics / Graphics / Procedural Animation / Visuals
This entry was posted in Programming. Bookmark the permalink.

Leave a Reply