Lesson 2

Problem. Construct an SR latch (set/reset-latch). The two input bits are \(\texttt{s}\) and \(\texttt{r}\). The output of your circuit must be a single bit.

Your circuit will be tested on many sequences of input pairs \(\texttt{(s,r)}\). At each step, the output should behave as follows: \[\begin{array}{c c | l} s & r & \text{output} \\ \hline 1 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 1 & \text{previous output} \\ 0 & 0 & \text{undefined}\end{array}\] Until the first set or reset signal, the output is also undefined. That means any output is allowed before the first occurrence of \(\texttt{(1,0)}\) or \(\texttt{(0,1)}\). If the pair \(\texttt{(0,0)}\) occurs at any later moment, the state becomes undefined again, and after that any output is allowed until the next set or reset signal.

In this problem feedback is allowed: a label may be used as an argument even if it is defined later. This lets you build cyclic circuits such as latches.

You may use only the following functions: \[\begin{aligned}\operatorname{NAND}(a,b) &= \neg(a \land b), & \operatorname{AND}(a,b) &= a \land b, \\ \operatorname{OR}(a,b) &= a \lor b, & \operatorname{INV}(a) &= \neg a, \\ \operatorname{XOR}(a,b) &= a \oplus b.\end{aligned}\]

For example, the line \(\texttt{q r nq}\) \(\operatorname{NAND}\) means \(\texttt{q}\)=\(\operatorname{NAND}\)(\(\texttt{r}\),\(\texttt{nq}\)), even if the label \(\texttt{nq}\) is defined later.

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