Datenstrukturen und effiziente Algorithmen fr die Logiksynthese kombinatorischer Schaltungen

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.