Heuristischer Logik-Minimierer für Espresso - Espresso heuristic logic minimizer

Der Logikminimierer von ESPRESSO ist ein Computerprogramm, das heuristische und spezifische Algorithmen verwendet, um die Komplexität digitaler Logikgatterschaltungen effizient zu reduzieren . ESPRESSO-I wurde ursprünglich bei IBM von Robert K. Brayton et. al. 1982. und 1984 als ESPRESSO-II verbessert. Richard L. Rudell veröffentlichte später die Variante ESPRESSO-MV im Jahr 1986 und ESPRESSO-EXACT im Jahr 1987. Espresso hat viele Derivate inspiriert.

Einführung

Elektronische Geräte bestehen aus zahlreichen Blöcken digitaler Schaltungen, deren Kombination die erforderliche Aufgabe erfüllt. Die effiziente Implementierung von Logikfunktionen in Form von Logikgatterschaltungen (so dass nicht mehr Logikgatter als notwendig verwendet werden) ist notwendig, um die Produktionskosten zu minimieren und/oder die Leistung einer Vorrichtung zu maximieren.

Entwerfen digitaler Logikschaltungen

Alle digitalen Systeme bestehen aus zwei elementaren Funktionen: Speicherelementen zum Speichern von Informationen und kombinatorischen Schaltungen , die diese Informationen umwandeln. Zustandsmaschinen sind wie Zähler eine Kombination aus Speicherelementen und kombinatorischen Logikschaltungen . Da Speicherelemente standardmäßige Logikschaltungen sind, werden sie aus einem begrenzten Satz alternativer Schaltungen ausgewählt; Das Entwerfen digitaler Funktionen läuft also darauf hinaus, die kombinatorischen Gatterschaltungen zu entwerfen und sie miteinander zu verbinden.

Im Allgemeinen wird die Instanziierung von Logikschaltungen aus einer Abstraktion auf hoher Ebene als logische Synthese bezeichnet , die von Hand durchgeführt werden kann, aber normalerweise wird eine formale Methode per Computer angewendet. In diesem Artikel werden die Entwurfsmethoden für kombinatorische Logikschaltungen kurz zusammengefasst.

Ausgangspunkt für den Entwurf einer digitalen Logikschaltung ist ihre gewünschte Funktionalität, die aus der Analyse des Gesamtsystems abgeleitet wurde, zu der die Logikschaltung gehören soll. Die Beschreibung kann in irgendeiner algorithmischen Form oder durch logische Gleichungen angegeben werden, kann aber auch in Form einer Tabelle zusammengefasst werden. Das folgende Beispiel zeigt einen Teil einer solchen Tabelle für einen 7-Segment-Anzeigentreiber , der den Binärcode für die Werte einer Dezimalziffer in die Signale übersetzt, die das Aufleuchten der entsprechenden Segmente der Anzeige bewirken.

  Digit  Code        Segments
                   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 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 einer Logikminimierungsphase , die unten beschrieben wird, um die Funktionstabelle zu vereinfachen, indem die einzelnen Terme zu größeren zusammengefasst werden, die weniger Variablen enthalten.

Als nächstes kann das minimierte Ergebnis durch eine Faktorisierungsprozedur in kleinere Teile zerlegt werden und schließlich auf die verfügbaren Basislogikzellen der Zieltechnologie abgebildet werden. Diese Operation wird allgemein als logische Optimierung bezeichnet .

Klassische Minimierungsmethoden

Das manuelle Minimieren von Booleschen Funktionen unter Verwendung der klassischen Karnaugh-Maps ist ein mühsamer, langwieriger und fehleranfälliger Prozess. Es ist nicht für mehr als sechs Eingabevariablen und nur für bis zu vier Variablen geeignet, während die gemeinsame Nutzung von Produkttermen für mehrere Ausgabefunktionen noch schwieriger durchzuführen ist. Außerdem lässt sich dieses Verfahren nicht in Form eines Computerprogramms automatisieren. Da moderne Logikfunktionen jedoch im Allgemeinen nicht auf eine so geringe Anzahl von Variablen beschränkt sind, während die Kosten sowie das Risiko von Fehlern für die manuelle Implementierung von Logikfunktionen unerschwinglich sind, wurde der Einsatz von Computern unverzichtbar.

