How could I express an AND gate using only XOR gates ?
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ why you want to express and gates with xor and in what ? $\endgroup$– abcOct 28, 2015 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$– Radu MardariOct 28, 2015 at 20:54
-
4$\begingroup$ Related: Functional completeness $\endgroup$– CodesInChaosOct 29, 2015 at 8:50
-
2$\begingroup$ Related: stackoverflow.com/questions/6106934/… $\endgroup$– rackandbonemanOct 29, 2015 at 15:37
-
1$\begingroup$ electronics.stackexchange.com/questions/140684/… $\endgroup$– Jon HannaOct 29, 2015 at 17:38
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
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$– TaemyrOct 29, 2015 at 8:40
$\begingroup$
$\endgroup$
8
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$ Oct 29, 2015 at 8:59
-
$\begingroup$ Isn't the first gate redundant in this case? $\endgroup$– EtheryteOct 29, 2015 at 13:35
-
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$ Oct 29, 2015 at 15:48
$\begingroup$
$\endgroup$
No
Consider W the set of the functions that maps {0, 1}×{0, 1} to {0, 1}. For example, the AND gate (denoted by ^) and the XOR gate (denoted by ⊕) are elements of W.
Now, for f ∈ W, define Val(f) in that way:
Val(f) := f(0, 0) ⊕ f(0, 1) ⊕ f(1, 0) ⊕ f(1, 1)
Its possible to prove that Val(¬f) = Val(f) and that Val(f ⊕ g) = Val(f) ⊕ Val(g). Now, let A(x, y) = x and B(x, y) = y two of the elements of W, and note that Val(A) = Val(B) = 0, and that Val(^) = 1
To finish, suppose that ^ can be expressed using only A, B, ⊕ and negations, so we have something like
A ^ B = ¬((¬A) ⊕ ((¬B) ⊕ A)) ⊕ ... ⊕ ((¬A) ⊕ (¬(A ⊕ ¬(A ⊕ B))))
and applying Val in both sides, we have
Val(A ^ B) = Val(¬((¬A) ⊕ ((¬B) ⊕ A)) ⊕ ... ⊕ ((¬A) ⊕ (¬(A ⊕ ¬(A ⊕ B)))))
→
1 = ((Val(A)) ⊕ ((Val(B)) ⊕ Val(A))) ⊕ ... ⊕ (((Val(A))) ⊕ ((Val(A) ⊕ (Val(A) ⊕ Val(B)))))
→
1 = ((0) ⊕ ((0) ⊕ 0)) ⊕ ... ⊕ (((0)) ⊕ ((0 ⊕ (0 ⊕ 0))))
→
1 = 0
a contradiction.
