Minimizador de lógica heurística Espresso

Todos los sistemas digitales se componen de dos funciones elementales: elementos de memoria para almacenar información y circuitos combinacionales que la transforman. Las máquinas de estados , 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 tanto, el diseño de funciones digitales se reduce a diseñar los circuitos de puertas combinacionales e interconectarlos.

En general, la instanciación de circuitos lógicos a partir de abstracciones de alto nivel se denomina síntesis lógica , la cual puede realizarse manualmente, aunque normalmente se aplica algún método formal mediante ordenador. En este artículo se resumen brevemente los métodos de diseño para 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 cual formará parte el circuito lógico. La descripción puede expresarse mediante algoritmos o ecuaciones lógicas, o bien resumirse en una tabla. El siguiente ejemplo muestra 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 activan los segmentos correspondientes de la pantalla.

 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 EC 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á más adelante, 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 objetivo. Esta operación se conoce comúnmente como optimización lógica . ^{[ 9 ]}

Minimizar manualmente funciones booleanas mediante los mapas de Karnaugh clásicos es un proceso laborioso, tedioso y propenso a errores. No es adecuado para más de seis variables de entrada y resulta práctico solo para hasta cuatro, 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 la automatización mediante un programa informático. Sin embargo, dado que las funciones lógicas modernas generalmente no se limitan a un número tan reducido de variables, y que el coste y el riesgo de cometer errores son prohibitivos para la implementación manual de funciones lógicas, el uso de ordenadores se ha vuelto indispensable.

El primer método alternativo que se popularizó 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, al combinar los minitérminos para los cuales las funciones son activas (la cobertura ON) o para los cuales el valor de la función es irrelevante (la cobertura Don'tCare o 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 ]}

Si bien el algoritmo de Quine-McCluskey es muy adecuado para su implementación en un programa informático, el resultado dista mucho de ser eficiente en términos de tiempo de procesamiento y uso de memoria. Añadir una variable a la función prácticamente duplica ambos parámetros, ya que la longitud de la tabla de verdad aumenta exponencialmente con el número de variables. Un problema similar se presenta al aumentar el número de funciones de salida de un bloque de funciones combinacionales. En consecuencia, el método de Quine - McCluskey solo resulta práctico para funciones con un número limitado de variables de entrada y funciones de salida.

Un enfoque diferente para 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 destinado a resolver el problema heurístico de minimización lógica de dos niveles sin riesgo . ^{[ 13 ]}

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 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 muy bien, y la solución siempre está libre de redundancia . Comparado con 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. Prácticamente no hay restricciones en cuanto al número de variables, funciones de salida y términos de 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 con la funcionalidad deseada; el resultado es una tabla minimizada que describe la función (activada o desactivada), según las opciones seleccionadas. Por defecto, las distintas funciones de salida comparten los términos del producto en la medida de lo posible, pero el programa puede configurarse para gestionar cada función de forma independiente. 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 eficaz que se ha incorporado como paso estándar de minimización de funciones lógicas en prácticamente cualquier herramienta de síntesis lógica actual . 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 una matriz de puertas programables en campo (FPGA) o un circuito integrado de aplicación específica (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 publicada 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 Debian Linux (.deb), así como el código fuente en C. La última versión publicada fue la 9.0, de 2008. ^{[ 15 ]} Una versión compatible con Windows y C++20 fue portada a GitHub en 2020. ^{[ 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 Berkeley Octtools. Con Logic Friday, los usuarios pueden introducir una función lógica como una tabla de verdad, una ecuación o un diagrama de compuertas, minimizar la función y, a continuación, visualizar 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 minimiza la lógica mediante el algoritmo Espresso. Permite generar una implementación de compuertas de dos niveles para un bloque de función combinacional con hasta 40 entradas y salidas, o una máquina de estados síncrona con hasta 256 estados. Forma parte del paquete de diseño educativo Publicad .

ESPRESSO-IISOJS es una implementación en JavaScript de ESPRESSO-II para funciones de salida única. Emplea la propagación de unidades como técnica de optimización adicional para los diversos algoritmos de ESPRESSO-II que se basan en el paradigma recursivo unate. Otra adición es que permite controlar cuándo se pueden generar literales, lo que puede aprovecharse para minimizar eficazmente las funciones lógicas de Kleene . ^{[ 18 ]}

Python EDA es una biblioteca de Python para la automatización del diseño electrónico que incluye enlaces para la minimización de la lógica Espresso. ^{[ 19 ]}