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.
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.jsonMichael 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.pdfhttps://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.
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.
