Lesson 3

Problem. Construct an ALU (Arithmetic Logic Unit). The five control bits are \(\texttt{u}\), \(\texttt{op1}\), \(\texttt{op0}\), \(\texttt{zx}\), and \(\texttt{sw}\). The labels \(\texttt{x}\) and \(\texttt{y}\) are hardcoded 16-bit inputs, so you may use them directly in gate lines. The output of your circuit must be a single 16-bit label.

First, the operands are modified as follows:

• If \(\texttt{sw}\)=1, then \(\texttt{x}\) and \(\texttt{y}\) are swapped.


• After that, if \(\texttt{zx}\)=1, then the left operand is replaced with \(0\).

Then \(\texttt{u}\), \(\texttt{op1}\), and \(\texttt{op0}\) select the final operation: \[\begin{array}{c c c | l} u & op_1 & op_0 & \text{output} \\ \hline 0 & 0 & 0 & x \land y \\ 0 & 0 & 1 & x \lor y \\ 0 & 1 & 0 & x \oplus y \\ 0 & 1 & 1 & \neg x \\ 1 & 0 & 0 & x + y \\ 1 & 1 & 0 & x - y \\ 1 & 0 & 1 & x + 1 \\ 1 & 1 & 1 & x - 1\end{array}\] Here the table is applied to the effective operands after the \(\texttt{sw}\) and \(\texttt{zx}\) modifications. For example, when the selected operation is subtraction: \[\begin{array}{c c | l} zx & sw & \text{effective operation} \\ \hline 0 & 0 & x-y \\ 0 & 1 & y-x \\ 1 & 0 & 0-y \\ 1 & 1 & 0-x\end{array}\]

All arithmetic is performed modulo \(2^{16}\). You may use only the following functions: \[\begin{aligned}\operatorname{NAND}(a,b) &= \neg(a \land b), \\ \operatorname{LOGICUNIT}(op_1,op_0,x,y) &= \text{the logic-unit output}, \\ \operatorname{ARITHUNIT}(op_1,op_0,x,y) &= \text{the arithmetic-unit output}, \\ \operatorname{AND}_{16}(a,b) &= a \land b, \\ \operatorname{ADD}_{16}(a,b) &= a+b \pmod{2^{16}}, \\ \operatorname{SELECT}_{16}(s,d_1,d_0) &= \begin{cases} d_0, & s=0, \\ d_1, & s=1, \end{cases} \\ \operatorname{INV}_{16}(a) &= \overline{a}, \\ 0() &= 0000000000000000.\end{aligned}\]

For example, a line \(\texttt{z sw y x SELECT16}\) means that \(\texttt{z}\) is a new 16-bit label equal to \(\texttt{x}\) if \(\texttt{sw}\)=0 and equal to \(\texttt{y}\) if \(\texttt{sw}\)=1.

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