Hallo, zur Minimierung von Schaltfunktionen werden in Grundlagenbüchern (z.B. Grundlagen der Technischen Informatik von Dirk Hoffmann) oft das KV-Diagramm und das Quine-McCluskey-Verfahren beschrieben. Bei beiden Verfahren erhält man anschließend ein Schaltfunktionen, die mit den Gattern AND, OR und NOT direkt in eine Schaltnetz übersetzt werden kann. Nun meine Fragen: 1. Es gibt noch weitere Gattertypen, z.B. NOR, NAND oder XOR. Man müsste doch eigentlich einige Schaltfunktionen mit diesen weiteren Gattern noch weiter optimieren können, so dass sie insgesamt mit weniger Gattern auskommen. Warum wird das in Grundlagenbüchern nicht gezeigt? Liegt es vielleicht daran, dass man NOR, NAND und XOR in richtigen Schaltungen immer aus AND, OR und NOT zusammenbaut? 2. Scheinbar reichen NAND-Gatter schon aus, um alle anderen Gatter daraus zu bauen, so dass man im Prinzip jedes Schaltnetz nur aus NAND-Gattern bauen kann (genauso mit NOR, oder mit AND und NOT, oder mit OR und NOT). Macht man das in Wirklichkeit in Logik-ICs so, dass man möglichst wenige "Basisgatter" verwendet? Viele Grüße und vielen Dank Michael
Michael schrieb: > Macht man das in Wirklichkeit in Logik-ICs so, dass man möglichst wenige > "Basisgatter" verwendet? Definiere "in Logik-ICs" genauer. Wenn du eine Schaltung mit einzelnen Bausteinen aufbaust, dann nimmst du die Schaltung, für die möglichst wenig Bauteile nötig sind. Und in FPGAs/CPLDs gibt es sowieso keine solchen "Basisgatter", sondern dort wird mit kleinen Funktionsgeneratoren (=kleine ROMs mit 4..6 Adressleitungen) oder mit recht mächtigen Produkttermen gearbeitet.
Lothar M. schrieb: > Definiere "in Logik-ICs" genauer z.B. ein 74xx247 7-Segemtdecoder. (Vielleicht bin ich hier bei FPGA im falschen Forum gelandet.)
Michael schrieb: > Scheinbar reichen NAND-Gatter schon aus, um alle anderen Gatter > daraus zu bauen, so dass man im Prinzip jedes Schaltnetz nur aus > NAND-Gattern bauen kann Logikschaltungen mit ganz vielen 74xx / 40xx habe ich schon lange nicht mehr gemacht. Als das noch akut war, habe ich mit Wahrheitstabellen und nur mit NAND-Gattern 7400 / 4011 auf Karopapier gemalt. Ausnahme waren Zähler / Teiler, da kamen direkt passende Typen in den Entwurf. Viele Bausteine gibt es auch mit drei oder vier Eingängen, es gibt AND, OR, NOR und Inverter. Wenn das Gebilde fertig entworfen war, kam "scharfes Angucken" - also entscheiden, welche Kombinationen mehrerer 2er-NAND sich zu anderen Typen zusammenfassen lassen. Ziel war halt, die Anzahl der Käfer zu verringern. Keine Ahnung, in welchem Lehrbuch das steht, da war irgendwie Bauchgefühl plus Erfahrung.
Michael schrieb: > Macht man das in Wirklichkeit in Logik-ICs so, dass man möglichst wenige > "Basisgatter" verwendet? Njein, das kommt auf die Entwurfsmethodik an, Gate Array, StandardCell oder FullCustom. http://web.cecs.pdx.edu/~mperkows/CLASS_VHDL_99/tran888/lecture014.CPLD-FPGA.pdf Bei Gatearray hat man IC-Grundmaterial (Halbzeug) auf dem sich viele der Grundgatter befinden, in der End-Fertigung werden dann lediglich die Metallisierungsebenen hinzugefügt die als Verbindungskanäle aus den Grundgattern die gewünschte Funktion verschalten. Bei FullCostum dagegen, wird der gesamte chip komplett neu aufgebaut und man hat die optimale Funktion aus Transistoren etc. einzeln 'gezeichnet'. Standard-cell ist dazwischen, da macht man nicht jede Ecke des IC neu, sondern verwendet optimimierte (nicht stur aus NAND's) aufgebaute Macros wie Adder etc.pp. Anzahl (Chipfläche) ist da nur ein Kriterium, ebenso wichtig ist die Durchlaufzeit. Was nutzt ein kleiner 'Carry-Ripple' Adder bei dem die 'Berechnung' 20 Nanosekunden braucht und so das Design auf 50 MHz ausgebremst wird.
Michael schrieb: > Lothar M. schrieb: >> Definiere "in Logik-ICs" genauer > z.B. ein 74xx247 7-Segemtdecoder. Dort innnen drin ist das Design auf Transistorebene optimiert. Es ist idealerweise keine Sperrschicht mehr drin, als diese 7-Segment-Decoder-Funktion benötigt.
Fpgakuechle K. schrieb: > Standard-cell ist dazwischen, da macht man nicht jede Ecke des IC neu, > sondern verwendet optimimierte (nicht stur aus NAND's) aufgebaute Macros > wie Adder etc.pp. Der Katalog von diesen Macros (genannt PDK) lizenziert man von der Chipfabrik, wo nachher produziert wird. Chiphersteller wechseln gibts nicht (Technisch schwierig, Lizenzmässig nicht vorgesehen). Bisher war da auch alles unter NDA. Mit LibreSilicon und dem neueren Angebot von Google kommt da mal Wind in die Sache und ich kann hier auf ein Git repo verweisen: https://foss-eda-tools.googlesource.com/skywater-pdk/libs/sky130_fd_sc_hd/+/836b7fa01a1f7870ab44f6b59220b0ad7f6f0ebc/cells/ Da sind alle verfügbaren Gattertypen der Library: "High density" digital standard cells provided by the SkyWater foundry. Es gibt diese Libraries dann nochmals für High-Speed und Low-Power. Interessant hier zum Erwähnen ist die Auswahl an "Complex Gates", wie z. B. "2-input AND into first input of 4-input NOR.": https://foss-eda-tools.googlesource.com/skywater-pdk/libs/sky130_fd_sc_hd/+/836b7fa01a1f7870ab44f6b59220b0ad7f6f0ebc/cells/a2111oi/definition.json Michael schrieb: > KV-Diagramm und das Quine-McCluskey-Verfahren beschrieben. [...] > Warum wird das in Grundlagenbüchern nicht gezeigt? Liegt es > vielleicht daran, dass man NOR, NAND und XOR in richtigen Schaltungen > immer aus AND, OR und NOT zusammenbaut? Das sind die Grundlagen, die man noch so von Hand auf Papier vermitteln kann. Alles was später kam (eigentlich schon Quine-McCluskey) nutzt Computer und macht entsprechend wenig Spass von Hand durchzuführen in Grundlagenkursen (darum haben sie bei uns Quine-McCluskey nur erwähnt ohne durchzukauen). Moderne Algorithmen, die auf Complex Gates mappen und optimieren können sind aufwändig und nicht Dokumentiert (Damit verdienen z. B. Cadence und Synopsis ihr Geld, neben anderem Spezialwissen).
Michael schrieb: > Man müsste > doch eigentlich einige Schaltfunktionen mit diesen weiteren Gattern noch > weiter optimieren können, so dass sie insgesamt mit weniger Gattern > auskommen. Warum wird das in Grundlagenbüchern nicht gezeigt? Weil es Grundlagenbücher sind. Das ist der Unterschied zwischen Theorie und Praxis. Wenn du diesbezüglich etwas praktisches lernen willst, besorge dir die Unterlagen von alten Computern, die mit solchen Logikgattern aufgebaut sind und versuche die Schaltungen nachzuvollziehen. Duke
Christoph Z. schrieb: > Das sind die Grundlagen, die man noch so von Hand auf Papier vermitteln > kann. Alles was später kam (eigentlich schon Quine-McCluskey) nutzt > Computer und macht entsprechend wenig Spass von Hand durchzuführen in > Grundlagenkursen (darum haben sie bei uns Quine-McCluskey nur erwähnt > ohne durchzukauen). Karnaugh und Quine-McCluskey ist haargenau selbe Prinzip, bei QMC wird ebenfalls eine 2D Matrix aufgebaut und nach zusammenfassbaren Nachbarn-Tupeln gesucht, nur eben nicht auf karierten Papier sondern in einem 2D-array im Speicher. Falls man das besser verstehen will, kann man sich ja in die ATPG (automated Test Pattern Generation) einlesen. Die basiert auch darauf das man Eingangsvektoren mit gleichen Ausgangsvektor erkennt. Ist nicht weiter kompliziert, nur reichlich abstrakte (Graphen-)Theorie. https://nptel.ac.in/content/storage2/courses/106103116/handout/mod9.pdf https://www.lume.ufrgs.br/bitstream/handle/10183/174523/001063170.pdf?sequence=1
Michael schrieb: > Warum wird das in Grundlagenbüchern nicht gezeigt? In meinen Vorlesungen damals wurde das sehr wohl gezeigt. Aus der Erinnerung war es so, dass es eben solche Tabellen gab, die mit teilinvertierten Gleichungen arbeiten. Man hat immer die Hälfte gespiegelt, weil statisch maximal die Hälfte in einer invertierten oder nichtinvertierten Logik gebaut werden muss, sonst kann man es auch umgekehrt bauen und die Inverter alle invertierten. Am Ende kam dann eine Lösung für NOR und AND sowie OR und NAND raus, die komplementär waren. Man kann es aber auch händisch machen und jeweils die inverter von hinten reinschieben, also das Gatter von OR auch NAND umbauen und dann vorne die Inverter wegfallen lassen, so welche da waren. Solche Sachen machen aber heute die ASIC-Compiler von alleine. Laut einen FAE werden da Matrizen gebildet, die die vorhandene Beschreibung schlagartig zu allen Möglichkeiten duplizieren und dann parallel, Pfad für Pfad nach vorne und hinten mit anderen Komponenten zusammenfassen. Daraus entstehen dann für jeden Knoten 4 Version und jeden Doppelknoten 16 Versionen von denen man die 4 langsamsten und die 4 größten wegwirft. Mit denen geht es dann weiter in die Pfadoptimierung und man vergleicht, welche Versionen von der Optimierung davor und dahinter als gut befunden wurde. Daraus bildet man die Schnittmenge und erhält einen schnellsten Pfad, einen kleinsten Pfad und einen stromsparendsten. Je nach Strategie am Ende wird dann einer der akzeptablen eingesetzt. Zur damaligen Zeit guckte der Optimierer immer jeweils 2 Knoten weit, später werden es wohl mehr geworden sein.
Angehängte Dateien:
-
TC80_PC1500.jpg
80 KB
Manfred schrieb: > Keine Ahnung, in welchem Lehrbuch das steht, da war irgendwie > Bauchgefühl plus Erfahrung. ging mir genauso
Noch ein Hinweis: Wenn die alten Lehrbuecher nicht mehr reichen, weil sie auch nur die Grundlagen abdecken: Mit yosys und berkeley-abc kann man dem Technologie-Mapping (insbesondere LUTs von FPGA-Technologien) auf die Finger schauen und damit auch produktiv herumspielen/lernen.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.