El minimizador lógico ESPRESSO es un programa de computadora 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. Alabama. en 1982. [2] [3] y mejorado como ESPRESSO-II en 1984. [4] [5] Richard L. Rudell publicó más tarde la variante ESPRESSO-MV en 1986 [6] y ESPRESSO-EXACT en 1987. [7] [8] [5] El espresso ha inspirado muchos derivados.
Introducción
Los dispositivos electrónicos se componen de 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 manera 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.
Diseño de circuitos lógicos digitales
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 estado , como los contadores, son una combinación de elementos de memoria y circuitos lógicos combinacionales . Dado que los elementos de memoria son circuitos lógicos estándar, se seleccionan de un conjunto limitado de circuitos alternativos; por lo que el diseño de funciones digitales se reduce a diseñar los circuitos de compuerta combinacionales e interconectarlos.
En general, la instanciación de circuitos lógicos a partir de la abstracción de alto nivel se conoce como síntesis lógica , que se puede realizar a mano, pero generalmente 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, habiendo derivado del análisis del sistema en su conjunto, del que forma parte el circuito lógico. La descripción puede expresarse en alguna 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 para los valores de un dígito decimal en las señales que hacen que los segmentos respectivos de la pantalla se iluminen.
Segmentos de código de dígitos ABCDEFG 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, para simplificar la tabla de funciones combinando los términos separados en otros más grandes que contienen menos variables.
A continuación, el resultado minimizado se puede dividir en partes más pequeñas mediante un procedimiento de factorización y finalmente se mapea en las celdas lógicas básicas disponibles de la tecnología objetivo. Esta operación se conoce comúnmente como optimización lógica . [9]
Métodos clásicos de minimización
Minimizar las 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 es práctico solo para hasta cuatro variables, mientras que el uso compartido de términos de producto para múltiples funciones de salida es aún más difícil de realizar. [10] Además, este método no se presta a ser automatizado en forma de 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 y el riesgo de cometer errores es prohibitivo para la implementación manual de funciones lógicas, el uso de computadoras se volvió indispensable.
El primer método alternativo que se popularizó fue el método tabular desarrollado por Willard Quine y Edward McCluskey . Comenzando con la tabla de verdad para un conjunto de funciones lógicas, combinando los términos mínimos 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 está muy bien adaptado 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. Se produce un problema similar al aumentar el número de funciones de salida de un bloque de funciones combinacionales. Como resultado, el método Quine-McCluskey es práctico solo para funciones con un número limitado de variables de entrada y funciones de salida.
Algoritmo ESPRESSO
Se sigue un enfoque diferente a este tema en el algoritmo ESPRESSO, desarrollado por Brayton et al. en la Universidad de California, Berkeley . [4] [3] En lugar de expandir una función lógica en minitérminos, el programa manipula "cubos", que representan los términos del producto en las cubiertas ON-, DC- y OFF- iterativamente. Aunque no se garantiza que el resultado de la minimización sea el mínimo global , en la práctica esto 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, reduciendo 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é recién hecho. Apenas hay restricciones al número de variables, funciones de salida y términos de producto de un bloque de funciones combinacionales. En general, por ejemplo, se tratan 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 cubierta ON o la cubierta OFF de la función, según las opciones seleccionadas. Por defecto, los términos del producto serán compartidos tanto como sea posible por las distintas funciones de salida, pero se puede indicar al programa que maneje cada una de las funciones de salida por separado. Esto permite una implementación eficiente en matrices lógicas de dos niveles, como PLA (matriz lógica programable) o PAL (matriz lógica programable).
El algoritmo ESPRESSO demostró ser tan exitoso que se ha incorporado como un paso de minimización de funciones lógicas estándar en prácticamente cualquier herramienta de síntesis lógica contemporánea . Para implementar una función en lógica multinivel, el resultado de 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 un circuito integrado específico de la aplicación ( ASIC).
Software
CAFÉ EXPRÉS
El programa ESPRESSO original está disponible como código fuente C en el sitio web de la Universidad de California, Berkeley . La última versión fue la versión 2.3 con fecha de 1988. [13] El programa ESPRESSO-AB y EQNTOTT (tabla de ecuaciones a la verdad), una versión actualizada de ESPRESSO para sistemas POSIX modernos, también está disponible en formato de archivo de distribución Debian Linux (.deb). el código fuente de C. La última versión fue la versión 9.0 de 2008. [14]
Viernes Lógico
Logic Friday es un programa gratuito de Windows que proporciona una interfaz gráfica para Espresso, así como para misII, otro módulo del paquete Berkeley Octtools. Con Logic Friday, los usuarios pueden ingresar una función lógica como una tabla de verdad, ecuación o diagrama de puerta, minimizar la función y luego ver los resultados en las otras dos representaciones. El último lanzamiento fue la versión 1.1.4 de 2012. [15]
Minilog
Minilog es un programa gratuito de Windows que proporciona una minimización lógica aprovechando este algoritmo Espresso. Puede generar una implementación de puerta de dos niveles para un bloque de función combinacional con hasta 40 entradas y salidas o una máquina de estado síncrona con hasta 256 estados. Es parte del paquete de diseño educativo de Publicad .
ESPRESSO-IISOJS
ESPRESSO-IISOJS es una implementación de JavaScript de ESPRESSO-II para funciones de salida única. Emplea la propagación unitaria como una técnica de optimización adicional para los diversos algoritmos en ESPRESSO-II que se basan en el paradigma recursivo unte. Otra adición es permitir el control sobre cuándo se pueden generar literales que se pueden explotar para minimizar de manera efectiva las funciones lógicas de Kleene . [dieciséis]
Referencias
- ^ Hayes, John Patrick (1993). Diseño de lógica digital . Addison Wesley . ISBN 0-201-15461-7.
- ^ Brayton, Robert King ; Hachtel, Gary D .; Hemachandra, Lane A .; Newton, A. Richard; Sangiovanni-Vincentelli, Alberto Luigi M. (1982). "Una comparación de estrategias de minimización lógica utilizando ESPRESSO: un paquete de programa APL para simulación lógica particionada". Actas del Simposio Internacional IEEE sobre Circuitos y Sistemas , 1982 . Nueva York, Nueva York, EE. UU .: IEEE : 42–48.
- ^ a b "Robert K. Brayton; profesor emérito, profesor de la escuela de posgrado" . Universidad de California, Berkeley . 2018-09-23. Archivado desde el original el 23 de septiembre de 2018 . Consultado el 23 de septiembre de 2018 .
- ^ a b Brayton, Robert King ; Hachtel, Gary D .; McMullen, Curtis Tracy ; Sangiovanni-Vincentelli, Alberto Luigi M. (1984). Algoritmos lógicos de minimización para síntesis VLSI (novena edición 2000, primera edición). Boston, Massachusetts, EE.UU .: Kluwer Academic Publishers . ISBN 0-89838-164-9.
- ^ a b Bolton, Martin (1990). "4.3.3 ESPRESSO-II". Escrito en la Universidad de Bristol, Bristol, Reino Unido. En Dagless, Erik L. (ed.). Diseño de Sistemas Digitales con Lógica Programable . Serie de Ingeniería de Sistemas Electrónicos (1 ed.). Wokingham, Reino Unido: Addison-Wesley Publishers Ltd. págs. 112, 115-116. ISBN 0-201-14545-6. LCCN 90000007 . ISBN 978-0-201-14545-8 arca: / 13960 / t2f83p38r . Consultado el 17 de abril de 2021 . (xiv + 379 + 1 páginas)
- ^ Rudell, Richard L. (5 de junio de 1986). Minimización de la lógica de múltiples valores para la síntesis de PLA (PDF) . Memorándum No. UCB / ERL M86-65 . Berkeley, Estados Unidos.
- ^ Rudell, Richard L .; Sangiovanni-Vincentelli, Alberto Luigi M. (septiembre de 1987). "Minimización lógica de múltiples valores para la optimización de PLA". Transacciones IEEE sobre diseño asistido por computadora . 6 (5): 727–750.
- ^ Rudell, Richard L. (abril de 1989). Síntesis lógica para el diseño VLSI (tesis doctoral). Laboratorio de Investigación en Electrónica, Facultad de Ingeniería, Universidad de California , Berkeley, EE. UU. (EXPRESO-EXACTO)
- ^ De Micheli, Giovanni (1994). Síntesis y Optimización de Circuitos Digitales . Ingeniería científica de McGraw-Hill . ISBN 0-07-016333-2.
- ^ Lewin, Douglas (1985). Diseño de Sistemas Lógicos . Van Nostrand (Reino Unido). ISBN 0-442-30606-7.
- ^ Katz, Randy Howard ; Borriello, Gaetano (1994). Diseño de lógica contemporánea . The Benjamin / Cummings Publishing Company . ISBN 0-8053-2703-7.
- ^ Lala, Parag K. (1996). Diseño y pruebas prácticas de lógica digital . Prentice Hall . ISBN 0-02-367171-8.
- ^ "Código fuente de Espresso C (1988)" . Universidad de California, Berkeley . 2018-09-21. Archivado desde el original el 21 de septiembre de 2018 . Consultado el 21 de septiembre de 2018 .
- ^ "Programa y código fuente de Espresso-eb / eqntott C (2008)" . Código de Google . 2018-09-21. Archivado desde el original el 21 de septiembre de 2018 . Consultado el 21 de septiembre de 2018 .
- ^ "Programa Logic Friday (2012)" . sontrak . 2018-09-21. Archivado desde el original el 22 de octubre de 2013 . Consultado el 21 de septiembre de 2018 .
- ^ "Espresso-IISOJS" .
Otras lecturas
- Eschermann, Bernhard (mayo de 1993). Funktionaler Entwurf digitaler Schaltungen - Methoden und CAD-Techniken [ Diseño funcional de circuitos digitales - Métodos y técnicas CAD ]. Springer-Lehrbuch (en alemán). Springer-Verlag . págs. 136-137, 140-141. ISBN 9-783540-56788-2. ISBN 3-540-56788-7 .