Lesson 7

Let \(\operatorname{ADD}_{n} \colon \{0,1\}^{2n}\to \{0,1\}^{n+1}\) be the addition function of two \(n\)-bit numbers: \[\operatorname{ADD}_{n}(x_{n-1}, x_{n-2},\dotsc, x_{0}, y_{n-1}, y_{n-2},\dotsc, y_{0})=(z_{n}, z_{n-1}, \dotsc, z_{0}),\] so that \[\left(\sum_{i=0}^{n-1}2^{i}x_{i}\right)+\left(\sum_{i=0}^{n-1}2^{i}y_{i}\right)=\sum_{i=0}^{n}2^{i}z_{i}.\] Below, we prove that the circuit complexity of this function is linear.

Theorem. \[\operatorname{size}(\operatorname{ADD}_{n}) \le 5n-3.\]

Proof. Our circuit simulates column-wise addition: we go from right to left through the numbers (from the least significant bits to the most significant) and add the two current bits, \(x_{i}\) and \(y_{i}\), as well as the carry bit \(c_{i}\) from the previous column. To add these three bits, we use the Full Adder block: \((c_{i+1}, z_{i})=\operatorname{FA}(x_{i}, y_{i}, c_{i})\). Thus, for each bit, we need five gates (since \(\operatorname{size}(\operatorname{FA})=5\)), and for the least significant bit (where there is no carry bit yet) we will need only two gates (since \(\operatorname{size}(\operatorname{HA})=2\)).

For example, when \(n=3\), the circuit is arranged as follows.