Datenstrukturen Und Effiziente Algorithmen Für Die Logiksynthese Kombinatorischer Schaltungen

ISBN-13: 9783519029458 / Niemiecki / Miękka / 1999 / 300 str.

Paul Molitor; Christoph Scholl

Opis

Das vorliegende Lehrbuch beschaftigt sich mit einem fiir das Gebiet der Infor matik sehr alten Thema, dem logischen Entwurf von kombinatorischen Schal tungen, also dem Problem, eine moglichst in Platz und Zeit effiziente Rea lisierung einer vorgegebenen Booleschen Funktion zu finden. Viele bekannte und weniger bekannte Wissenschaftler haben sich in den letzten 50 Jahren mit dieser grundlegenden Thematik der Technischen Informatik befafit. Stellver tretend seien C. E. Shannon, W. Quine, EJ. McCluskey, J. P. Roth und O. B. Lupanov genannt. Wahrend sich die Arbeiten bis in die 80er Jahre aufgrund der ungenfigenden zur Verfiigung stehenden Rechenkapazitaten vorwiegend mit (komplexitats-) theo retischen Aspekten beschaftigt haben, ist in den letzten 15 Jahren der prakti sche Aspekt immer mehr in den Vordergrund geriickt. Ein Anstofi hierfiir ist si cherlich in der rasanten Entwicklung der Hochstintegration und in der hieraus resultierenden Moglichkeit zum Entwurf sehr grofier (anwendungsspezifischer) digitaler Systeme, die in ihrer Komplexitat ohne Rechnerunterstfitzung mitt lerweile nicht mehr zu beherrschen sind, zu sehen. Ein weiterer Grund besteht in der Verfiigbarkeit schneller Rechentechnik, die es erst erlaubt, Instanzen, die fiber Spielbeispiele hinausgehen, in Angriff zu nehmen. Durch die Bereit stellung neuer Technologien -als Beispiel seien die Field Programmable Gate Arrays (FPGA) genannt, die in ihren Moglichkeiten weit fiber die der Program mable Logic Arrays (PLA) hinausgehen - und wiederum durch die rasant ge stiegene Leistungsfahigkeit heutiger Rechner, die es erlaubt, komplexere Auf gabenstellungen anzugehen, ist das Interesse von der zweistufigen logischen Synthese weg zur mehrstufigen Logiksynthese gerfickt.

Spis treści

Verband, Boolsche Algebra, Boolsche Funktionen - Technologien, Modelle und Kostenmaße - Exakte Verfahren zur 2-stufigen Logikminimierung - Minimierung binärer Entscheidungsgraphen - Mehrstufige Logiksynthese mit funktionaler Zerlegung - Weitere Werkzeuge der mehrstufigen Logiksynthese - Technologie-Anpassung bei mehrstufiger Logiksynthese

O autorze

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).

Blurb

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