Finite-State-Maschine

Feedback ist ein faszinierendes Konstruktionsprinzip. Es kann ein ziemlich einfaches Gerät oder Verfahren in etwas wesentlich komplexeres verwandeln. Wir haben die Effekte von Feedback, das absichtlich in Schaltungsdesigns integriert wurde, mit einigen ziemlich erstaunlichen Effekten gesehen:

• Komparator + Gegenkopplung—————-> Verstärker mit regelbarer Verstärkung
• Komparator + positives Feedback—————-> Komparator mit Hysterese
• Kombinationslogik + positives Feedback—> Multivibrator

In der Prozessinstrumentierung wird Feedback verwendet, um ein einfaches Messsystem in ein steuerbares System zu verwandeln:

• Messsystem + negatives Feedback—-> Regelsystem

Sowohl positive als auch negative Rückkopplungen haben die Tendenz, dem Betrieb eines Geräts oder Systems eine ganz neue Dynamik zu verleihen. Manchmal finden diese neuen Dynamiken nützliche Anwendung, während sie manchmal nur interessant sind.

Mit in Speichergeräte programmierten Nachschlagetabellen erzeugt die Rückmeldung von den Datenausgängen zurück zu den Adresseingängen einen ganz neuen Gerätetyp:die Finite State Machine , oder FSM :

Die obige Schaltung veranschaulicht die Grundidee:Die an jeder Adresse gespeicherten Daten werden zum nächsten Speicherort, an den das ROM adressiert wird. Das Ergebnis ist eine bestimmte Folge von Binärzahlen (die der im ROM programmierten Folge folgt) am Ausgang im Laufe der Zeit.

Um jedoch Signal-Timing-Probleme zu vermeiden, müssen wir die Datenausgänge über ein 4-Bit-D-Flip-Flop wieder mit den Adresseingängen verbinden, damit der Ablauf Schritt für Schritt im Takt eines kontrollierten Taktimpulses abläuft:

Eine Analogie für die Funktionsweise eines solchen Geräts könnte eine Reihe von Postfächern sein, von denen jedes eine Identifikationsnummer an der Tür (die Adresse) trägt und jedes ein Stück Papier mit der Adresse eines anderen Postfachs enthält. Feld darauf geschrieben (die Daten). Eine Person, die das erste Postfach öffnet. Box, würde darin die Adresse des nächsten Postfachs finden. Box zu öffnen.

Durch das Speichern eines bestimmten Adressenmusters im P.O. Schachteln können wir die Reihenfolge bestimmen, in der jede Schachtel geöffnet wird und somit die Reihenfolge, in der das Papier gelesen wird.

Mit 16 adressierbaren Speicherplätzen im ROM hätte diese Finite State Machine 16 verschiedene stabile „Zustände“, in denen sie sich verriegeln könnte. In jedem dieser Zustände würde die Identität des nächsten Zustands in das ROM einprogrammiert und wartet auf das Signal des nächsten Taktimpulses, das als Adresse an das ROM zurückgeführt wird.

Eine nützliche Anwendung eines solchen FSM wäre die Generierung einer willkürlichen Zählsequenz, wie zum Beispiel Gray Code:

Adresse -----> Daten-Gray-Code-Zählsequenz:0000 -------> 0001 0 0000 0001 -------> 0011 1 0001 0010 -------> 0110 2 0011 0011 -------> 0010 3 0010 0100 -------> 1100 4 0110 0101 -------> 0100 5 0111 0110 -------> 0111 6 0101 0111 -------> 0101 7 0100 1000 -------> 0000 8 1100 1001 -------> 1000 9 1101 1010 -------> 1011 10 1111 1011 -------> 1001 11 1110 1100 -------> 1101 12 1010 1101 -------> 1111 13 1011 1110 -------> 1010 14 1001 1111 -------> 1110 15 1000 

Versuchen Sie, der Gray-Code-Zählsequenz so zu folgen, wie es der FSM tun würde:Beginnen Sie mit 0000, folgen Sie den unter dieser Adresse (0001) gespeicherten Daten bis zur nächsten Adresse usw. (0011) usw. (0010) usw on (0110) usw. Das Ergebnis für die gezeigte Programmtabelle ist, dass die Adressierungssequenz scheinbar willkürlich von Adresse zu Adresse springt, aber wenn Sie jede Adresse überprüfen, auf die zugegriffen wird, werden Sie feststellen, dass es folgt der richtigen Reihenfolge für 4-Bit-Gray-Code.

