Lesson 4

Using latches, one can construct a circuit whose state evolves over time. However, a difficulty arises: since state transitions are not synchronized throughout the circuit, changes propagate in an unpredictable manner, giving rise to race conditions and, more generally, to indeterminate behavior. The standard remedy is the introduction of a clock signal, that is, a one-bit signal that changes periodically and is connected to all stateful components. If components are permitted to modify their outputs only in response to changes in the clock signal, then state transitions occur simultaneously across the circuit, thereby eliminating synchronization issues. In this task, you are required to construct a flip-flop component that stores a bit while the clock signal is equal to \(1\), but begins emitting the stored bit only when the clock signal transitions to \(0\).

Problem. Construct a DFF (data flip-flop). The three input bits are \(\texttt{st}\), \(\texttt{d}\), and \(\texttt{cl}\). The output of your circuit must be a single bit.

Your circuit will be tested on many sequences of input triples \(\texttt{(st,d,cl)}\). The behavior is divided into clock phases:

• When \(\texttt{cl}\)=0, the input bits \(\texttt{st}\) and \(\texttt{d}\) may change.


• When \(\texttt{cl}\) changes from \(0\) to \(1\): if \(\texttt{st}\)=1, then the current value of \(\texttt{d}\) is stored. The stored value is not output yet.


• When \(\texttt{cl}\) changes from \(1\) to \(0\): the previously stored value is output.


• While \(\texttt{cl}\)=1, assume that \(\texttt{st}\) and \(\texttt{d}\) do not change.

The effect of the inputs during this phase is: \[\begin{array}{c c | l} st & d & \text{next stored value} \\ \hline 1 & 0 & 0 \\ 1 & 1 & 1 \\ 0 & 0 & \text{unchanged} \\ 0 & 1 & \text{unchanged}\end{array}\] Before the first successful store-and-clock cycle, the output is undefined, so any output is allowed.

You may use only the following functions: \[\begin{aligned}\operatorname{DLATCH}(st,d) &= \text{the D-latch output}, \\ \operatorname{NAND}(a,b) &= \neg(a \land b), \\ \operatorname{INV}(a) &= \neg a, \\ \operatorname{AND}(a,b) &= a \land b, \\ \operatorname{OR}(a,b) &= a \lor b, \\ \operatorname{XOR}(a,b) &= a \oplus b, \\ \operatorname{SELECT}(s,d_1,d_0) &= \begin{cases} d_0, & s=0, \\ d_1, & s=1. \end{cases}\end{aligned}\] For example, a line \(\texttt{q st d DLATCH}\) means that \(\texttt{q}\) is a new label equal to the current output of a D latch with inputs \(\texttt{st}\) and \(\texttt{d}\).

The authors' solution uses \(4\) gates.