How could I express an AND gate using only XOR gates ?
20
$\begingroup$
$\endgroup$
-
1$\begingroup$ why you want to express and gates with xor and in what ? $\endgroup$ – ABD Oct 28 '15 at 20:38
-
1$\begingroup$ I am reading something about homomorphic encryption, namely this paper eprint.iacr.org/2013/094.pdf also known as LTV scheme. There it is stated that multiplication means AND, addition between two bits means XOR. So I ask if it is possible to rewrite the scheme using only XOR ? Maybe I should migrate the question to Cryptography beta? $\endgroup$ – user2991856 Oct 28 '15 at 20:54
-
4$\begingroup$ Related: Functional completeness $\endgroup$ – CodesInChaos Oct 29 '15 at 8:50
-
2$\begingroup$ Related: stackoverflow.com/questions/6106934/… $\endgroup$ – rackandboneman Oct 29 '15 at 15:37
-
1$\begingroup$ electronics.stackexchange.com/questions/140684/… $\endgroup$ – Jon Hanna Oct 29 '15 at 17:38
36
$\begingroup$
$\endgroup$
You cant.
Since $XOR$ is associative, i.e. $(x_1\oplus x_2)\oplus x_3=x_1\oplus(x_2\oplus x_3)$, you can only implement functions of the form $x_{i_1}\oplus...\oplus x_{i_k}$ where $x_{i_j}\in\{x_1,x_2\}$. This is equivalent to (depending on the parity of the number of instances of $x_1$ and $x_2$) either 0, $x_1$, $x_2$, or $x_1\oplus x_2$, which are not equivalent to AND.
-
5$\begingroup$ You might want to allow 0 and 1 as inputs as well. You still will not get AND though, although you will get the negation of the above as well. $\endgroup$ – Taemyr Oct 29 '15 at 8:40
19
$\begingroup$
$\endgroup$
Hmmm. It can't be done with boolean algebra that's for sure, but I could wire one up physically. The trick is wiring one of the inputs to a power lead of an XOR gate.
I2
|
0 I1 |
| | |
\| |/ |
|\ / | |
.|---| \ / |--------/
\ V /
\ /
\ /
V
|
AND OUTPUT
The XOR gate is wired up as a non inverting buffer. The trick involved is that if you wire VCC to GND (or by extension a logic ground), the output is a weak GND.
Disclaimer: this works on the silicon I have, but might not work on all silicon.
-
8$\begingroup$ Some explanation of how this works would make this a much better answer. $\endgroup$ – David Richerby Oct 29 '15 at 8:59
-
-
1
-
1
-
4$\begingroup$ "might not work on all silicon." ... yes, and might even damage some - applying an input to a physical gate with the power turned off, or even worse turning the power on afterwards, is out-of-spec for a lot of parts (re: CMOS latchup effect!). Also, the "true" output voltage of the first gate is lower than your supply voltage, and depending on how much lower it is, will shift interpretation of input levels at the second gate significantly. And it is not unlikely (protection diodes, complimentary output...) that I2 will be an effective short circuit to ground when lower gate is unpowered. $\endgroup$ – rackandboneman Oct 29 '15 at 15:48
