Describe how to build a circuit consisting of AND, OR and NOT gates that takes two n-bit binary numbers x and y and outputs then (n + 1)-bit binary number x + y. Your circuit should be a directed acyclic graph (a DAG) whose size is at most polynomial in n and whose depth is constant (where “depth” means the length of the longest directed path); the fan-in and fan-out are not bounded (where “fan-in” and “fan-out” mean the maximum in- and out-degree of any vertex)

Answer rating: 100% (QA)

Explanation An n bit full adder is obtained by cascading n 1bit elementary full adders A Full adder ... View the full answer