Tiefe einer Schaltung angeben, Lösung
-
Ich kann mir vorstellen, dass man sich hauptsächlich um die Volladdierer kümmert. Bei der ganzen Betrachtung geht es ja um Laufzeit oder Platzverbrauch, da werden für die Laufzeit die Addierer die ausschlaggebenden Gatter sein.
Mit 2n kommt man auf jeden Fall auf die maximale Anzahl an Volladdierern.
Warum: Bei n x n eingängen könnte ich mir das (etwas Leihenhaft) so erklären:
Du hast (wen du dir das z.B. als Matrix oder schriftliche Multiplikation hinschreibst) n-1 Additionen, aber bis zum hinterher führenden Bit n+1 Überträge, macht (n-1)+(n+1) = 2n Addierer für den längsten Pfad.
-
@Kajam
Ich wäre vorsichtig mit solchen Formeln.Die Hauptfrage an einer solchen Schaltung ist die Frage: Wie lange benötigt die Schaltung bis das Ergebnis fertig ist?
Deswegen benötigst du den längsten Pfad. Gehst du diesen entlang und summierst die Verzögerungen der einzelnen Gatter auf, dann erhälst du die maximale Verzögerung der Schaltung.
Nehmen wir mal an, jedes Gatter in deinem Beispiel hätte eine Verzögerung von 0,11 ms. Der längste Pfad ist 9 Gatter groß, also würde der längste Pfad nach 9×0,11 ms = 1 ms fertig sein. Das heißt nach 1 ms ist das Ergebnis fertig und man könnte die nächste Berechnung starten. Nach einer weiteren Millisekunde wäre das nächste Ergebnis fertig, s.d. man die nächste Berechnung starten könnte.
Das heißt man könnte alle Millisekunde eine neue Berechnung starten bzw. Berechnungen periodisch mit einer Zeit von 1ms durchführen. Nun wissen wir Frequenz = 1 / Periodendauer.
In deinem Beispiel wäre die Frequenz = 1 / 1 ms = 1 kHZ. Also kannst du die Schaltung mit 1 kHZ Taktfrequenz betreiben.
-
Ja, das ist alles schön und gut. Aber sind das jetzt 9 oder 8 Gatter wie in der Lösung? Zählt man das UND-Gatter jetzt nicht???
-
@Schlangenmensch Also sind die UND-Gatter egal???
-
@Leon0402 Der Lösungssteller antwortet nicht. Ich habe hier die Aufgabe und die Lösung als letzten Kommentar gepostet:
https://www.techniker-forum.de/thema/tiefe-einer-schaltung-angeben-loesung.122087/
-
@Kajam
9 Gatter natürlich!Überleg doch mal. Dein längster Pfad gibt die minimale Berechnungszeit an. Erst nach dieser Zeit ist die Berechnung fertig. Legst du vorher eine neue Eingabe an, so vermischst du die Ergebnisse und es kommt kein gültiges Ergebnis an!
-
@Kajam sagte in Tiefe einer Schaltung angeben, Lösung:
Also sind die UND-Gatter egal???
NEIN!!!
Dir ist schon bewusst dass so ein 1 Bit Addierer auch mit Hilfe von UND Gatter aufgebaut werden kann?
-
@Kajam
Mal eine Frage zum Nachdenken: Annahme du möchtest die Schaltung mit 1 GHz betreiben. Wie hoch ist dann die Periodendauer?
-
@Kajam Da ich nicht weiß, wodrauf dein Lehrer oder Professor hinaus möchte, kann ich das nicht sagen.
Prinzipiell interessieren dich beim Design von solchen Schaltungen 2 Sachen: Das eine, hier irrelevant, ist der Platzbedarf.
Das zweite ist die Laufzeit. Beides jeweils in Abhängigkeit von der Eingabegröße, also, wie skaliert das Ding, wenn die Eingabe richtig groß wird. Wenn du das eine UND da vor mitzählst, kommst du dann bei der Schaltung auf 2n+1 Gatter, das heiß, die Laufzeit von der Schaltung liegt in O(2n). Dieses eine UND Gatter ist dann bei der Betrachtung egal. Ob das, dass ist, was die Aufgabe / dein Lehrer, von dir will, weiß ich nicht.@Quiche-Lorraine sagte in Tiefe einer Schaltung angeben, Lösung:
@Kajam sagte in Tiefe einer Schaltung angeben, Lösung:
Also sind die UND-Gatter egal???
NEIN!!!
Dir ist schon bewusst dass so ein 1 Bit Addierer auch mit Hilfe von UND Gatter aufgebaut werden kann?
Aber genau, dass man die Addierer einzeln zählt und nicht die einzelnen Bestandteile, spricht doch eigentlich auch dafür, dass das eine UND hier nicht ausschlaggebend ist.
-
@Schlangenmensch sagte in Tiefe einer Schaltung angeben, Lösung:
Aber genau, dass man die Addierer einzeln zählt und nicht die einzelnen Bestandteile, spricht doch eigentlich auch dafür, dass das eine UND hier nicht ausschlaggebend ist.
Warum?
Ich glaube Ziel der Aufgabe ist das Verständnis der Signal-Laufzeiten. Wo sind nach x Nanosekunden korrekte Signale? Wo liegen nach x Nanosekunden ungültige Signale?
Nach 8 × Bearbeitungszeit Addierer liegt einfach kein korrektes Ergebnis an Pin y7. Wenn ich nun eine neue Eingabe anlege, wie dies in der ALU (Arithmetic Logical Unit) der Fall ist, und die Bearbeitungszeit des Und Gatter warte, so liegt an Pin y7 das korrekte Ergebnis an, aber an Pin y0 bereits das neue Ergebnis.
Ich lege hier ja nicht die Zeiten der einzelnen Gatter fest. Ich sage ja bloß das jedes Gatter zählt, da in moderen Chips die Taktfrequenz so hoch ist, dass es hier auf Nanosekunden ankommt. Es kann ja sein das ein Addierer beispielsweise 10 ns benötigt und ein Und Gatter 1 ns. In der Summe kann ich aber deswegen erst nach 81 ns weitermachen und nicht nach 80 ns. In der Summe macht dies ein Unterschied von 155 kHz aus.
-
@Quiche-Lorraine Ich gehe eher davon aus, dass es um's Laufzeitverhalten für beliebige Eingangsgrößen geht. Daher auch der Exkurs zur O-Notation. Aber ohne die Lehrinhalte vom TE zu kennen, ist das hier alles sehr spekulativ.
-
@Schlangenmensch
Laufzeitverhalten, Komplexitätsanalyse bei einer Schaltung? Achso.
Ich habe es eher aus Sicht der Rechnersysteme betrachtet. Also die Grundlagen einer CPU, Binärdarstellung von Zahlen (BCDs), Grundlagen einer Schaltung, Aufbau diverser Schaltungen (Addierer, Subtrahierer, ALU, Steuerwerk), Phasen einer CPU (Instruction Fetch, Instruction Decode,...), Pipelining,...
Ich könnte mir sogar vorstellen die Aufgabe in Form eines Petri Netzes zu modellieren.
@Kajam
Aus welche Ecke kommt die Frage? Wie heißt die Vorlesung bzw das Unterrichtsthema?
-
@Quiche-Lorraine sagte in Tiefe einer Schaltung angeben, Lösung:
Laufzeitverhalten, Komplexitätsanalyse bei einer Schaltung? Achso.
Jup. Hat zumindest mein Technische Informatik Prof damals gemacht und das oben irgendwo angegeben Buch macht das auch. Also Betrachtung von Laufzeitverhalten und Platzbedarf.
Edit: Die anderen Themen die du mit ansprichst gehörten auch mit dazu, nur bei grundlegenden Schaltungen war das halt auch ein Thema.
-
In der Lösung steht 2n Gatter. Mein "n" ist 4, weil ich a0, a1, a2 und a3 habe? Das wären dann 2*n=8, aber es sind 9 Gatter? Das heißt, die Lösung ist falsch?
-
@Quiche-Lorraine Also ist die Lösung falsch, weil ein UND-Gatter fehlt? Die "2n" ist richtig hinsichtlich der Darstellung der Addierer? Aber richtig wäre also 2n+1=9 Gatter für n=4?
-
@Quiche-Lorraine 9*1 GHz
-
@Quiche-Lorraine Die Veranstaltung/Vorlesung/Thema heißt: Informatik für Maschinenbau-Ingenieure
Boolesche Logik und Schaltungen und Automatentheorie
-
Können wir uns nicht einfach auf die Lösung beziehen? Ich bin gerade voll verzweifelt.
Also nochmal:
Größe: Anzahl der Gatter: Bei Multiplikation (an−1, . . . , a0) · (bm−1, . . . , b0) werden n · m UNDGatter, n · (m − 1) Volladdierer benötigt.
Tiefe: Längster Pfad von Eingang b0 zum Ausgang y7 geht über 2n Gatter (bei Rechnung eines
Volladdierers als 1 Gatter).Die Größe ist mir wohl klar. Bei der Tiefe steht in Klammern "bei Rechnung eines Volladdierers als 1 Gatter). Hier werden doch eindeutig nur die Addierer als 1 Gatter berücksichtig und verrechnet??? Demnach hat @Schlangenmensch recht? Oder es sei denn, in der Lösung ist das Und-Gatter vergessen worden...? Was jetzt?
-
@Kajam Nochmal zum mitschreiben: Die Lösung ist scheiße. Ohne nähere Details zu kennen (z.B. Vorlesungsinhalte auf die sich diese Aufgabe beziehen könnte) kann hier jeder nur spekulieren, was damit gemeint ist.
Frag den Prof -> Dafür ist er daIch kann dir nur sagen, dass mit Tiefe die in Reihe geschalteten Gatter gemeint sind (soweit ich weiß) und das du nicht den längsten Pfad markiert hast (außer du hast es zwischenzeitlich geändert).
-
Hier, das sind die Vorlesungsinhalte:
file:///C:/Users/kamil/Downloads/02_logik_schaltungen.pdf
file:///C:/Users/kamil/Downloads/03_automatentheorie.pdf
Bis der Prof antwortet, können Jahre vergehen.
