¿Cómo minimizar las puertas en la implementación?

Question

¿Cómo minimizar las puertas en la implementación?

#1 de Anshul (3 votos)
#2 de Greg (2 votos)

4

Soy un estudiante de informática, y varias veces se me ha pedido que implemente una expresión con el número mínimo de puertas NAND o NOR. Nunca pude obtener el pensamiento procedimental exacto al respecto y siempre adiviné la solución que a veces conduce a la respuesta incorrecta.

¿Puede decirme cómo podemos tomarlo como un problema de procedimiento? ¿O es solo practicar y adivinar para tales preguntas? Como ejemplo, ¿cómo se puede implementar una puerta XOR con 4 puertas NAND mínimas? ¿Cómo enfocaré esa pregunta?

digital-logic

pregunta user1766481

2 respuestas

Lea otras preguntas en las etiquetas digital-logic

Grosor de traza de Kicad y autodrutador ¿Es posible que un FPGA se configure "parcialmente"?

score 3 · Answer 1

Hay algunos métodos formales para abordar este problema y están bien documentados. Uno de ellos es K-Map o Karnaugh Maps , y el otro es Quinn-McCluskey . Había otro método bastante tedioso que aprendí, desafortunadamente no lo recuerdo ahora.

Pero estos dos métodos deben satisfacer sus necesidades la mayor parte del tiempo (no todos). El método Quine-McCluskey ofrece mejores resultados, pero es más largo e iterativo, pero escalable. K-Map es un método gráfico que es bastante simple pero se vuelve tedioso a medida que aumenta el número de entradas.

Pero en todos los casos, son mejores que las simples suposiciones, ya que estas últimas tienen cierta ventaja.

Editar: Después de tener una expresión mínima, generalmente es a través del álgebra y la práctica que obtiene las implementaciones NAND y NOR. Ahora no he mirado más allá de mis libros de texto y, por lo tanto, no sé si existen procedimientos formales.

score 2 · Answer 2

Estás buscando álgebra booleana . A continuación se muestran las fórmulas clave, así como un diagrama esquemático (dibujar los pasos puede ayudar a visualizar). Wikipedia entra en detalles con más reglas como leyes monotónicas y leyes de Nonmonotone

Reglas básicas:

BUF: A=(A')'=AA=A+A = A+(BB')=A(B+B')
NO: A'=((A')')'
AND: AB=((AB)')'=(A'+B')' (AND: salida NAND invertida o entradas inventadas NOR)
O: A+B=((A+B)')'=(A'B')' (O: salida NOR invertida o entradas NAND inventadas)
XOR: A^B=A'^B'=((A^B)')'=(A^B')'=AB'+A'B=(A+B)(AB)'=((A(AB)')'(B(AB)')')'
XNOR: (A^B)'=((A'^B')')'=(A^B)'=A^B'=AB+(A+B)'=((AB)'(A+B))'=((A+(A+B)')'+(B+(A+B)')')'

Otro común:

AB+CD = ((AB)'(CD)')'
(A+B)(C+D) = ((A+B)'+(C+D)')'

^{simular este circuito : esquema creado usando CircuitLab}

Método para representar XOR como cuatro puertas NAND:

A^B =       AB' +  A'B     // add forms of 0, BUF rule
    =   AA'+AB' +  A'B+BB' // factor out A and B, algebra
    =  A(A'+B') + (A'+B')B // represent (A'+B') as C :: Reminder (A'+B')=(AB)'
    =        AC + CB       // represent AC as X and CB as Y
    =         X + Y        // substitute  X+Y as (X'Y')', OR rule
    =         (X'Y')'      // restore X and Y to original values
    =      ((AC)'(CB)')'   // restore C as (AB)', equivalent to (A'+B')
    = ((A(AB)')'((AB)'B)')'// DONE, XOR as 4 NAND gates, sharing the (AB)' line

Otro método para hacer lo mismo:

A^B =       (A+B)(AB)'     // represent (AB)' as C
    =       (A+B)C         // Distribute C
    =         AC+BC        // represent AC as X and BC as Y
    =          X+Y         // substitute  X+Y as (X'Y')', OR rule
    =         (X'Y')'      // restore X and Y to original values
    =      ((AC)'(BC)')'   // restore C as (AB)', equivalent to (A'+B')
    = ((A(AB)')'(B(AB)')')'// DONE, XOR as 4 NAND gates, sharing the (AB)' line

¿Cómo minimizar las puertas en la implementación?

Publicaciones recientes del blog

2 respuestas