Die erste alternative Methode, die populär wurde, war die von Willard Quine und Edward McCluskey entwickelte tabellarische Methode . Beginnend mit der Wahrheitstabelle für einen Satz logischer Funktionen durch Kombinieren der Minterms, für die die Funktionen aktiv sind (die ON-Abdeckung) oder für die der Funktionswert irrelevant ist (die Don't-Care -Abdeckung oder DC-Abdeckung) eine Menge von Primimplikanten ist zusammengesetzt. Schließlich wird systematisch vorgegangen, um die kleinste Menge von Primimplikanten zu finden, mit der die Ausgabefunktionen realisiert werden können.

Obwohl sich dieser Quine-McCluskey-Algorithmus sehr gut für die Implementierung in ein Computerprogramm eignet, ist das Ergebnis in Bezug auf Verarbeitungszeit und Speichernutzung noch immer alles andere als effizient. Wenn Sie der Funktion eine Variable hinzufügen, werden beide ungefähr verdoppelt, da die Länge der Wahrheitstabelle mit der Anzahl der Variablen exponentiell zunimmt . Ein ähnliches Problem tritt auf, wenn die Anzahl der Ausgangsfunktionen eines kombinatorischen Funktionsblocks erhöht wird. Daher ist die Quine-McCluskey-Methode nur für Funktionen mit einer begrenzten Anzahl von Eingangsvariablen und Ausgangsfunktionen sinnvoll.

ESPRESSO-Algorithmus

Ein anderer Ansatz zu diesem Thema wird im ESPRESSO-Algorithmus verfolgt, der von Brayton et al. an der University of California, Berkeley . Es ist eine Ressource und Leistung effizienten Algorithmus zur Lösung der heuristischen Ziel Gefahr -freien Zwei-Ebenen - Logik Minimierungsproblem.

Anstatt eine logische Funktion in Minterms zu erweitern, manipuliert das Programm "Würfel", die die Produktterme in den ON-, DC- und OFF-Abdeckungen iterativ darstellen. Obwohl das Minimierungsergebnis nicht garantiert das globale Minimum ist , wird dieses in der Praxis sehr gut angenähert, während die Lösung immer redundanzfrei ist . Im Vergleich zu den anderen Methoden ist diese wesentlich effizienter und reduziert den Speicherverbrauch und die Rechenzeit um mehrere Größenordnungen. Sein Name spiegelt die Art wider, wie man sofort eine Tasse frischen Kaffee zubereitet. Die Anzahl der Variablen, Ausgangsfunktionen und Produktterme eines kombinatorischen Funktionsbausteins ist kaum eingeschränkt. Im Allgemeinen werden z. B. Dutzende von Variablen mit Dutzenden von Ausgabefunktionen leicht verarbeitet.

Die Eingabe für ESPRESSO ist eine Funktionstabelle der gewünschten Funktionalität; Das Ergebnis ist eine minimierte Tabelle, die abhängig von den ausgewählten Optionen entweder die ON-Cover oder die OFF-Cover der Funktion beschreibt. Standardmäßig werden die Produktbegriffe so weit wie möglich von den verschiedenen Ausgabefunktionen geteilt, aber das Programm kann angewiesen werden, jede der Ausgabefunktionen separat zu behandeln. Dies ermöglicht eine effiziente Implementierung in zweistufigen Logikarrays wie einem PLA (Programmable Logic Array) oder einem PAL (Programmable Array Logic).

Der ESPRESSO-Algorithmus erwies sich als so erfolgreich, dass er als Standardschritt zur Minimierung von Logikfunktionen in praktisch jedes moderne Logiksynthesewerkzeug integriert wurde . Zur Implementierung einer Funktion in Multi-Level-Logik wird das Minimierungsergebnis durch Faktorisierung optimiert und auf die verfügbaren Basislogikzellen in der Zieltechnologie abgebildet, sei es ein feldprogrammierbares Gate-Array (FPGA) oder ein anwendungsspezifischer integrierter Schaltkreis ( ASIC).

Software

ESPRESSO

Das ursprüngliche ESPRESSO- Programm ist als C- Quellcode auf der Website der University of California, Berkeley verfügbar. Die letzte Version war Version 2.3 vom 1988. Das Programm ESPRESSO-AB und EQNTOTT (Equation to Truth Table), eine aktualisierte Version von ESPRESSO für moderne POSIX- Systeme, ist im Dateiformat der Debian- Linux-Distribution (.deb) sowie im Quellcode C verfügbar Code. Die letzte Version war Version 9.0 vom 2008.

Logik Freitag

Logic Friday ist ein kostenloses Windows- Programm, das eine grafische Schnittstelle zu Espresso bietet, sowie zu misII, einem weiteren Modul des Berkeley Octtools-Pakets. Mit Logic Friday können Benutzer eine logische Funktion als Wahrheitstabelle, Gleichung oder Gatterdiagramm eingeben, die Funktion minimieren und dann die Ergebnisse in den beiden anderen Darstellungen anzeigen. Die letzte Version war Version 1.1.4 vom 2012.

Minilog

Minilog ist ein kostenloses Windows-Programm, das mithilfe dieses Espresso-Algorithmus logische Minimierung bietet. Es ist in der Lage, eine zweistufige Gatterimplementierung für einen kombinatorischen Funktionsblock mit bis zu 40 Ein- und Ausgängen oder eine synchrone Zustandsmaschine mit bis zu 256 Zuständen zu generieren . Es ist Teil des Publicad- Pakets für pädagogisches Design.

ESPRESSO-IISOJS

ESPRESSO-IISOJS ist eine JavaScript-Implementierung von ESPRESSO-II für einzelne Ausgabefunktionen. Es verwendet Unit Propagation als zusätzliche Optimierungstechnik für die verschiedenen Algorithmen in ESPRESSO-II, die auf dem unat rekursiven Paradigma basieren. Ein weiterer Zusatz ist die Kontrolle darüber, wann Literale erzeugt werden können, was ausgenutzt werden kann, um Kleene-Logikfunktionen effektiv zu minimieren .

Verweise

Weiterlesen

• Eschermann, Bernhard (Mai 1993). Funktionaler Entwurf digitaler Schaltungen - Methoden und CAD-Techniken [ Funktionelles Design digitaler Schaltungen - Methoden und CAD - Techniken ]. Springer-Lehrbuch. Springer-Verlag . S. 136–137, 140–141. ISBN 9-783540-56788-2. ISBN  3-540-56788-7 .