É possível escrever um portão AND usando portas XOR?

21

Como expressar um portão AND usando apenas portões XOR?

user2991856
fonte
1
por que você quer expressar e portões com xor e em quê?
ABD
1
Estou lendo algo sobre criptografia homomórfica, ou seja, este documento eprint.iacr.org/2013/094.pdf, também conhecido como esquema LTV. Ali se afirma que multiplicação significa AND, adição entre dois bits significa XOR. Então, pergunto se é possível reescrever o esquema usando apenas XOR? Talvez eu devesse migrar a pergunta para a criptografia beta?
user2991856
4
Relacionado:
Integralidade
2
Veja também: stackoverflow.com/questions/6106934/…
rackandboneman

Respostas:

36

Você não pode.

Uma vez que é associativa, ou seja, ( x 1x 2 ) x 3 = x 1( x 2x 3 ) , só é possível implementar as funções da forma de x i 1. . . x i k onde x i j{ x 1 , x 2 }XOR(x1x2)x3=x1(x2x3)xi1...xikxEuj{x1,x2}. Isso é equivalente a (dependendo da paridade do número de instâncias de e x 2 ) 0, x 1 , x 2 ou x 1x 2 , que não são equivalentes a AND.x1x2x1x2x1x2

Ariel
fonte
5
Você também pode permitir 0 e 1 como entradas. Você ainda não receberá AND, embora também receba a negação do acima.
Taemyr
19

Hummm. Isso não pode ser feito com álgebra booleana, com certeza, mas eu poderia conectar um fisicamente. O truque é conectar uma das entradas ao cabo de força de um portão XOR.

                     I2
                     |
      0  I1          |
      |   |          |
     \|   |/         |
     |\   / |        |
.|---| \ /  |--------/
     \  V  /  
      \   /  
       \ /  
        V 
        |            
     AND OUTPUT

O portão XOR está conectado como um buffer não inversor. O truque envolvido é que, se você conectar o VCC ao GND (ou, por extensão, um aterramento lógico), a saída será um GND fraco.

Isenção de responsabilidade: isso funciona com o silício que eu tenho, mas pode não funcionar com todo o silício.

Joshua
fonte
8
Alguma explicação de como isso funciona tornaria essa uma resposta muito melhor.
David Richerby
O primeiro portão não é redundante neste caso?
Nit
1
Que são estes .|, |>?
Wojowu 29/10/2015
1
@ Wojowu chão e Vcc, eu presumo.
John Dvorak
4
"pode ​​não funcionar com todo o silício." ... sim, e pode até danificar alguns - aplicar uma entrada a um portão físico com a energia desligada ou, pior ainda, ligar a energia posteriormente, está fora da especificação para muitas partes (re: efeito de travamento do CMOS !). Além disso, a tensão de saída "verdadeira" do primeiro gate é mais baixa que a tensão de alimentação e, dependendo de quanto for menor, alterará significativamente a interpretação dos níveis de entrada no segundo gate. E não é improvável (diodos de proteção, saída complementar ...) que I2 seja um curto-circuito efetivo para aterrar quando o portão inferior não estiver energizado.
rackandboneman