Espresso heuristic logic minimizer

Das Espresso -Logik Minimierer ist ein Computerprogramm verwendet Heuristik und spezifisch Algorithmen zur effizienten Reduzierung der Komplexität von digital Logik -Tor Schaltungen.[1] Espresso-I wurde ursprünglich bei entwickelt IBM durch Robert K. Brayton et al. 1982.[2][3] und verbesserte sich 1984 als Espresso-II.[4][5] Richard L. Rudell veröffentlichte später 1986 den Varianten Espresso-MV[6] und Espresso-passend im Jahr 1987.[7][8][5] Espresso hat viele Derivate inspiriert.

Einführung

Elektronische Geräte bestehen aus zahlreichen Blöcken digitaler Schaltungen, von denen die Kombination die erforderliche Aufgabe ausführt. Die effiziente Umsetzung von Logikfunktionen in Form von Logik -Tor Schaltkreise (so dass keine logischen Gates verwendet werden als notwendig sind) sind erforderlich, um die Produktionskosten zu minimieren und/oder die Leistung eines Geräts zu maximieren.

Entwerfen digitaler Logikschaltungen

Alle digitalen Systeme bestehen aus zwei Elementarfunktionen: Speicherelemente zum Speichern von Informationen und Kombinationsschaltungen das verwandelt diese Informationen. Staatsmaschinen, wie Zähler, eine Kombination von Speicherelementen und Kombinationslogik Schaltungen. Da Speicherelemente Standard -Logikkreise sind, werden sie aus einer begrenzten Reihe alternativer Schaltungen ausgewählt. Das Entwerfen digitaler Funktionen hängt also von der Gestaltung der Kombinationsgate -Schaltungen und der Zusammenhänge von ihnen ab.

Im Allgemeinen wird die Instanziierung von Logikschaltungen aus der Abstraktion auf hoher Ebene als bezeichnet Logiksynthese, die von Hand ausgeführt werden kann, aber normalerweise eine formelle Methode mit dem Computer angewendet werden. In diesem Artikel werden die Entwurfsmethoden für Kombinationslogikschaltungen kurz zusammengefasst.

Der Ausgangspunkt für die Gestaltung eines digitalen Logikkreises ist die gewünschte Funktionalität, die sich aus der Analyse des gesamten Systems abgeleitet hat. Die Beschreibung kann in einer algorithmischen Form oder in Logikgleichungen angegeben werden, kann jedoch auch in Form einer Tabelle zusammengefasst werden. Das folgende Beispiel zeigt einen Teil einer solchen Tabelle für a 7-Segment-Anzeige Treiber, der den Binärcode für die Werte einer Dezimalzahl in die Signale übersetzt, die die jeweiligen Segmente des Displays beleuchten.

  Zifferncode -Segmente 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 F B 3 0011 1 1 1 1 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 E C 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

Der Implementierungsprozess beginnt mit a logische Minimierung Phase, um nachstehend beschrieben zu werden, um die Funktionstabelle zu vereinfachen, indem die getrennten Begriffe in größere Variablen kombiniert werden.

Als nächstes kann das minimierte Ergebnis durch ein Faktorisierungsverfahren in kleineren Teilen aufgeteilt werden und wird schließlich auf die verfügbaren grundlegenden Logikzellen der Zieltechnologie abgebildet. Diese Operation wird allgemein als als bezeichnet logische Optimierung.[9]

Klassische Minimierungsmethoden

Minimierung Boolesche Funktionen von Hand mit der Klassiker Karnaugh Maps ist ein mühsamer, mühsamer und fehleranfälliger Prozess. Es ist nicht für mehr als sechs Eingangsvariablen geeignet und nur für bis zu vier Variablen praktisch, während die Produktbegriff für mehrere Ausgangsfunktionen noch schwieriger ist.[10] Darüber hinaus eignet sich diese Methode nicht, um in Form eines Computerprogramms automatisiert zu werden. Da jedoch moderne Logikfunktionen im Allgemeinen nicht auf eine so kleine Anzahl von Variablen beschränkt sind, während die Kosten sowie das Risiko von Fehlern für die manuelle Implementierung der Logikfunktionen unerschwinglich sind, wurde die Verwendung von Computern unverzichtbar.

Die erste alternative Methode, um populär zu werden, war die tabellarische Methode, die von entwickelt wurde von Willard Quine und Edward McCluskey. Beginnend mit dem Wahrheitstabelle für eine Reihe von Logikfunktionen durch Kombination der Minterms für die die Funktionen aktiv sind (die On-Cover) oder für die der Funktionswert irrelevant ist (die NICHT-Cover oder DC-Cover) ein Satz von Prime Implicants ist komponiert. Schließlich wird ein systematisches Verfahren befolgt, um den kleinsten Satz von Prime Implicants zu finden, mit denen die Ausgangsfunktionen realisiert werden können.[11][12]

