What are the minimum depth circuits possible for addition and multiplication of two n-bit numbers using just AND and XOR gates? I read somewhere that we can achieve constant depth for addition if we have an OR gate. Can I achieve that using XOR gates?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
You can simulate an OR gate using a constant number of AND and XOR gates:
$$x \lor y = ((x \oplus 1) \land (y \oplus 1)) \oplus 1.$$
Consequently, anything you can do in depth $d$ using AND and OR gates, can be done in depth $\le 3d$ using AND and XOR gates.
-
$\begingroup$ I'm trying to build a SwHE scheme. Can you please tell me the minimum depth circuit for addition and multiplication in which each gate takes just two inputs at a time? The carry lookahead adder ensures constant depth using gates with variable fan-in. $\endgroup$ Commented May 13, 2017 at 16:21