Número mínimo de puertas NAND para implementar f(x,y,z,w)=x(y+zw)+yz'

Como dice el título, dada una función F ( X , y , z , w ) = X . ( y + z . w ) + y . z ¯ , ¿cuál es el número mínimo de puertas NAND que necesita para implementar f?

Mi primer intento de solución fue dibujar un kmap para ver si había una expresión booleana más simplificada (técnicamente, primero dibujé la tabla de verdad para encontrar los términos mínimos). Desde el kmap, encontré F ( X , y , z , w ) = X . y + y . z ¯ + X . z . w

Sé que puede implementar AND usando dos puertas NAND, O usando 3 puertas NAND, y NO usando una sola puerta NAND. Por lo tanto, pensé, "bueno, tenemos 1 NO, 2 OR, 3 AND, por lo que necesitaríamos 1 + ( 2 ∗ 3 ) + ( 3 ∗ 2 ) = 13 Puertas NAND". Pero se supone que la respuesta correcta es 7.

  1. ¿Qué está mal/insuficiente con mi razonamiento?
  2. ¿Cómo diablos implementas la función usando solo 7 NAND?
Ponerlo en forma SOP significa que tiene una cantidad mínima de capas lógicas y, por lo tanto, un tiempo de propagación mínimo, pero no significa necesariamente una cantidad mínima de puertas, que yo sepa. Pero no he hecho lógica digital en años, por lo que podría estar equivocado.
Creo que no existe un método formal para una implementación NAND óptima. Sin embargo, hay algunos basados ​​​​en heurística, pero dudo que se le pida que emplee uno. Probablemente solo te pidan que uses tu intuición.
Haz tu kmap. Hacer SOP. Toma de Morgan
La doble inversión común y el método de aplicación del teorema de DeMorgan convierte cada suma de productos fácilmente en una fórmula solo NAND. Comience desde el x(y+zw)+yz' original porque tiene menos operaciones que su versión minimizada. Pero el usuario @Shashank VM ya dijo cómo se debe hacer, así que no escribo una respuesta duplicada, esto queda como un comentario. f=((x(y'(zw)')')'(yz')')' Supongo que muchos de nosotros no podemos ver esto como un circuito a primera vista, pero si encuentra cómo obtener lo mismo, tiene descubrió la solución.

Respuestas (2)

Le sugiero que esboce su solución propuesta, simplemente reemplazando las compuertas AND, OR y NOT con NAND según sea necesario.

Ahora, busque lugares donde tenga dos NAND en serie donde ambos NAND estén conectados como puertas NOT. Hay una oportunidad para la simplificación allí.

Problema diferente, mismo enfoque general en términos de cómo pensarlo... electronics.stackexchange.com/questions/264105/…
@ShashankVM Bueno, el tiempo y el esfuerzo necesarios dependerán de las habilidades y los antecedentes del estudiante. Encuentro que el enfoque algebraico es bastante propenso a errores e innecesario para casos simples, pero para cada uno.

Un enfoque algebraico es más sencillo. Si reemplaza las puertas por el equivalente NAND, lo más probable es que su circuito se vuelva redundante y luego necesite simplificarlo nuevamente.

He explicado en detalle cómo convertir una expresión booleana a forma NAND, algebraicamente, con la ayuda de un ejemplo en esta respuesta

Es interesante notar que puede implementar la función en cuestión usando solo 5 puertas NAND, no siete . Aquí está la manipulación algebraica para convertir la expresión a la forma NAND: F ( X , y , z , w ) = X . ( y + z . w ) + y . z ¯ = X . y + X . z . w + y . z ¯

Tomando doble complemento, obtenemos

F ( X , y , z , w ) = X . y + X . z . w + y . z ¯ ¯ ¯

Aplicando la ley de De Morgan:

F ( X , y , z , w ) = ( X . y ¯ ) . ( X . z . w ¯ ) . ( y . z ¯ ¯ ) ¯

El circuito utiliza 5 puertas NAND.

esquemático

simular este circuito : esquema creado con CircuitLab

Número mínimo de puertas NAND para implementar f(x,y,z,w)=x(y+zw)+yz'
RespuestasAquíPolítica de privacidad1y, 2v