Tiefe einer Schaltung angeben, Lösung



  • Hallo,

    es geht um folgende Aufgabe:

    Geben Sie die Größe und Tiefe der resultierenden Schaltung an.

    Schaltung:

    https://www.techniker-forum.de/thema/tiefe-einer-schaltung-angeben-loesung.122087/

    Lösung der Aufgabe:

    Tiefe: Längster Pfad von Eingang b0 zum Ausgang y7 geht über 2n Gatter (bei Rechnung eines Volladdierers als 1 Gatter).

    Das verstehe ich leider nicht ganz. Wie ist das gemeint mit dem längsten Pfad? Habe ich den längsten Pfad richtig markiert? Ich komme immer auf 7 Gatter. Laut der Formel müssten es aber 2*4(n=4)=8 Gatter. Kann mir jemand bitte erklären, wie das gemeint ist? Wie geht man da am Besten vor? Was ist diese Tiefe? Hat jemand geprüftes Wissen und kann mir helfen? 😃

    LG, Kajam



  • @Kajam C++ != Schaltung



  • Kannst du das Bild auch nochmal hier posten, dass man es in groß mal öffnen könnte?



  • @Leon0402 https://abload.de/img/16028421460045lk8y.png

    Aber ich hätte da mal eine generelle Frage. Ich habe irgendwann gelernt, daß eine Verbindung zwischen zwei sich kreuzenden Verbindungen mit einem "Knödel" (= Kloß, Punkt) gekennzeichnet werden. In der vorliegenden Zeichnung wird das nicht gemacht, weder dort wo klar ist daß es eine Verbindung ist noch da, wo es nicht klar ist. ... soll man da rätselraten?



  • @Swordfish Da muss man für angemeldet sein und ich wollte mich jetzt nicht dafür anmelden 😃



  • @Leon0402 Oh my. Link geändert.



  • @Kajam Ganz offensichtlich gibt es längere Pfade in dem Schaubild. Z.b. über das und von 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.



  • Vlt. sollen nur die Volladdierer gezählt werden? ... Würde ja passen, längster Pfad wäre dann doch 8 😃



  • @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 und von 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?


Log in to reply