Lesson 3

The tokens \(\texttt{ADD16}\) and \(\texttt{SUB16}\) take two 16-bit values \(x,y\), in that order, and write one 16-bit value: \(\operatorname{ADD}(x,y)=x+y \pmod{2^{16}}\) and \(\operatorname{SUB}(x,y)=x-y \pmod{2^{16}}\). The token \(\texttt{1}\) has no inputs and writes the 16-bit value \(1\).

Problem. Synthesize a circuit of size \(5\) over \(\{\operatorname{NAND}_{2},\allowbreak \operatorname{SELECT},\allowbreak \operatorname{ADD},\allowbreak \operatorname{SUB},\allowbreak 1\}\) computing the 16-bit arithmetic-unit function \(\operatorname{ARITHUNIT}(op_{1},op_{0},x,y)\): The input-label line 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 (all arithmetic is modulo \(2^{16}\)): \[\begin{array}{c c | l} op_1 & op_0 & \text{output} \\ \hline 0 & 0 & x + y \\ 0 & 1 & x + 1 \\ 1 & 0 & x - y \\ 1 & 1 & x - 1\end{array}\]