Construir una puerta and de puertas XOR

Question

Yo era capaz de entender cómo hacer que una puerta not bastante fácilmente, pero estoy perplejo, tratando de averiguar cómo hacer que una puerta and. Es incluso posible?

Answer 1

La operación XOR es bilineal: la inversión de cualquiera de las entradas siempre se invierte la salida.

Esta propiedad se conserva incluso si usted cascada de múltiples puertas XOR (y, opcionalmente, la constante de insumos y/o NO puertas) juntos: la inversión de cualquier entrada siempre invierte la salida. Por supuesto, usted puede construir circuitos más complejos donde una sola entrada puede ser dividida de la fed y en varias puertas, pero todos estos circuitos puede ser ampliado a un equivalente de árbol de puertas XOR, posiblemente con la misma entrada que aparecen varias veces. Para cada entrada, uno de los dos casos siguientes se mantenga:

• si el valor de entrada aparece un número impar de veces en la XOR árbol, invirtiendo el que de entrada se invierte la salida;

• si el valor de entrada aparece un número par de veces en la XOR árbol, sus efectos sobre la salida de cancelar, y el resultado termina siendo completamente independiente de la de entrada.

En cualquier caso, sólo los tipos de funciones que se pueden construir mediante la combinación de puertas XOR son aquellos en los que cada entrada sea nunca afecta a la salida, o siempre invertir la salida cuando la entrada es invertida.

Ahora considere la posibilidad de una puerta and: si la primera entrada es 1, la salida es igual a la segunda entrada, mientras que si la primera entrada es 0, el resultado siempre será 0 , independientemente de la segunda entrada. Esto es imposible de implementar con puertas XOR: en cualquier XOR-sólo circuito, alternando la segunda entrada debe cambiar, siempre que la salida o no cambiarlo.

Todo esto puede ser expresado de la manera más concisa en términos matemáticos: XOR es multilineal operador, y la composición de operadores multilineales siempre es multilineal. Y es que no multilineal operador, por lo que no puede ser obtenida por la combinación de XOR de los operadores.

Answer 2

He aquí una prueba de que podría ser un poco más fácil a la imagen visual . . .

Desde XOR es conmutativa (p XOR q = q XOR p) y asociativa (p XOR (q XOR r) = (p XOR q) XOR r), no hay manera interesante re-o re-estructura de una fórmula donde XOR es la única puerta de entrada; algo como p XOR ((t XOR (s XOR q)) XOR r) es equivalente a p XOR q XOR r XOR s XOR t.

Así que si usted sólo tiene dos variables p y q, y la única puerta de entrada que tiene es XOR, entonces la fórmula se puede simplificar el formulario (p XOR p XOR ... XOR p) XOR (q XOR q XOR ... XOR q). Podemos simplificar p XOR p XOR ... XOR p como así:

# of p's       full version     simplification
   0               FALSE             FALSE
   1                 p                 p
   2              p XOR p            FALSE
   3           p XOR p XOR p           p
   4        p XOR p XOR p XOR p      FALSE
   5     p XOR p XOR p XOR p XOR p     p
   .                 .                 .
   .                 .                 .
   .                 .                 .

. . . y del mismo modo con q XOR q XOR ... XOR q. Tan sólo hay cuatro funciones que se pueden calcular:

FALSE XOR FALSE          FALSE
FALSE XOR   q              q
  p   XOR FALSE            p
  p   XOR   q           p XOR q

Ya que dicen que se las arregló para construir una puerta not, supongo que también eres lo que permite proporcionar una entrada constante; pero como se puede ver, la adición de FALSEs no va a cambiar el resultado, la adición de un número par de Verdades no va a cambiar el resultado, y la adición de un número impar de Verdades simplemente invertir el resultado (dándole TRUE, NOT p, NOT qo p XNOR q). Ninguna de estas posibilidades es equivalente a Y.

Answer 3

No. Debido a las complementarias y simétricas de la naturaleza de la XOR de entradas y salidas no hay manera de configurar cualquier número de ellos para generar una salida que no presenta la misma simetría.

Answer 4

Cualquier puramente combinatoria circuito que consiste enteramente de puertas XOR, a partir de una combinatoria punto de vista, calcular el par o impar la función de paridad para la combinación de algunos de sus entradas e ignorar el resto. Esto puede ser demostrado por inducción que si se observa que cada una de las entradas será el de paridad impar, la función de sí mismo, y el xor de dos paridad de funciones de una función de paridad de sus distintos insumos (entradas de los términos que se utilizan en ambos cancelar). El xor de dos o, incluso, dos de paridad impar funciones una función de paridad; el xor de una incluso con un extraño (o viceversa) será una de paridad impar, la función.

Incluso si uno no limitarse a la combinatoria de los circuitos y está dispuesto a asumir determinista retrasos de propagación a través de las compuertas, que no ayuda a menos que los retardos de propagación a través de una puerta XOR variar dependiendo del tipo de señal que pasa a través de. De lo contrario, si una de las entradas a un circuito de cambios, cada nodo nunca será afectado, o siempre va a experimentar el mismo transiciones de estado en el mismo momento en relación a el cambio, independientemente del estado de los demás nodos. Desde una puerta Y requiere que un cambio en una de las entradas sólo debe cambiar la salida si la entrada es baja, una puerta XOR no tendría manera de simular tales condicional comportamiento.