La optimización lógica es un proceso de encontrar una representación equivalente del circuito lógico especificado bajo una o más restricciones específicas. Este proceso es parte de una síntesis lógica aplicada en electrónica digital y diseño de circuitos integrados .
Generalmente, el circuito está limitado a un área mínima de chip que cumple 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 una latencia más corta y minimiza los riesgos de diafonía inesperada , el peligro de procesamiento de señal retrasado y otros problemas presentes en el nivel nanoescalar de 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 de encontrar una más simple, que al evaluarla finalmente produciría los mismos resultados que la original.
El problema de tener un circuito complicado (es decir, uno con muchos elementos, como puertas lógicas ) es que cada elemento ocupa espacio físico y su producción cuesta tiempo y dinero. La minimización de circuitos puede ser una forma de optimización lógica utilizada para reducir el área de lógica compleja en 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 la forma del algoritmo Quine-McCluskey , seguido más tarde por el minimizador lógico heurístico Espresso , la rápida mejora de las densidades de chips y la amplia adopción de lenguajes de descripción de hardware para la descripción de circuitos, formalizó el dominio de optimización lógica tal como existe hoy, incluido Logic Friday (interfaz gráfica), Minilog y ESPRESSO-IISOJS (lógica de muchos valores). [3]
Los métodos de simplificación de circuitos lógicos son igualmente aplicables a la minimización de expresiones booleanas.
Hoy en día, la optimización lógica se divide en varias categorías:
Los métodos gráficos representan la función lógica requerida mediante un diagrama que representa las variables lógicas y el valor de la función. Al manipular o inspeccionar un diagrama, se pueden eliminar muchos cálculos tediosos. Los métodos de minimización gráfica para lógica de dos niveles incluyen:
Los mismos métodos de minimización (simplificación) de expresiones booleanas que se enumeran a continuación se pueden aplicar a la optimización del circuito.
Para el caso en el que la función booleana está especificada por un circuito (es decir, queremos encontrar un circuito equivalente del tamaño mínimo posible), durante mucho tiempo se conjeturó que el problema de minimización del circuito ilimitado era completo en complejidad temporal , un resultado finalmente demostrado. en 2008, [4] pero existen heurísticas efectivas como los mapas de Karnaugh y el algoritmo Quine-McCluskey que facilitan el proceso.
Los métodos de minimización de funciones booleanas incluyen:
Los métodos que encuentran representaciones de circuitos óptimas de funciones booleanas a menudo se denominan "síntesis exacta" en la literatura. Debido a la complejidad computacional, la síntesis exacta sólo es manejable para funciones booleanas pequeñas. Los enfoques recientes asignan el problema de optimización a un problema de satisfacibilidad booleano . [5] [6] Esto permite encontrar representaciones de circuitos óptimas utilizando un solucionador SAT .
Un método heurístico utiliza reglas establecidas que resuelven un subconjunto práctico y útil del conjunto mucho mayor posible de problemas. Es posible que el método heurístico no produzca la solución teóricamente óptima, pero si es útil, proporcionará la mayor parte de la optimización deseada con un mínimo de esfuerzo. Un ejemplo de un sistema informático que utiliza métodos heurísticos para la optimización lógica es el minimizador lógico heurístico Espresso .
Mientras que una representación de circuitos de dos niveles se refiere estrictamente a la vista plana del circuito en términos de SOP ( suma de productos ), que es más aplicable a una implementación PLA del diseño [ se necesita aclaración ] , una representación de circuitos de varios niveles La representación es una visión más genérica del circuito en términos de SOP, POS ( producto de sumas ), forma factorizada, etc. conectados arbitrariamente. Los algoritmos de optimización lógica generalmente funcionan en la representación estructural (SOP, forma factorizada) o funcional ( decisión binaria) . diagramas , diagramas algebraicos de decisión ) del circuito. En forma de suma de productos (SOP), las puertas AND forman la unidad más pequeña y se unen mediante OR, mientras que en forma de producto de sumas (POS) es lo opuesto. El formulario POS requiere paréntesis para agrupar los términos OR bajo puertas AND, porque OR tiene menor precedencia que AND. Tanto el formulario SOP como el POS se traducen muy bien en lógica de circuito.
Si tenemos dos funciones F 1 y F 2 :
La representación de 2 niveles anterior toma seis términos de producto y 24 transistores en CMOS Rep.
Una representación funcionalmente equivalente en multinivel puede ser:
Si bien el número de niveles aquí es 3, el número total de términos y literales del producto se reduce [ cuantifica ] debido a que se comparte el término B + C.
De igual forma, distinguimos entre circuitos combinacionales y circuitos secuenciales . Los circuitos combinacionales producen sus salidas basándose únicamente en las entradas actuales. Se pueden representar mediante relaciones booleanas . Algunos ejemplos son codificadores prioritarios , decodificadores binarios , multiplexores , demultiplexores .
Los circuitos secuenciales producen su salida basándose tanto en las entradas actuales como en las pasadas, dependiendo de una señal de reloj para distinguir las entradas anteriores de las actuales. Pueden representarse mediante máquinas de estados finitos. Algunos ejemplos son las chanclas y las contadoras .
Si bien hay muchas formas de minimizar un circuito, este es un ejemplo que minimiza (o simplifica) una función booleana. La función booleana que realiza 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 . 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 puertas Y y una puerta O.
El circuito se puede simplificar (minimizar) aplicando las leyes del álgebra booleana o usando la intuición. Dado que el ejemplo establece que es verdadero cuando es falso y al revés, se puede concluir que esto simplemente significa . En términos de puertas lógicas, la desigualdad simplemente significa una puerta XOR (o exclusiva). Por lo tanto, . Entonces los dos circuitos que se muestran a continuación son equivalentes, como se puede comprobar mediante una tabla de verdad :
{{cite book}}: |work=ignorado ( ayuda )