Sequential logic

Introduction

Sequential logic is an important building block for finite state machines used in all digital circuitry. They are essential in understanding of how computer memory works, how data is stored and read in a computer. In this article we’ll look at the components of sequential logic.

Bistable circuit

A bistable circuit is the fundamental element of computer memory. It can be depicted with two inverters connected in a loop such that the input of one inverter, I1, is the output of another one, I2. And the input of I2 is the output of I1. As you can see, the bistable circuit doesn’t have an input but two outputs, Q and Q̅. The latter symbol, Q̅ (pronounced “Q-bar”) is the opposite of Q; if Q is 0, Q̅ is 1 and vice versa.

The bistable circuit can also be shown as a pair of cross-coupled inverters to display its symmetry:

Let’s analyze this simple circuit. Q can be either 0 or 1. First, we’ll look at the case of Q being 0:

- Q is the input to I2 which means that I2 receives the value of 0. I2 inverts FALSE value to TRUE value producing the value of 1 on Q̅. This value is passed as an input to I1 which produces the opposite value on Q. So, the output Q becomes 0 as expected. So, we began with Q being 0 in the beginning of the loop, and we ended up with confirming Q remaining 0 at the end of the loop. We can say that the case of Q = 0 is stable.

Now let’s look at the case Q = 1:

- I2 receives TRUE input and produces FALSE output on Q̅. Another inverter, I1 receives the value of FALSE (or 1) and produces TRUE output on Q. So, Q becomes 1 as expected. We began with Q being 1 in the beginning of the loop, and we ended up with confirming Q remaining 1 at the end of the loop. We can say that the case of Q = 1 is stable.

Since the system has two stable states, when Q equals 0 and Q equals 1, this circuit is known as bistable. Can the bistable circuit be used to store information? Of course, it can. When the value of Q is 1, it remains 1 forever. Likewise, Q will remain 0 forever if it begins with the value 0. So, the history of Q can predict the future behavior of its own. Though the bistable circuit can store a bit of information, it isn’t practical because there’s no input to the system, and the user cannot control the state with this design.

SR Latch

The next circuit we’ll look at is called SR Latch.

SR latch can be described as a pair of cross-coupled NOR gates. The two inputs, S and R, stand for Set and Reset. Like the bistable circuit, SR Latch has two outputs Q and Q̅. Two inputs S and R can have the value of 0 and 1. This means that to understand the circuit, we have to look at 4 cases:

- S = 0, R = 1. The NOR gate produces 0 if at least one of the inputs is 1. Therefore, N1 produces FALSE output on Q. This value is passed as an input to N2. Since both inputs (Q and S) to N2 are 0, it produces TRUE output on Q̅.

- S = 1, R = 0. N2 produces FALSE output on Q̅ because one of its inputs, S, equals 1. This FALSE output is passed as an input to N1 which has already received another FALSE input, R. This means that N1 produces TRUE output on Q.

- S = 1, R = 1. Both N1 and N2 receive at least one TRUE input. So, they produce FALSE output on Q1 and Q2 respectively.

- S = 0, R = 0. This is an interesting case. N1 receives two inputs, Q̅ and R. We know that R is 0 — this is given — but we don’t know what Q̅ is. Maybe first looking at N2 will clear the issue. N2 receives two inputs, Q and S. We know that S is 0 — this is given — but we don’t know what Q is. So, are we stuck? We can proceed by looking at two subcases, Q = 0 and Q = 1.

· If Q = 0, then both inputs of N2 are 0 which means that it produces TRUE output on Q̅. Now, N1 receives TRUE input from Q̅, thus producing FALSE output on Q which aligns with that Q equals 0.

· If Q = 1, then N2 produces FALSE output on Q̅. Now, N1 receives FALSE input from Q̅, thus producing TRUE output on Q which aligns with that Q equals 1.

We see that when S = 0 and R = 0, Q remains 0 if it has the value of 0. And if it has the value of 1, it remains 1, if both inputs S and R equal to 0. If we call the previous values of Q and Q̅ respectively, Qold and Q̅old, then we can confirm that Q and Q̅ will remember their previous values. Thus, SR Latch has memory. Below you can find the truth table of SR latch. It summarizes all four cases we described above.

SR Latch truth table

Input

