Lesson 4

Problem. Construct a condition checker. The three input flags are \(\texttt{lt}\), \(\texttt{eq}\), and \(\texttt{gt}\). The label \(\texttt{x}\) is a hardcoded 16-bit input, so you may use it directly in gate lines. The output of your circuit must be a single bit.

The flags correspond to the following conditions on \(\texttt{x}\): \[\begin{array}{c | l} \text{flag} & \text{condition} \\ \hline \texttt{lt} & x < 0 \\ \texttt{eq} & x = 0 \\ \texttt{gt} & x > 0\end{array}\]

Your circuit should output \(1\) if at least one selected condition is true for \(\texttt{x}\). So the flags can be combined as follows: \[\begin{array}{c c c | l} lt & eq & gt & \text{output } 1 \text{ when} \\ \hline 0 & 0 & 0 & \text{never} \\ 0 & 0 & 1 & x > 0 \\ 0 & 1 & 0 & x = 0 \\ 0 & 1 & 1 & x \ge 0 \\ 1 & 0 & 0 & x < 0 \\ 1 & 0 & 1 & x \ne 0 \\ 1 & 1 & 0 & x \le 0 \\ 1 & 1 & 1 & \text{always}\end{array}\]

Here \(\texttt{x}\) is interpreted as a signed 16-bit integer, so \(\texttt{x}\)<0 exactly when its most significant bit is \(1\).

You may use only the following functions: \[\begin{aligned}\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{ISNEG}(x) &= \begin{cases} 1, & x < 0, \\ 0, & x \ge 0, \end{cases} \\ \operatorname{ISZERO}(x) &= \begin{cases} 1, & x = 0, \\ 0, & x \ne 0. \end{cases}\end{aligned}\]

For example, a line \(\texttt{z x ISNEG}\) means that \(\texttt{z}\)=1 exactly when the hardcoded input \(\texttt{x}\) is negative.

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