Optimización lógica

La optimización lógica es un proceso que consiste en encontrar una representación equivalente del circuito lógico especificado bajo una o más restricciones específicas. Este proceso forma parte de la síntesis lógica aplicada en la electrónica digital y el diseño de circuitos integrados .

Generalmente, el circuito está limitado a un área mínima de chip que cumpla con un retardo de respuesta predefinido. El objetivo de la optimización lógica de un circuito dado es obtener el circuito lógico más pequeño que evalúe los mismos valores que el original. ^{[ 1 ]} Por lo general, el circuito más pequeño con la misma función es más barato, ^{[ 2 ]} ocupa menos espacio, consume menos energía , tiene menor latencia y minimiza los riesgos de diafonía inesperada , el peligro de procesamiento de señal retardado y otros problemas presentes en el nivel de nanoescala de las estructuras metálicas en un circuito integrado .

En términos de álgebra booleana , la optimización de una expresión booleana compleja es un proceso para encontrar una más simple que, al evaluarse, produzca finalmente los mismos resultados que la original.

El problema de tener un circuito complejo (es decir, uno con muchos elementos, como puertas lógicas ) es que cada elemento ocupa espacio físico y su producción requiere tiempo y dinero. La minimización de circuitos puede ser una forma de optimización lógica que se utiliza para reducir el área de la lógica compleja en los circuitos integrados .

Con la llegada de la síntesis lógica , uno de los mayores desafíos que enfrentó la industria de la automatización del diseño electrónico (EDA) fue encontrar la representación de circuito más simple de la descripción de diseño dada. ^{[ nb 1 ]} Si bien la optimización lógica de dos niveles había existido durante mucho tiempo en forma del algoritmo Quine-McCluskey , seguido posteriormente por el minimizador lógico heurístico Espresso , la rápida mejora de las densidades de los chips y la amplia adopción de lenguajes de descripción de hardware para la descripción de circuitos formalizaron el dominio de la optimización lógica tal como existe hoy, incluyendo Logic Friday (interfaz gráfica), Minilog y ESPRESSO-IISOJS (lógica multivaluada). ^{[ 3 ]}

Los métodos de simplificación de circuitos lógicos son igualmente aplicables a la minimización de expresiones booleanas .

Si bien existen muchas maneras de minimizar un circuito, este es un ejemplo que minimiza (o simplifica) una función booleana. La función booleana realizada por el circuito está directamente relacionada con la expresión algebraica a partir de la cual se implementa la función. ^{[ 7 ]} Considere el circuito utilizado para representar${\displaystyle (A\wedge {\bar {B}})\vee ({\bar {A}}\wedge B)}$Es evidente que en esta afirmación se utilizan dos negaciones, dos conjunciones y una disyunción. Esto significa que para construir el circuito se necesitarían dos inversores , dos compuertas AND y una compuerta OR .

El circuito se puede simplificar (minimizar) aplicando las leyes del álgebra booleana o usando la intuición. Dado que el ejemplo indica que${\displaystyle A}$es cierto cuando${\displaystyle B}$es falso y viceversa, se puede concluir que esto simplemente significa${\displaystyle A\neq B}$En términos de compuertas lógicas, la desigualdad simplemente significa una compuerta XOR (o exclusivo). Por lo tanto,${\displaystyle (A\wedge {\bar {B}})\vee ({\bar {A}}\wedge B)\iff A\neq B}$Entonces, los dos circuitos que se muestran a continuación son equivalentes, como se puede comprobar utilizando una tabla de verdad :

• Diagrama de decisión binaria (BDD)
• No me importa la condición
• Implicante principal
• Complejidad del circuito : sobre la estimación de la complejidad del circuito
• Composición de la función
• Descomposición de funciones
• subutilización de puertas
• Redundancia lógica
• Tabla de minimización de Harvard (Wikiversity) (Wikibooks)

• Lind, Larry Frederick; Nelson, John Christopher Cunliffe (1977). Análisis y diseño de sistemas digitales secuenciales . Macmillan Press . ISBN 0-33319266-4.(146 páginas)
• De Micheli, Giovanni (1994). Síntesis y optimización de circuitos digitales . McGraw-Hill . ISBN 0-07-016333-2.(Nota: Los capítulos 7 a 9 tratan sobre la optimización combinatoria de dos niveles, la optimización combinatoria de múltiples niveles y la optimización de circuitos secuenciales, respectivamente).
• Hachtel, Gary D.; Somenzi, Fabio (2006) [1996]. Algoritmos de síntesis y verificación lógica . Springer Science & Business Media . ISBN 978-0-387-31005-3.
• Kohavi, Zvi; Jha, Niraj K. (2009). "4-6". Teoría de la conmutación y los autómatas finitos (3ª  ed.). Prensa de la Universidad de Cambridge . ISBN 978-0-521-85748-2.
• Rutenbar, Rob A. Minimización multinivel, Parte I: Modelos y métodos (PDF) (diapositivas de la clase). Universidad Carnegie Mellon (CMU). Clase 7. Archivado (PDF) del original el 15 de enero de 2018. Recuperado el 15 de enero de 2018 ;Rutenbar, Rob A. Minimización multinivel, Parte II: Extracto de cubo/cokernel (PDF) (diapositivas de la clase). Universidad Carnegie Mellon (CMU). Clase 8. Archivado (PDF) del original el 15 de enero de 2018. Recuperado el 15 de enero de 2018 .