Lesson 2

Starting with this problem, one label may denote an entire 16-bit value. The tokens \(\texttt{INV16}\), \(\texttt{AND16}\), \(\texttt{OR16}\), and \(\texttt{XOR16}\) apply the corresponding bit operation componentwise and write one 16-bit value. The token \(\texttt{SELECT16}\) takes a selector bit \(s\), followed by two 16-bit values \(d_{1},d_{0}\), and writes \(d_{s}\). Only \(\texttt{NAND}\) operates on individual bits in this task.

Problem. Synthesize a circuit of size \(7\) over \(\{\operatorname{NAND}_{2}, \operatorname{SELECT}, \operatorname{INV}, \operatorname{AND}, \operatorname{OR}, \operatorname{XOR}\}\) computing the 16-bit logic-unit function \(\operatorname{LOGICUNIT}(op_{1},op_{0},x,y)\): The input is \(\texttt{op1 op0}\); the 16-bit labels \(\texttt{x}\) and \(\texttt{y}\) are predefined. The unit has one 16-bit output, selected as follows: \[\begin{array}{c c | l} op_1 & op_0 & \text{output} \\ \hline 0 & 0 & x \land y \\ 0 & 1 & x \lor y \\ 1 & 0 & x \oplus y \\ 1 & 1 & \neg x\end{array}\] For example, \(\texttt{z x y AND16}\) means \(z=x \land y\).