Obwohl dieses Quine -McCluskey -Algorithmus Ist das Ergebnis sehr gut geeignet, um in einem Computerprogramm implementiert zu werden. Das Hinzufügen einer Variablen zur Funktion wird beide ungefähr doppelt exponentiell mit der Anzahl der Variablen. Ein ähnliches Problem tritt bei der Erhöhung der Anzahl der Ausgangsfunktionen eines Kombinationsfunktionsblocks auf. Infolgedessen ist die Quine -McCluskey -Methode nur für Funktionen mit einer begrenzten Anzahl von Eingangsvariablen und Ausgangsfunktionen praktisch.

Espresso -Algorithmus

Ein anderer Ansatz für dieses Problem wird im Espresso -Algorithmus verfolgt, der von Brayton et al. Bei der Universität von Kalifornien, Berkeley.[4][3] Es handelt sich um einen Ressourcen- und leistungseffizienten Algorithmus, der darauf abzielt, die Heuristik zu lösen Gefahr-Freie zweistufige Logik-Minimierungsprobleme.[13]

Anstatt eine Logikfunktion in Minterms zu erweitern, manipuliert das Programm "Würfel" und repräsentiert die Produktbegriffe in den iterativen, dc- und off-Deckungen. Obwohl das Minimierungsergebnis nicht garantiert das ist globales MinimumIn der Praxis wird dies sehr eng angenähert, während die Lösung immer frei von Redundanz. Im Vergleich zu den anderen Methoden ist diese im Wesentlichen effizienter und verkürzt die Speicherverwendung und Berechnungszeit um mehrere Größenordnungen. Sein Name spiegelt den Weg wider, sofort eine Tasse frischer Kaffee zu machen. Die Anzahl der Variablen, Ausgangsfunktionen und Produktbedingungen eines Kombinationsfunktionsblocks ist kaum eine Beschränkung. Im Allgemeinen z.B. Zehn Variablen mit zehn Ausgangsfunktionen werden leicht behandelt.

Die Eingabe für Espresso ist eine Funktionstabelle der gewünschten Funktionalität. Das Ergebnis ist eine minimierte Tabelle, die je nach ausgewählten Optionen entweder die Einstellung oder die Off-Cover der Funktion beschreibt. Standardmäßig werden die Produktbegriffe von den verschiedenen Ausgabefunktionen so weit wie möglich geteilt, das Programm kann jedoch angewiesen werden, jede der Ausgangsfunktionen separat zu verarbeiten. Dies ermöglicht eine effiziente Implementierung in zweistufigen Logikarrays wie a PLA (Programmierbares Logikarray) oder a KUMPEL (Programmierbare Array -Logik).

Der Espresso -Algorithmus erwies sich als so erfolgreich, dass er als Standard -Logikfunktionsminimierungsschritt in praktisch alle Zeitgenossen aufgenommen wurde Logiksynthese Werkzeug. Für die Implementierung einer Funktion in mehrstufiger Logik wird das Minimierungsergebnis durch Faktorisierung optimiert und auf die verfügbaren grundlegenden Logikzellen in der Zieltechnologie abgebildet, unabhängig davon Feldprogrammierbares Gate-Array (FPGA) oder ein Anwendungsspezifische integrierte Schaltung (ASIC).

Software

ESPRESSO

Das Original ESPRESSO Programm ist verfügbar als C Quellcode aus dem Universität von Kalifornien, Berkeley Webseite. Die letzte Veröffentlichung war Version 2.3 vom 1988.[14] Das Espresso-ab und Eqntott (Gleichung zu Wahrheitstabelle) Programm, eine aktualisierte Version von Espresso für Moderne Posix Systeme, ist in erhältlich Debian Linux -Verteilung (.DEB) Dateiformat auch den C -Quellcode. Die letzte Veröffentlichung war Version 9.0 vom 2008.[15] Ein Windows und C ++ 20 kompatibel wurden 2020 auf Github portiert.[16]

Logik Freitag

Logik Freitag ist frei Fenster Programm, das eine grafische Schnittstelle zu Espresso sowie zu Misii bietet, ein weiteres Modul im Berkeley OctTools -Paket. Mit Logic Friday können Benutzer eine Logikfunktion als Wahrheitstabelle, Gleichung oder Gate -Diagramm eingeben, die Funktion minimieren und dann die Ergebnisse in beiden anderen beiden Darstellungen anzeigen. Die letzte Veröffentlichung war Version 1.1.4 vom 2012.[17]

Minilog

Minilog ist ein kostenloses Windows -Programm, das logische Minimierung bietet, die diesen Espresso -Algorithmus ausnutzt. Es ist in der Lage, eine zweistufige Gate-Implementierung für einen Kombinationsfunktionsblock mit bis zu 40 Eingängen und Ausgängen oder a zu erzeugen Synchronstatusmaschine mit bis zu 256 Staaten. Es ist Teil der Öffentlich Bildungsdesign -Paket.

Espresso-iisojs

Espresso-iisojs ist eine JavaScript-Implementierung von Espresso-II für einzelne Ausgabefunktionen. Es gebraucht Einheitsausbreitung Als zusätzliche Optimierungstechnik für die verschiedenen Algorithmen in Espresso-II, die auf dem UNATE-rekursiven Paradigma basieren. Eine andere Ergänzung ist die Kontrolle über die Kontrolle, wenn Literale angehoben werden können, was genutzt werden kann, um effektiv zu minimieren Kleene Logik Funktionen.[18]

