Lesson 6

The gate \(\operatorname{INV}_{8}(A)=\neg A\) complements all eight bits of \(A\) and writes the resulting eight bits in the same order.

Problem. Synthesize a circuit of size \(4\) over \(\{\operatorname{NAND}_{2}, \operatorname{INV}_{1}, 0, \operatorname{OR}_{2}, \operatorname{INC}_{8}, \operatorname{ADD}_{8}, \operatorname{INV}_{8}\}\) computing \(8\)-bit subtraction: \(\operatorname{SUB}_{8}(A,B) = A - B \pmod{2^8}\).

The input bits are \(a_{7},\dotsc,a_{0},b_{7},\dotsc,b_{0}\); list the output bits as \(y_{7},\dotsc,y_{0}\). The gate \(\texttt{INC8}\), constructed in the preceding problem, takes eight input bits and writes eight output bits; for example, the abbreviated gate line \(\texttt{z7 ... z0 a7 ... a0 INC8}\) means \(Z=A+1 \pmod{2^8}\), where the \(z\)-bits encode \(Z\). It has no carry output.