Lesson 4

Problem. Synthesize a circuit of size \(2\) that adds two 2-bit numbers and a carry bit. The inputs are \(a_{1},a_{0},b_{1},b_{0},c_{\mathrm{in}}\), where \(a_{1}a_{0}\) and \(b_{1}b_{0}\) are two-bit numbers and \(c_{\mathrm{in}}\) is the input carry bit. The outputs are \(c_{\mathrm{out}}, s_{1}, s_{0}\), where \(c_{\mathrm{out}}\) is the high bit of the sum. In the output line of your circuit, list \(c_{\mathrm{out}}\), \(s_{1}\), and \(s_{0}\) in this order.

You may use only the following functions: \[\begin{aligned}\operatorname{NAND}(a,b) &= \neg(a \land b), & \operatorname{INV}(a) &= \neg a, \\ \operatorname{AND}(a,b) &= a \land b, & \operatorname{OR}(a,b) &= a \lor b, \\ \operatorname{XOR}(a,b) &= a \oplus b, & \operatorname{ADD}(a,b,c) &= \bigl([(a+b+c)\ge 2],\; (a+b+c)\bmod 2\bigr).\end{aligned}\]

If you use the function \(\operatorname{ADD}\) in a circuit line, write its two output labels first: for example, \(\texttt{h l a b c ADD}\) means \((h,l)=\operatorname{ADD}(a,b,c)\).

Examples: \[\begin{array}{c c c c c | c c c | l} a_1 & a_0 & b_1 & b_0 & c_{\mathrm{in}} & c_{\mathrm{out}} & s_1 & s_0 \\ \hline 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 2+2+1=5 \\ 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 1+2+1=4 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 3+1=4\end{array}\]

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