Lesson 5

The next task uses two new primitives. The gate \(\texttt{ZERO1}\) has no inputs and writes one zero bit. For gate \(\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.

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