Lesson 5

The next task provides two additional primitives. The token \(\texttt{0}\) has no inputs and writes one bit. The gate \(\operatorname{ADD}_{8}(A,B,c_{\mathrm{in}})=(c_{\mathrm{out}},Z)\) adds two 8-bit values and a carry bit, so \(A+B+c_{\mathrm{in}}=2^{8}c_{\mathrm{out}}+Z\).

Problem. Synthesize a circuit of size \(3\) over \(\{\operatorname{NAND}_{2}, \operatorname{INV}_{1}, 0, \operatorname{XOR}_{2}, \operatorname{ADD}_{8}\}\) computing \(8\)-bit increment: \(\operatorname{INC}_{8}(x) = x + 1 \pmod{2^8}\).

The input bits are \(x_{7},\dotsc,x_{0}\); list the output bits as \(y_{7},\dotsc,y_{0}\). For \(\texttt{ADD8}\), the line \(\texttt{cout z7 ... z0 a7 ... a0 b7 ... b0 cin ADD8}\) means \(A+B+\texttt{cin}=2^{8}\texttt{cout}+Z\), where the \(z\)-bits encode \(Z\), while \(\texttt{cin}\) and \(\texttt{cout}\) are the carry-in and carry-out bits.