Skip to main content
main-content

Inhaltsverzeichnis

Frontmatter

Einleitung

Zusammenfassung
Der rasant fortschreitende Wandel von der Industrie- zur Informations-, Kommunikations- und Wissensgesellschaft mit steigender Mobilität, die neuen Anwendungen bei Multimedia und Telematik, die Innovationssprünge auf dem PC-Markt und der weiter steigende Halbleiter-Anteil in elektronischen Geräten aller Art lassen den Halbleitermarkt sich in den nächsten Jahren weiter positiv entwickeln und überdurchschnittliche Zuwachsraten erwarten. Neue umsatzträchtige Märkte öffnen sich der Halbleiterzunft bei Identifizierungssystemen und intelligenten Chipkarten. Elektronische Wegfahrsperren im Automobil, Krankenscheine auf Plastikkarte und intelligente Fahrscheine sind nur einige Alltagsbeispiele einer Reihe von Einsatzfeldern, die eine vielversprechende Entwicklung für Halbleiterhersteller und Chipdesigner vermuten lassen.
Paul Molitor, Christoph Scholl

1. Verband, Boolesche Algebra, Boolesche Funktionen

Zusammenfassung
Das zentrale mathematische Werkzeug beim Entwurf von kombinatorischen Schaltungen ist die durch Boole im Jahre 1847 [Boo47] vorgestellte ”Algebra of logic”, heute bekannt unter dem Namen Boolesche Algebra. Der Physiker P. Ehrenfest schlug 1910 erstmalig vor, die Boolesche Algebra im Rahmen des Entwurfs digitaler Systeme einzusetzen [Ehr10]. Erste Methoden der Anwendung der Booleschen Algebra beim Schaltungsentwurf wurden 1938 von Shannon vorgestellt [Sha38].
Paul Molitor, Christoph Scholl

2. Technologien, Modelle und Kostenmaße

Zusammenfassung
In diesem Kapitel wollen wir die heute gebräuchlichsten Technologien beim Entwurf anwendungsspezifischer Schaltungen kurz vorstellen. Es sind dies ROMs (Read Only Memories) und PLAs (Programmable Logic Arrays), Standardzellen- und Sea-of-Gate-Entwürfe, sowie seit kurzem die FPGAs (Field Programmable Gate Arrays). Wir werden bei der Vorstellung dieser Technologien nur soweit auf Details eingehen, wie es für das Verständnis der bei der logischen Synthese verwendeten Modelle und Kostenmaße notwendig ist.
Paul Molitor, Christoph Scholl

3. Exakte Verfahren zur 2-stufigen Logikminimierung

Zusammenfassung
Nachdem wir in den letzten beiden Kapiteln die grundlegenden Begriffe für die in diesem Buch behandelte Thematik durchgegangen sind und praxisrelevante Modelle und Datenstrukturen für Boolesche Funktionen vorgestellt haben, wollen wir nun versuchen, minimale Darstellungen von Booleschen Funktionen zu konstruieren. Wir beginnen mit der zweistufigen Logiksynthese, also mit der Konstruktion eines Polynoms p = (p1, …, p m ) für eine Boolesche Funktion f = (f1, …, f m )aus B n,m mit minimalen Kosten. Wie in dem Kapitel über Technologien, Modelle und Kostenmaße in Abschnitt 2.2.2 motiviert, ist das Problem der zweistufigen Logiksynthese wie folgt definiert.
Paul Molitor, Christoph Scholl

4. Heuristische Verfahren zur 2-stufigen Logikminimierung

Zusammenfassung
Die im Kapitel 3 vorgestellten Verfahren zur Berechnung eines Minimalpolynoms einer allgemeinen Booleschen Funktion f sind sehr aufwendig.
Paul Molitor, Christoph Scholl

5. Minimierung binärer Entscheidungsgraphen

