El minimizador lógico ESPRESSO es un programa informático que utiliza algoritmos heurísticos y específicos para reducir de manera eficiente la complejidad de los circuitos de puertas lógicas digitales. [1] ESPRESSO-I fue desarrollado originalmente en IBM por Robert K. Brayton et al. en 1982. [2] [3] y mejorado como ESPRESSO-II en 1984. [4] [5] Richard L. Rudell publicó posteriormente la variante ESPRESSO-MV en 1986 [6] y ESPRESSO-EXACT en 1987. [7] [8] [5] Espresso ha inspirado muchos derivados.
Los dispositivos electrónicos están compuestos por numerosos bloques de circuitos digitales, cuya combinación realiza la tarea requerida. La implementación eficiente de funciones lógicas en forma de circuitos de puertas lógicas (de modo que no se utilicen más puertas lógicas de las necesarias) es necesaria para minimizar los costos de producción y/o maximizar el rendimiento de un dispositivo.
Todos los sistemas digitales se componen de dos funciones elementales: elementos de memoria para almacenar información y circuitos combinacionales que transforman esa información. Las máquinas de estados , como los contadores, son una combinación de elementos de memoria y circuitos lógicos combinacionales . Como los elementos de memoria son circuitos lógicos estándar, se seleccionan de un conjunto limitado de circuitos alternativos; por lo tanto, el diseño de funciones digitales se reduce a diseñar los circuitos de compuertas combinacionales e interconectarlos.
En general, la creación de instancias de circuitos lógicos a partir de abstracciones de alto nivel se denomina síntesis lógica , que puede llevarse a cabo a mano, pero normalmente se aplica algún método formal por computadora. En este artículo se resumen brevemente los métodos de diseño de circuitos lógicos combinacionales.
El punto de partida para el diseño de un circuito lógico digital es su funcionalidad deseada, derivada del análisis del sistema en su conjunto, del que el circuito lógico formará parte. La descripción puede formularse en forma algorítmica o mediante ecuaciones lógicas, pero también puede resumirse en forma de tabla. El siguiente ejemplo muestra una parte de dicha tabla para un controlador de pantalla de 7 segmentos que traduce el código binario de los valores de un dígito decimal en las señales que hacen que se iluminen los segmentos respectivos de la pantalla.
Segmentos de código de dígitos A B C D E F G 0 0000 1 1 1 1 1 1 0 -A- 1 0001 0 1 1 0 0 0 0 | | 2 0010 1 1 0 1 1 0 1 FB 3 0011 1 1 1 1 0 0 1 | | 4 0100 0 1 1 0 0 1 1 -G- 5 0101 1 0 1 1 0 1 1 | | 6 0110 1 0 1 1 1 1 1 CE 7 0111 1 1 1 0 0 0 0 | | 8 1000 1 1 1 1 1 1 1 -D- 9 1001 1 1 1 1 0 1 1
El proceso de implementación comienza con una fase de minimización lógica , que se describirá a continuación, con el fin de simplificar la tabla de funciones combinando los términos separados en otros más grandes que contengan menos variables.
A continuación, el resultado minimizado puede dividirse en partes más pequeñas mediante un procedimiento de factorización y, finalmente, se asigna a las celdas lógicas básicas disponibles de la tecnología de destino. Esta operación se conoce comúnmente como optimización lógica . [9]
Minimizar funciones booleanas a mano utilizando los mapas clásicos de Karnaugh es un proceso laborioso, tedioso y propenso a errores. No es adecuado para más de seis variables de entrada y solo es práctico para hasta cuatro variables, mientras que la compartición de términos de producto para múltiples funciones de salida es aún más difícil de llevar a cabo. [10] Además, este método no se presta a ser automatizado en forma de un programa de computadora. Sin embargo, dado que las funciones lógicas modernas generalmente no están limitadas a un número tan pequeño de variables, mientras que el costo, así como el riesgo de cometer errores, son prohibitivos para la implementación manual de funciones lógicas, el uso de computadoras se volvió indispensable.
El primer método alternativo que se hizo popular fue el método tabular desarrollado por Willard Quine y Edward McCluskey . Partiendo de la tabla de verdad para un conjunto de funciones lógicas, mediante la combinación de los minterms para los cuales las funciones están activas (la cubierta ON) o para los cuales el valor de la función es irrelevante (la cubierta Don't-Care o la cubierta DC) se compone un conjunto de implicantes primos . Finalmente, se sigue un procedimiento sistemático para encontrar el conjunto más pequeño de implicantes primos con los que se pueden realizar las funciones de salida. [11] [12]
Aunque este algoritmo de Quine-McCluskey es muy adecuado para ser implementado en un programa de computadora, el resultado aún está lejos de ser eficiente en términos de tiempo de procesamiento y uso de memoria. Agregar una variable a la función duplicará aproximadamente ambas, porque la longitud de la tabla de verdad aumenta exponencialmente con el número de variables. Un problema similar ocurre cuando se aumenta el número de funciones de salida de un bloque de función combinacional. Como resultado, el método de Quine-McCluskey es práctico solo para funciones con un número limitado de variables de entrada y funciones de salida.
Un enfoque diferente a este problema se sigue en el algoritmo ESPRESSO, desarrollado por Brayton et al. en la Universidad de California, Berkeley . [4] [3] Es un algoritmo eficiente en recursos y rendimiento cuyo objetivo es resolver el problema de minimización de lógica de dos niveles sin riesgos heurísticos. [13]
En lugar de expandir una función lógica en minterms, el programa manipula "cubos", que representan los términos del producto en las coberturas ON, DC y OFF de forma iterativa. Aunque no se garantiza que el resultado de la minimización sea el mínimo global , en la práctica se aproxima mucho, mientras que la solución siempre está libre de redundancia . En comparación con los otros métodos, este es esencialmente más eficiente, ya que reduce el uso de memoria y el tiempo de cálculo en varios órdenes de magnitud. Su nombre refleja la forma de preparar instantáneamente una taza de café fresco. Apenas hay restricciones en cuanto al número de variables, funciones de salida y términos del producto de un bloque de función combinacional. En general, por ejemplo, se manejan fácilmente decenas de variables con decenas de funciones de salida.
La entrada para ESPRESSO es una tabla de funciones de la funcionalidad deseada; el resultado es una tabla minimizada, que describe la función ON (activada) o OFF (desactivada), según las opciones seleccionadas. De forma predeterminada, los términos del producto se compartirán tanto como sea posible entre las distintas funciones de salida, pero se puede indicar al programa que gestione cada una de las funciones de salida por separado. Esto permite una implementación eficiente en matrices lógicas de dos niveles, como una PLA (matriz lógica programable) o una PAL (matriz lógica programable).
El algoritmo ESPRESSO ha demostrado ser tan exitoso que se ha incorporado como un paso estándar de minimización de funciones lógicas en prácticamente todas las herramientas de síntesis lógica contemporáneas . Para implementar una función en lógica multinivel, el resultado de la minimización se optimiza mediante factorización y se asigna a las celdas lógicas básicas disponibles en la tecnología de destino, ya sea que se trate de una matriz de puertas programables en campo (FPGA) o de un circuito integrado específico de la aplicación (ASIC).
El programa ESPRESSO original está disponible como código fuente en C en el sitio web de la Universidad de California, Berkeley . La última versión fue la 2.3 de 1988. [14] El programa ESPRESSO-AB y EQNTOTT (ecuación a tabla de verdad), una versión actualizada de ESPRESSO para sistemas POSIX modernos, está disponible en formato de archivo de distribución Linux Debian (.deb), así como el código fuente en C. La última versión fue la 9.0 de 2008. [15] En 2020, se trasladó a GitHub una versión compatible con Windows y C++20. [16]
Logic Friday es un programa gratuito para Windows que proporciona una interfaz gráfica para Espresso, así como para misII, otro módulo del paquete Octtools de Berkeley. Con Logic Friday, los usuarios pueden introducir una función lógica como tabla de verdad, ecuación o diagrama de compuertas, minimizar la función y luego ver los resultados en las otras dos representaciones. La última versión fue la 1.1.4 de 2012. [17]
Minilog es un programa gratuito para Windows que permite la minimización lógica aprovechando este algoritmo Espresso. Es capaz de generar una implementación de compuerta de dos niveles para un bloque de función combinacional con hasta 40 entradas y salidas o una máquina de estados sincrónicos con hasta 256 estados. Forma parte del paquete de diseño educativo Publicad .
ESPRESSO-IISOJS es una implementación de ESPRESSO-II en JavaScript para funciones de salida única. Emplea la propagación de unidades como una técnica de optimización adicional para los diversos algoritmos de ESPRESSO-II que se basan en el paradigma recursivo de una sola salida. Otra adición es permitir el control sobre cuándo se pueden generar literales, lo que se puede aprovechar para minimizar de manera efectiva las funciones lógicas de Kleene . [18]