Forum: FPGA, VHDL & Co. Minimierung von Schaltfunktionen, verwendete Gattertypen


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Michael (Gast)


Lesenswert?

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

von Lothar M. (lkmiller) (Moderator) Benutzerseite


Lesenswert?

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.

von Michael (Gast)


Lesenswert?

Lothar M. schrieb:
> Definiere "in Logik-ICs" genauer

z.B. ein 74xx247 7-Segemtdecoder. (Vielleicht bin ich hier bei FPGA im 
falschen Forum gelandet.)

von Manfred (Gast)


Lesenswert?

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.

von Fpgakuechle K. (fpgakuechle) Benutzerseite


Lesenswert?

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.

von Lothar M. (lkmiller) (Moderator) Benutzerseite


Lesenswert?

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.

von Christoph Z. (christophz)


Lesenswert?

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

von Duke Scarring (Gast)


Lesenswert?

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

von Hypercus (Gast)


Lesenswert?

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

von Ingenieur (Gast)


Lesenswert?

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.

von Joachim B. (jar)


Angehängte Dateien:

Lesenswert?

Manfred schrieb:
> Keine Ahnung, in welchem Lehrbuch das steht, da war irgendwie
> Bauchgefühl plus Erfahrung.

ging mir genauso

von Martin S. (strubi)


Lesenswert?

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.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [vhdl]VHDL-Code[/vhdl]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.