Zusammenfassung
Reduzierte geordnete binäre Entscheidungsgraphen, also BDDs, als Datenstruktur zur Repräsentation Boolescher Funktionen wurden im Abschnitt 2.3.2 schon eingeführt. Eine erste Anwendung haben wir im Rahmen der zweistufigen Logikminimierung in Abschnitt 3.2.4 kennengelernt, bei der BDDs eingesetzt werden, um große Primimplikantenmengen unter Verwendung der dazugehörigen charakteristischen Funktionen effizient darzustellen. Erst durch eine solche implizite Darstellung großer Mengen kann eine exakte zweistufige Logikminimierung von Booleschen Funktionen, die viele Primimplikanten haben, möglich werden. Eine herausragende Bedeutung haben BDDs ebenfalls bei der Verifikation kombinatorischer (und sequentieller) Schaltkreise und der mehrstufigen Logiksynthese, speziell bei der funktionalen Dekomposition Boolescher Funktionen, die wir uns im nächsten Kapitel noch genauer anschauen werden. Dabei beeinflußt die Größe der BDDs der Booleschen Funktionen entscheidend die Effizienz bzw. die Einsetzbarkeit der Verfahren. Je größer der BDD, desto größer die synthetisierte Schaltung bzw. desto aufwendiger sind die Analyse- und Syntheseverfahren. Sind die BDDs mit dem zur Verfügung stehenden Speicherplatz nicht darstellbar, so versagen diese Verfahren sogar vollständig.
Paul Molitor, Christoph Scholl

6. Mehrstufige Logiksynthese mit funktionaler Zerlegung

Zusammenfassung
Häufig beschränkt man sich bei der automatischen Logiksynthese zur Realisierung von Schaltfunktionen auf Lösungen, wie wir sie in den Kapiteln 3 und 4 vorgestellt haben, zielt also auf zweistufige Logikrealisierungen ab. Dies hat im wesentlichen zwei Gründe. Einerseits sind die Verfahren mittlerweile relativ weit ausgereift und in der Lage, kostengünstige zweistufige Realisierungen zu finden, sofern es solche gibt. Andererseits lassen sich zweistufige Realisierungen durch programmierbare logische Felder leicht umsetzen und sind leicht auf Fabrikationsfehler testbar [FK81, KMO89]. Allerdings macht man die Beobachtung, daß in der Praxis sehr einfache Schaltfunktionen vorkommen, bei denen die beste zweistufige Realisierung sehr groß ist.
Paul Molitor, Christoph Scholl

7. Weitere Werkzeuge der mehrstufigen Logiksynthese

Zusammenfassung
Nachdem wir im letzten Kapitel mit der funktionalen Zerlegung Boolescher Funktionen einen Ansatz zur mehrstufigen Logiksynthese kennengelernt haben, der erst vor kurzem wieder an Aktualität gewonnen hat, wollen wir in diesem Kapitel die Grundideen der bisher verwendeten algebraischen Verfahren vorstellen. Wir folgen hierbei zum Teil der Arbeit von Brayton, Hachtel und Sangiovanni-Vincentelli [BHSV90] und den Büchern von Hachtel und Somenzi [HS96] und de Micheli [dM94].
Paul Molitor, Christoph Scholl

8. Technologie-Anpassung bei mehrstufiger Logiksynthese

Zusammenfassung
Während bei der zweistufigen Logiksynthese die berechneten Minimalpolynome direkt mit Programmierbaren Logischen Feldern (siehe Kapitel 2.2) realisiert werden können, müssen bei der mehrstufigen Logiksynthese die synthetisierten logischen Netzwerke über der durch die gewählte Technologie bereitgestellten Zellenbibliothek realisiert werden (siehe Abschnitt 2.3.1 auf Seite 53). Zur Realisierung eines logischen Netzwerkes dürfen nur Gatter aus der vorgegebenen Zellenbibliothek benutzt werden. Bei der Anpassung an die Technologie (genauer: an die Zellenbibliothek) sollte wie auch bei den bisher betrachteten Aufgaben versucht werden, die Fläche bzw. die Signallaufzeiten der Realisierung des logischen Netzwerkes zu minimieren.
Paul Molitor, Christoph Scholl

Backmatter

Weitere Informationen