Datenstrukturen und effiziente Algorithmen für die by Prof. Dr. habil. Paul Molitor, Dr.-Ing. Christoph Scholl

By Prof. Dr. habil. Paul Molitor, Dr.-Ing. Christoph Scholl (auth.)

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 determination 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 email correspondence bei molitor@informatik

Show description

Read or Download Datenstrukturen und effiziente Algorithmen für die Logiksynthese kombinatorischer Schaltungen PDF

Similar german_4 books

Extra resources for Datenstrukturen und effiziente Algorithmen für die Logiksynthese kombinatorischer Schaltungen

Sample text

Dargestellt wird ein geordneter binarer Entscheidungsgraph tiber {Xl, X2, X3, X4} mit der Ordnung 60 2 Technologien, Modelle und KostenmaBe X2 < Xl < X3 < X4 fUr die Boolesche Funktion Xl . X3 . X4 + X2. Die Knoten tragen als Beschriftung ihre Markierung aus {Xl, X2, X3, X4} beziehungsweise aus {O, I}. Die low- Kanten sind gestrichelt und die high- Kanten durchgehend gezeichnet. Innere Knoten sind durch Kreise und Blatter durch kleine Vierecke dargestellt. Der Entscheidungsgraph ist geordnet, da auf jedem Pfad von der Wurzel zu einem Blatt die Variable X2 nie nach Xl, X3 oder X4, Xl nie nach X3 oder X4 und X3 nie nach X4 abgefragt wird.

X~ . X4. Die Menge ONU) ist in diesem Beispiel gleich der Menge {(O, 0, 0,1), (0,0,0,0), (1,0,0,1), (1, 1,0,0), (1, 1,0,1), (1, 1, 1,0), (1, 1, 1, I)}. Der gerade angegebene Boolesche Ausdruck besteht aus drei Monomen. Jedes dieser Monome findet sich ebenfalls im Wtirfel wieder. Die durch das Monom x~ . x~ . x~ beschriebene Funktion entspricht dem 1-dimensionalen Teilwtirfel, der aus den Knoten (0,0,0,0) und (0,0,0,1) und der dazugehorigen Kante besteht. Das Monom Xl ·x~ ·x~ ·X4 entspricht dem O-dimensionalen Teilwtirfel, der nur aus dem Knoten (1,0,0,1) besteht.

Wk)) = ¢(W1) + ... + ¢(Wk) c) Vw E A(X): ¢(w') = ¢(w)'. ¢ wird die Interpretation der Booleschen Ausdriicke genannt. 6 Gilt ¢(w) = 1, so sagen wir, da8 der "Boolesche Ausdruck W die Boolesche Funktion 1 beschreibt" oder "w ein Boolescher Ausdruck von 1 ist". Auch werden wir oft Boolesche Ausdriicke mit ihrer Interpretation gleichsetzen, falls keine Mi8versUindrusse zu befiirchten sind. Offensichtlich gibt es zu jeder Booleschen Funktion 1 E Bn eine unendliche Menge von Booleschen Ausdriicken, die 1 beschreiben.

Download PDF sample

Rated 4.32 of 5 – based on 48 votes