Verweise

  1. ^ Hayes, John Patrick (1993). Digitales Logikdesign. Addison Wesley. ISBN 0-201-15461-7.
  2. ^ Brayton, Robert King; Hachtel, Gary D.; Hemachandra, Lane A.; Newton, A. Richard; Sangiovanni-Vincentelli, Alberto Luigi M. (1982). "Ein Vergleich von Logikminimierungsstrategien mit Espresso: Ein APL -Programmpaket für partitionierte Logiksimulation". Verfahren der IEEE Internationales Symposium über Schaltkreise und Systeme, 1982. New York, New York, USA: IEEE: 42–48.
  3. ^ a b "Robert K. Brayton; emeritierter Professor, Professor an der Graduiertenschule". Universität von Kalifornien, Berkeley. 2018-09-23. Archiviert vom Original am 2018-09-23. Abgerufen 2018-09-23.
  4. ^ a b Brayton, Robert King; Hachtel, Gary D.; McMullen, Curtis Tracy; Sangiovanni-Vincentelli, Alberto Luigi M. (1984). Logikminimierungsalgorithmen für die VLSI -Synthese (9. Druck 2000, 1. Aufl.). Boston, Massachusetts, USA: KLUWER Academic Publishers. ISBN 0-89838-164-9.
  5. ^ a b Bolton, Martin (1990). "4.3.3 Espresso-II". Geschrieben an der University of Bristol, Bristol, Großbritannien. In Dagless, Erik L. (Hrsg.). Digitales Systemdesign mit programmierbarer Logik. Electronic Systems Engineering Series (1 Ed.). Wokingham, UK: Addison-Wesley Publishers Ltd. S. 112, 115–116. ISBN 0-201-14545-6. Lccn 90000007. ISBN978-0-201-14545-8 ARK:/13960/T2F83P38R. Abgerufen 2021-04-17.{{}}: CS1 Wartung: URL-Status (Link) (xiv+379+1 Seiten)
  6. ^ Rudell, Richard L. (1986-06-05). Mehrfach bewertete logische Minimierung für die PLA-Synthese (PDF). Memorandum Nr. UCB/ERL M86-65. Berkeley, USA.
  7. ^ Rudell, Richard L.; Sangiovanni-Vincentelli, Alberto Luigi M. (September 1987). "Mehrfachwerte logische Minimierung für die PLA-Optimierung". IEEE-Transaktionen zum computergestützten Design. 6 (5): 727–750.
  8. ^ Rudell, Richard L. (April 1989). Logiksynthese für VLSI -Design (Doktorarbeit). Elektronikforschungslabor, College of Engineering, Universität von Kalifornien, Berkeley, USA. (Espresso-passend)
  9. ^ De Micheli, Giovanni (1994). Synthese und Optimierung digitaler Schaltungen. McGraw-Hill Science Engineering. ISBN 0-07-016333-2.
  10. ^ Lewin, Douglas (1985). Entwurf von Logiksystemen. Van Nostrand (VEREINIGTES KÖNIGREICH). ISBN 0-442-30606-7.
  11. ^ Katz, Randy Howard; Borriello, Gaetano (1994). Zeitgenössisches Logikdesign. Das Benjamin/Cummings -Verlagsunternehmen. ISBN 0-8053-2703-7.
  12. ^ Lala, Parag K. (1996). Praktisches digitales Logikdesign und Tests. Prentice Hall. ISBN 0-02-367171-8.
  13. ^ Theobald, Michael; Nowick, Steven M. "Schnelle heuristische und exakte Algorithmen für zweistufige gefährdungsfreie logische Minimierung". Abteilung für Computerwissenschaften, Universität von Columbia. Abgerufen 2021-10-04.{{}}: CS1 Wartung: URL-Status (Link)
  14. ^ "Espresso C Quellcode (1988)". Universität von Kalifornien, Berkeley. 2018-09-21. Archiviert vom Original am 2018-09-21. Abgerufen 2018-09-21.
  15. ^ "Espresso-EB / Eqntott C Quellcode und Programm (2008)". Google -Code. 2018-09-21. Archiviert vom Original am 2018-09-21. Abgerufen 2018-09-21.
  16. ^ "Espresso Heuristic Logic Minimizer C ++ 20 Windows -Quelle".
  17. ^ "Logic Friday Program (2012)". Sontrak. 2018-09-21. Archiviert von das Original Am 2013-10-22. Abgerufen 2018-09-21.
  18. ^ "Espresso-iisojs".

Weitere Lektüre

  • Eschermann, Bernhard (Mai 1993). Funktionaler entwurf digitaler schaltungen - methoden und cad -techniken [Funktionales Design digitaler Schaltungen - Methoden und CAD -Techniken]. Springer-Lehrbuch (auf Deutsch). Springer-Verlag. S. 136–137, 140–141. ISBN 9-783540-56788-2. ISBN3-540-56788-7.