Now we can understand what Set and Reset mean. When S is 1, i.e., when we set a bit, we make Q 1 as well — we make it TRUE (this is the case when S = 1 and R = 0). When R is 1, we reset a bit, i.e., we make it FALSE. So, Q becomes 0 when S = 0 and R = 1. When both inputs are zero, the state of the circuit is called “latched”, i.e., it remembers its previous value and “latches” on it. The last case — when both inputs are 1 — is invalid because Q and Q̅ both equal to 0. But we know that they have to have inverse relationship.

SR Latch is drawn with a box with two inputs and two outputs:

D Latch

SR Latch is useful because it “remembers” a bit of information — it can provide information about which of the inputs was TRUE (or ON or 1 or voltage) last time. But as Petzold notes in “Code” — which is, by the way, an amazing book on how computers really work — a circuit remembering if a signal was 0 or 1 at particular point in time can be much more useful.

What D latch does is exactly this. It has two elements: CLK which control when the output changes, and D which represents the next state, i.e., what the output will change to. What they essentially do is the following. When CLK is 0, the input D has no effect on the output. When CLK is 1, the value of D will be passed to Q, so the circuit will reflect D. Then, if CLK goes back to being 0. This time the circuit will remember the value of D and Q will remain as Qold.

Analyzing the following circuit will explain how D latch works.

You can see that when CLK is off, i.e., it has the value of 0, both AND gates will produce FALSE output, regardless of the value of D. So, Q will remember its previous value, Qold. When CLK is 1, we have two subcases involving D: D = 1 and D = 0. In the former case, i.e., CLK = 1 and D = 1, the lower AND gate will produce TRUE output on S and FALSE output on R, which means Q and Q̅ will produce 1 and 0 respectively (you can refer to the truth table of SR latch above to check the case of S = 1 and R = 0). When CLK = 1 and D = 0, the upper AND gate will produce TRUE output on R and FALSE output on S, which means Q and Q̅ will produce 0 and 1 respectively. Again, you can look at the truth table of SR latch above to verify that when S = 0 and R = 1, Q will be 0 and Q̅ thus will be 1.

Below is the truth table of D latch.

X means “don’t care.” When the value of CLK equals to 0, the circuit its previous state regardless of the value of D. When the value of CLK is 1, the circuit will reflect the value of D. We say that in this case the latch is transparent because the data at D flows through to Q. Conversely, when CLK is 0, the latch is opaque because the new data is blocked to pass through to Q. The output Q retains its previous value.

D Latch is typically described with the following drawing:

D latch is useful in not only controlling when the output changes, but also avoiding the invalid case of S = R = 1 which we saw when looking at SR latch.

D flip-flop

D latch is a level-triggered device which means that whenever Clock changes its value from 0 to 1, the value of Data input will be reflected in the output. If CLK remains 1, change in Data input will be passed to Q. In some cases, we need a circuit which only changes its output when the value of Clock input changes from 0 to 1. This type of circuit is called edge-triggered. An edge trigger changes the value of output only when the value of CLK changes from 0 to 1. The change from 0 to 1 is also called a positive transition. Likewise, a negative transition is the change from 1 to 0.

The following scheme describes D flip-flop (DFF).

Here DFF is built from two D latches linked with the node N1. The first latch, L1 is the master or leader latch; the second latch, L2, is the slave or follower latch. When CLK is 0, the master latch becomes transparent, and the slave latch goes opaque. So, the value of D input will be passed to N1. If CLK = 1, the slave latch becomes transparent, and the master latch is opaque. The value of N1 goes through to Q. But since the master is opaque in this case, N1 is not linked to D. What this means is that the value of D at the time before there was a positive transition in the CLK input — i.e., the value of Clock went from 0 to -1 — will propagate through to output Q when CLK rises from low to high (this is another way of saying that the input goes from to 1).

To summarize, a D flip-flop will reflect the value of Data input whenever there is a rising edge, i.e., the value of CLK goes from 0 to 1.

D flip-flop can be described by the following diagram as well. Here a DFF is built of two stages of SR latches. Personally, I think this is a better way of explaining how a DFF works.

We see that both stages are controlled by the CLK input. The first stage functions like a D latch with the only difference being that it reflects the Data input when the Clock is 0. This is because the Clock is inverted in the first stage. The output of the first stage is the input to the second stage which is only stored when the Clock is 1. The overall idea of the circuit is that the Data input is reflected in the output Q when the Clock goes from 0 to 1. The concept of Data flip-flop is very important in building memory so we will repeat how a DFF works. The Data input is stored when CLK is edge triggered from 0 to 1.