Lesson 2

Starting with this problem, one variable label may denote an entire \(16\)-bit value. The gates \(\texttt{INV16}\), \(\texttt{AND16}\), \(\texttt{OR16}\), and \(\texttt{XOR16}\) apply the corresponding bit operation component-wise and write one 16-bit value. The gate \(\texttt{SELECT16}\) takes a selector bit \(s\), followed by two 16-bit values \(d_{1},d_{0}\), and writes \(d_{s}\). The gate \(\texttt{NAND2}\) is the only gate in this task whose inputs and output are all individual bits.

Problem. Synthesize a circuit of size \(7\) over \(\{\operatorname{NAND}_{2}, \operatorname{SELECT}_{16}, \operatorname{INV}_{16}, \operatorname{AND}_{16}, \operatorname{OR}_{16}, \operatorname{XOR}_{16}\}\) computing the 16-bit logic-unit function \[\operatorname{LOGICUNIT}_{16}(op_{1},op_{0},x,y)=R,\] where \(R\) is selected as follows: \[\begin{array}{c c | l} op_1 & op_0 & R \\ \hline 0 & 0 & x \land y \\ 0 & 1 & x \lor y \\ 1 & 0 & x \oplus y \\ 1 & 1 & \neg x\end{array}\]