Verbindung zwischen kombinatorischer Logik und sequentieller Logik

Ich dachte immer, dass kombinatorische Logikschaltungen nur Probleme lösen könnten, die keinen Speicher benötigen, aber dann fiel mir etwas auf.
Wann immer wir einen binären Addierer mit einer endlichen Zustandsmaschine modellieren, betrachten wir dies als ein Problem, das Speicherplatz erfordert (wir müssen wissen, ob die vorherige Ziffernaddition zu einem Übertrag geführt hat oder nicht). Deshalb brauchen wir zwei Zustände, "kein Übertrag" und "Übertrag".

Geben Sie hier die Bildbeschreibung ein

Aber dann können wir leicht sehen, wie binäre Addierer mit Trägern durch kombinatorische Logikschaltungen gelöst werden können, die scheinbar kein Gedächtnis haben.

Geben Sie hier die Bildbeschreibung ein

Es scheint mir, dass der Speicher irgendwie so codiert ist, wie wir die einzelnen Addierer in Reihe geschaltet haben ( C_out des letzten Addierers geht in den C_in des aktuellen Addierers ).

Vergleicht man die Finite-State-Machine-Lösung für das Problem mit der Kombinationslogik-Lösung für das Problem, scheint es, als würde erstere entscheiden, jeweils eine Ziffer hinzuzufügen, geregelt durch eine Uhr, und deshalb muss der Speicher in Form von Zuständen vorliegen. Und es scheint, als ob letzterer beschließt, alle Ziffernadditionen gleichzeitig durchzuführen, sodass keine Uhren erforderlich sind und der Speicher für die vorherigen Träger irgendwie über eine serielle Kaskadenverbindung zwischen den Addierern implementiert wird.

So wie wir sowohl eine FSM- als auch eine kombinatorische Logikversion für das Problem der arithmetischen Addition mit Trägern haben können, denke ich darüber nach, ob wir tatsächlich JEDE endliche Zustandsmaschine in eine kombinatorische Logikschaltung umwandeln können, die die gleiche Aufgabe erfüllt, vorausgesetzt, wir arrangieren eine Teilschaltung für jeden möglichen Job, der im FSM in einem Takt erledigt wird (im letzten Fall eine Ziffernaddition), alle parallel schalten und den Speicher irgendwie in einer seriellen Kaskadenverbindung codieren.

Ist es wahr ?

Dieser Zweifel kam, weil ich versuche, alle Konzepte, die ich kürzlich in Theory of Computation gelernt habe (Automata, Turing Machines, Computational Complexity: Time Complexity and Space Complexity), mit kombinatorischen Logikschaltungen zu verknüpfen.

Vielen Dank im Voraus.

Antworten (6)

Nein, Sie können eine (nichttriviale) Schaltung mit Gedächtnis nicht in eine kombinatorische (rückkopplungslose) Schaltung übersetzen.

Die Ausgänge einer kombinatorischen Schaltung sind per Definition eine Funktion ihrer Eingänge (und sonst nichts).

Nehmen Sie die einfachste nichtkombinatorische Schaltung: die Set-Rest-Speicherzelle (zwei Kreuzpaare NANDs oder NORS). Wenn die Eingaben den Wert „Erinnern“ haben, sind die Ausgaben eine Funktion der Vergangenheit. Dies ist einfach mit keinem Schaltnetz möglich.

Wenn das Design einen Zustand benötigt, muss es eine Möglichkeit haben, diesen Zustand zu speichern, nämlich Speicher.

Die Ausgabe eines Addierers (oder Multiplikators usw.) wird vollständig durch die Eingaben bestimmt und kann daher vollständig in kombinatorischer Logik implementiert werden.

Ein Einzelbitspeicher kann nicht in kombinatorischer Logik implementiert werden, sonst wäre er kein Speicher.

Das liegt daran, dass die Modellierung des Addierers als FSM bequem, aber letztendlich falsch ist. Es gibt keine Zustände; Was als "Zustand" gezeigt wird, ist lediglich die Ausgabe und nicht das Ergebnis eines zustandsbasierten Übergangs.

Das scheint tief und ich möchte es wirklich begreifen, aber ich konnte es nicht vollständig verstehen. Gibt es eine Art Methode oder Hinweis, um eine FSM zu erhalten und zu prüfen, ob es sich um eine echte FSM handelt oder nicht, dh zu prüfen, ob es sich bei den Zuständen wirklich um Ausgänge handelt oder ob sie wirklich das Ergebnis eines zustandsbasierten Übergangs darstellen? ? Könnt ihr mir Lesestoff empfehlen? Vielen Dank
Ein FSM benötigt eine Art Speicher, um den aktuellen Zustand zu speichern, sowie eine Art Taktgeber, um zu bestimmen, wann Übergänge durchgeführt werden sollen (dh er kann nur für sequentielle Logik existieren). Ein Addierer (der rein kombinatorische Logik ist) hat beides nicht.
Was @IgnacioVazquez-Abrams sagte, wenn es Speicher (und eine Uhr) gibt, dann gibt es Zustände. Sie können gefälschte "Fall-Through"- oder temporäre Zustände erstellen, indem Sie einfach Zwischenknoten als Zustände benennen, aber das ist nur eine Annehmlichkeit für den Designer. Ein weiterer Hinweis darauf, dass Sie Zustände haben, ist, dass Sie (normalerweise) beim Einschalten der "Schaltung" etwas Besonderes tun müssen. ROM scheint eine Ausnahme zu sein, aber Sie haben das "Etwas Besonderes" gemacht, als Sie es programmiert haben, nach der Programmierung verhält sich das ROM als kombinatorische Logik. Im größeren Zusammenhang muss "Zustand" nicht null oder eins sein, es könnte analog sein.

