Datenstrukturen und effiziente Algorithmen für die Logiksynthese kombinatorischer Schaltungen

Paul Molitor, Christoph Scholl (Autoren)

Buch | Softcover

300 Seiten

1999
Vieweg & Teubner (Verlag)
9783519029458 (ISBN)

Artikel merken

Datenstrukturen und effiziente Algorithmen spielen eine herausragende Rolle bei dem automatisierten Entwurf großer digitaler Schaltungen. Durch die Einführung neuer Technologien und der gleichzeitigen Entwicklung effizienter Datenstrukturen hat das Gebiet der Logiksynthese von digitalen Schaltungen in den letzten Jahren eine stürmische Entwicklung genommen. Das vorliegende Buch stellt die heute verwendeten Datenstrukturen und effizienten Algorithmen aus dem Bereich der logischen Synthese kombinatorischer Schaltungen vor. Im ersten Teil des Buches wird eine ausführliche, sehr anschaulich gehaltene Einführung in die zur logischen Synthese benötigten Grundlagen der Verbandstheorie und der Theorie der Booleschen Algebren gegeben und die verschiedenen Technologien, die heute als Zielarchitektur benutzt werden, werden vorgestellt. Der zweite Teil des Buches widmet sich der traditionellen zweistufigen logischen Synthese und stellt die verschiedenen exakten und heuristischen Methoden zur Berechnung von Minimalpolynomen vor. Nach einer ausführlichen Vorstellung binärer Entscheidungsgraphen (reduced ordered binary decision diagrams) beschäftigt sich das Buch dann mit der mehrstufigen Logiksynthese, insbesondere mit dem Themengebiet der funktionalen Dekomposition Boolescher Funktionen und mitalgebraischen Methoden, wie sie im an der UC Berkeley entwickelten SIS Paket benutzt werden. Das Buch ist als Lehrbuch für Lehrveranstaltungen im Bereich der Technischen Informatik für Studierende der Informatik und der Elektrotechnik konzipiert. Es wurde sehr viel Wert auf die Anschauung der Konzepte gelegt. Mit diesem Buch wurde der Versuch unternommen, eine theoretisch fundierte Darstellung der Thematik mit anschaulichen Illustrationen zu verbinden. Anhand zahlreicher Abbildungen soll der Leser zu einem tiefergehenden Verständnis der Sachverhalte hingeführt werden. Vorlesungsfolien (ca. 650 Stück) können von Dozenten über electronic mail bei molitor@informatik

Paul Molitor ist Professor für Technische Informatik an der Martin-Luther-Universität Halle-Wittenberg. Vor seiner Tätigkeit an der Universität Halle war er Professor für Schaltungstechnik an der Humboldt-Universität zu Berlin (1993/94) bzw. Projektleiter in dem an der Universität des Saarlandes und der Universität Kaiserslautern angegliederten Sonderforschungsbereich 'VLSI Entwurfsmethoden und Parallelität' (1983-92). Er studierte Informatik und Mathematik an der Universität des Saarlandes (Diplom 1982, Promotion 1986, Habilitation 1992).

1 Verband, Boolesche Algebra, Boolesche Funktionen.- 1.1 Partielle Ordnung, Hasse-Diagramm, Verband.- 1.2 Boolesche Algebren.- 1.3 Die Algebra der Booleschen Funktionen mit n Variablen.- 1.4 Unvollständig spezifizierte Boolesche Funktionen.- 2 Technologien, Modelle und Kostenmaße.- 2.1 Nurlesespeicher und Funktionstafeln v.- 2.2 PLAs und Boolesche Polynome.- 2.3 Mehrstufige Realisierungen und ihre Darstellungen.- 3 Exakte Verfahren zur 2-stufigen Logikminimierung.- 3.1 Wie sehen Minimalpolynome aus?.- 3.2 Charakterisierung der Primimplikanten.- 3.3 Berechnung eines Minimalpolynoms.- 3.4 Minimalpolynome spezieller Funktionen.- 4 Heuristische Verfahren zur 2-stufigen Logikminimierung.- 4.1 Grundlegende Algorithmen auf Polynomen.- 4.2 Strategie in Espresso.- 5 Minimierung binärer Entscheidungsgraphen.- 5.1 Vertauschung benachbarter Variablen.- 5.2 Exaktes Minimierungsverfahren.- 5.3 Heuristische Verfahren.- 5.4 Die Rolle von Symmetrien bei der BDD-Minimierung.- 5.5 Berechnung von Symmetriemengen.- 6 Mehrstufige Logiksynthese mit funktionaler Zerlegung.- 6.1 Einführung in funktionale Zerlegungen.- 6.2 Zerlegungs- und Zusammensetzungsfunktionen.- 6.3 Algorithmus zur Zerlegung einer Funktion mit einem Ausgang.- 6.4 Zerlegung einer Funktion mit mehreren Ausgängen.- 6.5 Zerlegung von unvollständig spezifizierten Booleschen Funktionen.- 7 Weitere Werkzeuge der mehrstufigen Logiksynthese.- 7.1 Optimierung logischer Netzwerke im Überblick.- 7.2 Realisierung der Optimierungsschritte.- 8 Technologie-Anpassung bei mehrstufiger Logiksynthese.- 8.1 Die Grundidee.- 8.2 Permutationsunabhängiger Boolescher Vergleich.- 8.3 Technologie-Anpassung bei look-up table FPGAs.

Erscheint lt. Verlag	18.1.1999
Reihe/Serie	XLeitfäden der Informatik
Zusatzinfo	300 S. 58 Abb.
Verlagsort	Wiesbaden
Sprache	deutsch
Maße	170 x 244 mm
Gewicht	462 g
Themenwelt	Mathematik / Informatik ► Informatik ► Theorie / Studium
Schlagworte	Algebra • Algorithmen • Bollsche Funktionen • Boolsche Algebra • Datenstrukturen • Effizienter Algorithmus • Exakte Verfahren • HC/Informatik, EDV/Informatik • Informatik • Leitfäden der Informatik • Mehrstufige Logiksynthese • Minimierung binärer Entscheidungsgraphen • Schaltnetz • Schaltung • Technologie • Technologie-Anpassung • Technologien
ISBN-13	9783519029458 / 9783519029458
Zustand	Neuware