La optimización lógica es un proceso de búsqueda de una representación equivalente del circuito lógico especificado bajo una o más restricciones especificadas. 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á restringido 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 económico, [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 de nanoescala de las estructuras metálicas en un circuito integrado .
En términos del álgebra de Boole , la optimización de una expresión booleana compleja es un proceso de encontrar una más simple, que al evaluarla produciría en última instancia los mismos resultados que la original.
El problema de tener un circuito complicado (es decir, uno con muchos elementos, como las puertas lógicas ) es que cada elemento ocupa espacio físico y cuesta tiempo y dinero producirlo. 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 el advenimiento de la síntesis lógica , uno de los mayores desafíos que enfrentó la industria de 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 , las densidades de chips que mejoran rápidamente 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, 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 la lógica de dos niveles incluyen:
Los mismos métodos de minimización (simplificación) de expresiones booleanas enumerados a continuación se pueden aplicar a la optimización del circuito.
Para el caso en que la función booleana es especificada por un circuito (es decir, queremos encontrar un circuito equivalente de tamaño mínimo posible), durante mucho tiempo se conjeturó que el problema de minimización de 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 de 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 se denominan a menudo síntesis exacta en la literatura. Debido a la complejidad computacional, la síntesis exacta solo es factible para funciones booleanas pequeñas. Los enfoques recientes asignan el problema de optimización a un problema de satisfacibilidad booleana . [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 de un conjunto mucho más amplio de problemas posibles. El método heurístico puede no producir la solución teóricamente óptima, pero si es útil, proporcionará la mayor parte de la optimización deseada con un mínimo 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 aplanada del circuito en términos de SOP ( suma de productos ), que es más aplicable a una implementación PLA del diseño [ aclaración necesaria ] , una representación de múltiples niveles es una vista más genérica del circuito en términos de SOP conectados arbitrariamente, POS ( producto de sumas ), forma factorizada, etc. Los algoritmos de optimización lógica generalmente funcionan en la representación estructural (SOP, forma factorizada) o funcional ( diagramas de decisión binaria , diagramas de decisión algebraica ) del circuito. En la forma de suma de productos (SOP), las compuertas AND forman la unidad más pequeña y se unen mediante OR, mientras que en la forma de producto de sumas (POS) es lo opuesto. La forma POS requiere paréntesis para agrupar los términos OR bajo las compuertas AND, porque OR tiene menor precedencia que AND. Tanto la forma SOP como la POS se traducen bien en la lógica de circuitos.
Si tenemos dos funciones F 1 y F 2 :
La representación de dos 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 manera similar, distinguimos entre circuitos combinacionales y circuitos secuenciales . Los circuitos combinacionales producen sus salidas basándose únicamente en las entradas actuales. Pueden representarse mediante relaciones booleanas . Algunos ejemplos son los codificadores de prioridad , los decodificadores binarios , los multiplexores y los demultiplexores .
Los circuitos secuenciales generan su salida en función de las entradas actuales y 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 los flip-flops y los contadores .
Si bien existen muchas formas de minimizar un circuito, este es un ejemplo que minimiza (o simplifica) una función booleana. La función booleana llevada a cabo 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 . Es evidente que en esta declaració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 AND y una puerta OR .
El circuito se puede simplificar (minimizar) aplicando las leyes del álgebra de Boole o usando la intuición. Dado que el ejemplo establece que es verdadero cuando es falso y viceversa, 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 utilizando una tabla de verdad :
{{cite book}}: |work=ignorado ( ayuda )