Das in der Frage gezeigte Zustandsdiagramm ist ein serieller Addierer . Es hat nur einen Volladdierer und ein Speicherelement darin. Und es erfordert N Taktzyklen, um das Ergebnis der Addition von zwei N-Bit-Zahlen zu erzeugen.

Das in der Abbildung gezeigte Blockdiagramm ist ein 4-Bit -Ripple-Carry-Addierer , der 4 Volladdiererblöcke benötigt. Dies addiert zwei 4-Bit-Zahlen parallel und liefert das Ergebnis in kürzester Zeit (Laufzeitverzögerungen werden vernachlässigt). Die Logik hier ist rein kombinatorisch und enthält kein Gedächtnis.

Kurz gesagt entspricht das gegebene Zustandsdiagramm nicht dem gegebenen Blockdiagramm. Es sind zwei unterschiedliche digitale Systeme. Der serielle Addierer hat zwei Einzelbiteingänge und einen Bitausgang. Wohingegen ein Ripple-Carry-Addierer zwei N-Bit-Eingänge und einen N+1-Bit-Ausgang hat.

Sequentielle Maschinen können nicht durch kombinatorische Logik ersetzt werden. Kombinatorische Schaltungen können jedoch durch sequentielle Schaltungen ersetzt werden. Normalerweise wird dies getan, um die Hardwarekomplexität zu reduzieren. Was wir in Ihrer Frage gesehen haben, ist ein Beispiel dafür. Die Schaltungen wie Zähler, Schieberegister usw. können niemals durch kombinatorische Logik ersetzt werden.

Hinsichtlich der Rechenkomplexität trennt der serielle Addierer die Rechenschritte zeitlich, wobei die Hardware wiederverwendet wird. Der Ripple-Addierer trennt die Schritte im Raum, indem er separate Kopien der Hardware verwendet, um die separaten Schritte auszuführen.

Meiner Meinung nach hängt es von der Funktionalität der Schaltung ab, ob eine kombinatorische Schaltung aus einer sequentiellen Schaltung extrahiert werden kann. Viele (aber nicht alle) sequentiellen Logikschaltungen können entpackt und als reine kombinatorische Schaltungen implementiert werden (ich denke, das ist so gilt insbesondere für Moore-Maschinen), aber es gibt viele Zeit- und Bereichsspezifikationen, die sehr schwer zu erfüllen wären, wenn wir uns entscheiden würden, sie auf diese Weise zu implementieren. Außerdem wird die Entwicklung mit zunehmender Anzahl von Zuständen unpraktisch und zu kostspielig ein System auf diese Weise.

Ich bin mir nicht sicher, ob ich der Haltung zustimme, dass die Darstellung eines Addierers mit dem von Ihnen bereitgestellten Diagramm notwendigerweise falsch ist, wie ein anderer Poster angegeben hat. Vielleicht ist es im Zusammenhang mit der von Ihnen bereitgestellten Ripple-Addierer-Schaltung falsch, aber ein N-Bit-Addierer kann tatsächlich sein so modelliert, dass sie zwei Zustände durchläuft, Übertrag-1 und Übertrag-0, und eine sequentielle Schaltung wie die unten extrahierte.

Sequentielle Addierer

Viele sequentielle (synchrone / getaktete) Schaltungen können in vielen Situationen auch durch rein kombinatorische (asynchrone / taktlose) Schaltungen ersetzt werden. Diese asynchronen Schaltungen verwenden Bündeldatenprotokolle wie das 4-Phasen-Dual-Rail-Protokoll zur Kommunikation einander und haben im Wesentlichen Zustandsinformationen, die in ihren Ausgängen codiert sind.

Grundsätzlich betrachten wir den Carry für die nächste Operation (nicht den Zustand), aber es ist egal, was es sein wird, es kann 1 oder 0 sein, und die endgültige Ausgabe wird durch den Wert und die Kombination aller Logik entschieden, wir können es nicht mit dem Zustand modellieren Maschine, da die gesamte Schaltung im Gegensatz zu einem Zähler nicht mehrere Zustände durchläuft

Verbindung zwischen kombinatorischer Logik und sequentieller Logik
AntwortenHierDatenschutz-Bestimmungen1y, 0v