HTSEFP: Digital logic - sequential logic

1RS latches¶

Given the diagram for a circuit made using a particular type of gate, determine whether or not it is an RS latch and explain why. If it is, draw out the R and S timing diagrams for a particular timing diagram of Q.

1.1General solution¶

1.1.1Truth tables for RS latches¶

First, draw out the truth table for the type of gate used, and use that to draw out the truth table for the values of R and S. As an example, using the RS latch with NAND gates, we have the following situation:

• If R is 0, $Q$ must be 1, as only two 1's can result in a 0 with a NAND gate.
  • If S is 0, $\overline Q$ must be 1.
  • If S is 1, $\overline Q$ must be 0, as both inputs to the NAND gate (S and Q) are 1.
• If R is 1:
  • If S is 0, $\overline Q$ must be 1, and so $Q$ must be 0, as both inputs to the NAND gate (S and $\overline Q$) are 1.
  • If S is 1, then nothing happens, and we stick with the previous values of $Q$ and $\overline Q$.

This results in the following truth table:

Any circuit that results in a truth table with the above outputs (in whatever order) can be considered an RS latch. If we consider the circuits described in question 3 of exercises 3²:

(a) XOR gates: No, because any combination of inputs will result in a hold.
(b) OR gates: No, because if R = S = 0, then we have a hold, but for any other combination, we have $Q = \overline Q = 1$, which is not allowed.
(c) AND gates: No, because if R = S = 1, then we have a hold, but for any other combination, we have $Q = \overline Q = 0$, which is nt allowed.

1.1.2Timing diagrams for RS latches¶

When drawing out a timing diagram, just refer to the truth table, and remember that Q can only change when the clock is 1 and the value is not being held. (It should change as soon as the clock becomes 1, if the conditions require it to change.) Make sure to hold the value initially and only do a set for the time when Q becomes 1.¹ See the

1.2Examples¶

• Exercises 3, questions 1, 2 and 3

2Gate-limited D flip-flops¶

Draw the circuit diagram of a D flip-flop using only particular types of gates. What if one of the D latches were replaced by a particular type of gate?

2.1General solution¶

2.1.1Some background on D flip-flops¶

First, a bit of background: we begin with D latches, which are essentially RS latches where instead of arbitrarily choosing Q to be 1 or 0, we set it to the value of some variable, "D" (for data). If D is 1, then we want Q to be 1, in which case we'd need to set R = 0 and S = 1. On the other hand, if D is 0, then we want Q to be 1, in which case we'd need to set R = 1 and S = 0. Consequently, $S = D$ and $R = \overline D$, so we can split D into two branches, one of which is negated and one which is not. Since we also need a clock in an RS latch, we add an input variable C that splits into two branches, each of which is ANDed with a D branch. The result of ANDing C with a negated D branch is the variable R, and the result of ANDing C with the non-negated D branch is the variable S. R and S are then fed into an RS latch as is typical.

The main problem with D latches is that simultaneous reads and writes can occur, resulting in nonsensical output. This can be solved using a mechanism called a D flip-flop, which is basically a pair of D latches with complementary C inputs. If the flip-flop is triggered by a falling edge, then the second D latch gets the negated branch of C; if triggered by a rising edge, the first D latch gets the negated branch of C. This results in two separate D latches, which cannot be written to simultaneously; this means that one can be used as read-only memory and the other can be used as write-only memory for a given clock cycle, elegantly solving the problem with D latches.

Specifically, in the rising edge case, when C = 0, the first D latch has an output value of D, and the second D latch has an output value of Q (i.e. the previous value). When C = 1, the first D latch has an output value of its previous value, and the second D latch has the same output value as the first. Similarly, in the falling edge case, when C = 0, the first D latch has an output value of its previous value, and the second D latch has the same output value as the first; and when C = 1, the first D latch has an output value of D, and the second D latch has an output value of its previous value. Note that in order for this to work, the clock pulse interval has to be long enough for all the necessary circuit wizardry to be completed before writing back to the flip-flop is attempted.

2.1.2D flip-flops with different gates¶

Let's say you have to draw the complete circuit diagram of a D flip-flop using only AND, OR, and NOT gates (from exercises 3, question 4). You can pretty much take the standard D flip-flop diagram - the only change you have to make is to replace the NOR gates with inverted OR gates (so OR, followed immediately by a NOT). See the solution in the exercises for the diagram.

As another example: if you were only allowed to use AND and NOT gates, you could replace each NOR gate by an AND gate to which both inputs were inverted with a NOT gate. In other words, you would be converting NOR ($\overline{(A + B)}$) into $\overline A \cdot \overline B$.

2.1.3Replacing a D latch¶

Draw out the truth table for the proposed replacement gate and work through the cases. See question 5 in exercises 3 for an example.

2.2Examples¶

• Exercises 3, questions 4 and 5

3Timing diagrams for registers¶

Given the circuit diagram for a register and the initial values in the register, draw the timing diagram for it.

3.1General solution¶

Some background: registers consist of a set of D flip-flops, which together hold the value of some variable. They're written to all at once, not individually (but of course, they can all have different values). See the lecture 6 notes for an example of a shift right register.

With a more general shift register that can shift in either direction, clear its memory, and write to all its bits, we would need a 2-bit selector applied via a multiplexor for each D latch.

To draw the timing diagram for each of the outputs ($Q_0, Q_1, Q_2$ etc), just iterate through each clock cycle and follow what happens at each D latch.

3.2Examples¶

• None

4T flip-flops¶

Implement a circuit that involves a T flip-flop (e.g. a counter circuit).

4.1General solution¶

A T flip-flop ("toggle") consists of a D latch in which the input variable D comes from the output variable $\overline Q$. The output $Q$ changes switches between 0 and 1 at half the rate of the clock cycle, and whether it changes value at a falling edge or at a rising edge depends on that property of the D latch itself.

These circuits can be used as counters. If we were to implement a mod $n$ counter, we'd probably want to use a multiplexor of some sort. Not really sure how this works. See the example below.

4.2Examples¶

• Exercises 3, question 6

5Generic circuits¶

Describe a circuit that performs a specified task.

5.1General solution¶

Usable elements:

• RS latch
• D latch
• D flip-flop
• T flip-flop
• Shift registers
• Registers to hold the results
• Selectors and multiplexors
• Basic logic gates

See the example below.

5.2Examples¶

• Exercises 3, question 7