Tiefe einer Schaltung angeben, Lösung
-
@manni66 was soll das bedeuten?
-
@Schlangenmensch sagte in Tiefe einer Schaltung angeben, Lösung:
@Kajam Ganz offensichtlich gibt es längere Pfade in dem Schaubild. Z.b. über das
undvon a1 und b0, dann aus dem Volladerer weiter nach "links" dann in eine Ebene tiefer, wieder nach "links" wieder nach unten usw.Und mal wieder eine Formel, die vom Himmel fällt. Woher kommt die? Hast du die entwickelt? Kannst du beweisen, dass die Korrekt ist? Ich komme im Moment auf 9 Gatter für den längsten Pfad, aber ich habe da jetzt nur 5 Minuten drauf geguckt und ich muss @Swordfish recht geben, dass Schaubild ist eine Katastrophe.
Edit: Ich habe eben mal ein altes Buch aus meiner Studienzeit rausgeholt (Grundlagen der technischen Informatik, von Dirk W. Hoffman, Ausgabe von 2007) da drinnen finde ich die Information zu dem Matrixmultiplizierer, das, dass Signal auf dem längsten Pfad n + (n - 1) Volladierer durchläuft. Das scheint mir auch falsch zu sein, mein Prof hat damals schon auf verschiedene Fehler in dem Buch hingewiesen. Ich hab grade aber meine Unterlagen von damals nicht zur Hand, aber 2n Volladierer scheint mir Sinn zu ergeben und passt zumindest in dem Beispiel.
Diese Formel ist aus der Lösung der Aufgabe. Kann sein, dass die stimmt. Aber wie kommt man darauf? Ich glaube, ich will es verstehen
Zumal ein anderes Mitglied mit der Formel um die Ecke kam: 3n-3 Gatter oder 3n-4 wenn man das letzte UND-Gatter nicht mitzählt.
Was ist nun richtig?
-
@Leon0402 sagte in Tiefe einer Schaltung angeben, Lösung:
Vlt. sollen nur die Volladdierer gezählt werden? ... Würde ja passen, längster Pfad wäre dann doch 8
Also zählt man immer nur die Volladdierer mit und nicht die anderen Und-Gatter?
-
@Kajam Wüsste ich das, hätte ich kein Fragezeichen dahinter gestellt. Für mich ist ein And Gatter auch ein Gatter. Aber da die Lösung schon recht schwammig formuliert ist, liegt es ja nahe, dass die Aufgabenstellung auch schwammig formuliert ist.
Woher ist denn Aufgabe + Lösung? Kann der Lösungsersteller nicht gefragt werden?
-
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