Wenn die FSM ihren letzten programmierten Zustand (Adresse 1000) erreicht, sind die dort gespeicherten Daten 0000, was die gesamte Sequenz wieder bei Adresse 0000 im Schritt mit dem nächsten Taktimpuls beginnt.

Wir könnten die Fähigkeiten der obigen Schaltung erweitern, indem wir ein ROM mit mehr Adressleitungen verwenden und mehr Programmierdaten hinzufügen:

Genau wie die Nachschlagetabellen-Addiererschaltung, die wir in eine arithmetische Logikeinheit (+, -, x, / Funktionen) verwandelt haben, indem wir mehr Adressleitungen als "Funktionssteuer"-Eingänge verwenden, kann dieser FSM-Zähler verwendet werden, um mehr zu generieren als eine Zählsequenz, eine andere Sequenz programmiert für die vier Rückmeldebits (A0 bis A3) für jede der beiden Funktionssteuerleitungseingangskombinationen (A4 =0 oder 1).

Adresse -----> Datenadresse -----> Daten 00000 -------> 0001 10000 -------> 0001 00001 -------> 0010 10001 -------> 0011 00010 -------> 0011 10010 -------> 0110 00011 -------> 0100 10011 -------> 0010 00100 -------> 0101 10100 -------> 1100 00101 -------> 0110 10101 -------> 0100 00110 -------> 0111 10110 -------> 0111 00111 -------> 1000 10111 -------> 0101 01000 -------> 1001 11000 -------> 0000 01001 -------> 1010 11001 -------> 1000 01010 -------> 1011 11010 -------> 1011 01011 -------> 1100 11011 -------> 1001 01100 -------> 1101 11100 -------> 1101 01101 -------> 1110 11101 -------> 1111 01110 -------> 1111 11110 -------> 1010 01111 -------> 0000 11111 -------> 1110 

Wenn A4 0 ist, zählt der FSM binär; wenn A4 1 ist, zählt die FSM im Gray-Code. In jedem Fall ist die Zählreihenfolge willkürlich:bestimmt durch die Laune des Programmierers. Aus diesem Grund muss die Zählsequenz nicht einmal 16 Schritte umfassen, da der Programmierer entscheiden kann, dass die Sequenz bei jedem der Schritte auf 0000 zurückgesetzt wird. Es ist ein völlig flexibles Zählgerät, dessen Verhalten streng durch die Software (Programmierung) im ROM bestimmt wird.

Wir können die Fähigkeiten des FSM noch erweitern, indem wir einen ROM-Chip mit zusätzlichen Adresseingangs- und Datenausgangsleitungen verwenden. Nehmen Sie zum Beispiel die folgende Schaltung:

Hier werden die Datenausgänge D0 bis D3 ausschließlich zur Rückmeldung an die Adressleitungen A0 bis A3 verwendet. Die Datumsausgabeleitungen D4 bis D7 können so programmiert werden, dass sie etwas anderes als den „Status“-Wert des FSM ausgeben. Da vier Datenausgangsbits auf vier Adressbits zurückgeführt werden, ist dies immer noch ein Gerät mit 16 Zuständen.

Da die Ausgabedaten jedoch von anderen Datenausgabeleitungen stammen, hat der Programmierer mehr Freiheit bei der Konfiguration von Funktionen als zuvor. Mit anderen Worten, dieses Gerät kann weit mehr als nur zählen! Der programmierte Ausgang dieses FSM hängt nicht nur vom Zustand der Rückmeldeadressleitungen (A0 bis A3) ab, sondern auch vom Zustand der Eingangsleitungen (A4 bis A7).

Auch der Taktsignaleingang des D-Flip/Flops muss nicht von einem Impulsgenerator kommen. Um die Sache interessanter zu machen, könnte das Flip/Flop bei einem externen Ereignis mit dem Takt verbunden werden, sodass der FSM nur dann in den nächsten Zustand geht, wenn ein Eingangssignal ihn dazu auffordert.

Jetzt haben wir ein Gerät, das die Bedeutung des Wortes „programmierbar“ besser erfüllt. Die in das ROM geschriebenen Daten sind im wahrsten Sinne des Wortes ein Programm:Die Ausgaben folgen einer vorgegebenen Reihenfolge basierend auf den Eingaben in das Gerät und in welchem ​​„Schritt“ sich das Gerät in seiner Reihenfolge befindet.

Dies kommt dem Bedienkonzept der Turing-Maschine sehr nahe , ein theoretisches Rechengerät, das von Alan Turing erfunden wurde und mathematisch bewiesen ist, dass es in der Lage ist, jedes bekannte arithmetische Problem zu lösen, wenn genügend Speicherkapazität vorhanden ist.