Lesson 2

Problem. Construct an arithmetic unit. The two bit-flags \(op_{1}\) and \(op_{0}\) select which of four arithmetic operations is performed on two hardcoded 16-bit inputs \(x\) and \(y\). In this task, the labels \(\texttt{x}\) and \(\texttt{y}\) are already available and denote 16-bit input values, so you may use them directly in gate lines. The output of your circuit must be a single 16-bit label.

The selected operation is: \[\begin{array}{c c | l} op_1 & op_0 & \text{output} \\ \hline 0 & 0 & x + y \\ 1 & 0 & x - y \\ 0 & 1 & x + 1 \\ 1 & 1 & x - 1\end{array}\]

All arithmetic is performed modulo \(2^{16}\); that is, any overflow bit is ignored.

You may use only the following functions: \[\begin{aligned}\operatorname{NAND}(a,b) &= \neg(a \land b), \\ \operatorname{SELECT}_{16}(s,d_1,d_0) &= \begin{cases} d_0, & s=0, \\ d_1, & s=1, \end{cases} \\ \operatorname{ADD}_{16}(a,b) &= a+b \pmod{2^{16}}, \\ \operatorname{SUB}_{16}(a,b) &= a-b \pmod{2^{16}}, \\ 0() &= 0, \\ \operatorname{INV}(a) &= \neg a, \\ \operatorname{BUNDLE}_{16}(a_{15},\dotsc,a_0) &= (a_{15}\dotsm a_0).\end{aligned}\]

For example, a line \(\texttt{z x y ADD16}\) means that \(\texttt{z}\) is a new 16-bit label equal to the sum of the hardcoded inputs \(\texttt{x}\) and \(\texttt{y}\), modulo \(2^{16}\).

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