Boolean Circuits · NAND Game: Arithmetic Logic Unit (Optional)

Lesson 4

Nikolai Chukhin · Alexander S. Kulikov

The token \(\texttt{0}\) used below has no inputs and writes one 16-bit zero.

Problem. Synthesize a circuit of size \(7\) over \(\{\operatorname{NAND}_{2},\allowbreak \operatorname{LOGICUNIT},\allowbreak \operatorname{ARITHUNIT},\allowbreak \operatorname{AND},\allowbreak \operatorname{ADD},\allowbreak \operatorname{SELECT},\allowbreak \operatorname{INV},\allowbreak 0\}\) computing the 16-bit arithmetic-logic-unit function \(\operatorname{ALU}(u,op_{1},op_{0},zx,sw,x,y)\): The input-label line is \(\texttt{u op1 op0 zx sw}\); the 16-bit labels \(\texttt{x}\) and \(\texttt{y}\) are predefined. First, modify the operands 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 single 16-bit output: \[\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 & 0 & 1 & x + 1 \\ 1 & 1 & 0 & x - y \\ 1 & 1 & 1 & x - 1\end{array}\] The table uses the modified operands, and arithmetic is modulo \(2^{16}\).

This problem can only be submitted at Cogniterra.