Finite-state machine

Feedback is een fascinerend technisch principe. Het kan een vrij eenvoudig apparaat of proces veranderen in iets dat aanzienlijk complexer is. We hebben de effecten gezien van feedback die opzettelijk is geïntegreerd in circuitontwerpen met een aantal nogal verbazingwekkende effecten:

• Comparator + negatieve feedback—————-> versterker met regelbare versterking
• Vergelijker + positieve feedback—————-> vergelijker met hysterese
• Combinatielogica + positieve feedback—> multivibrator

Op het gebied van procesinstrumentatie wordt feedback gebruikt om een ​​eenvoudig meetsysteem om te zetten in iets dat controleerbaar is:

• Meetsysteem + negatieve feedback—-> gesloten regelsysteem

Feedback, zowel positief als negatief, heeft de neiging om een ​​geheel nieuwe dynamiek toe te voegen aan de werking van een apparaat of systeem. Soms vinden deze nieuwe dynamieken een nuttige toepassing, andere keren zijn ze alleen maar interessant.

Met opzoektabellen die in geheugenapparaten zijn geprogrammeerd, creëert feedback van de gegevensuitvoer terug naar de adresinvoer een geheel nieuw type apparaat:de Finite State Machine , of FSM :

Het bovenstaande circuit illustreert het basisidee:de gegevens die op elk adres zijn opgeslagen, worden de volgende opslaglocatie waaraan de ROM wordt geadresseerd. Het resultaat is een specifieke reeks binaire getallen (volgens de reeks die in de ROM is geprogrammeerd) aan de uitgang, in de loop van de tijd.

Om problemen met de signaaltiming te voorkomen, moeten we de data-uitgangen echter weer verbinden met de adresingangen via een 4-bit D-type flip-flop, zodat de reeks stap voor stap plaatsvindt op de maat van een gecontroleerde klokpuls:

Een analogie voor de werking van zo'n apparaat zou een reeks postbussen kunnen zijn, elk met een identificatienummer op de deur (het adres), en elk met een stuk papier met het adres van een andere postbus. vakje erop geschreven (de gegevens). Een persoon die de eerste postbus opent doos, zou daarin het adres van de volgende postbus vinden. vak om te openen.

Door een bepaald patroon van adressen op te slaan in de P.O. dozen, kunnen we de volgorde dicteren waarin elke doos wordt geopend, en dus de volgorde waarin het papier wordt gelezen.

Met 16 adresseerbare geheugenlocaties in de ROM, zou deze Finite State Machine 16 verschillende stabiele "states" hebben waarin hij zou kunnen vergrendelen. In elk van die toestanden zou de identiteit van de volgende toestand in de ROM worden geprogrammeerd, in afwachting van het signaal van de volgende klokpuls die als een adres naar de ROM wordt teruggevoerd.

Een nuttige toepassing van zo'n FSM zou zijn om een ​​willekeurige telreeks te genereren, zoals Gray Code:

Adres -----> Data Gray Code-tellingsvolgorde: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 

Probeer de Gray Code-tellingsvolgorde te volgen zoals de FSM het zou doen:beginnend bij 0000, volg de gegevens die op dat adres (0001) zijn opgeslagen tot het volgende adres, enzovoort (0011), enzovoort (0010), enzovoort op (0110), enz. Het resultaat, voor de getoonde programmatabel, is dat de volgorde van adresseren rondspringt van adres naar adres op wat lijkt op een lukrake manier, maar wanneer u elk adres controleert dat wordt geopend, zult u zien dat het volgt de juiste volgorde voor 4-bits grijze code.

Wanneer de FSM de laatst geprogrammeerde status bereikt (adres 1000), zijn de gegevens die daar zijn opgeslagen 0000, die de hele reeks opnieuw begint op adres 0000 in de pas met de volgende klokpuls.

We zouden de mogelijkheden van het bovenstaande circuit kunnen uitbreiden door een ROM met meer adreslijnen te gebruiken en meer programmeergegevens toe te voegen:

Nu kan deze FSM-teller worden gebruikt om meer adresregels te gebruiken als "functiecontrole" -ingangen, net als het opzoektabel-optellercircuit dat we hebben omgezet in een rekenkundige logische eenheid (+, -, x, / functies) dan één telreeks, een andere reeks geprogrammeerd voor de vier feedbackbits (A0 t/m A3) voor elk van de twee functiecontrolelijningangscombinaties (A4 =0 of 1).

Adres -----> Gegevens Adres -----> Gegevens 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 

Als A4 0 is, telt de FSM binair; als A4 1 is, telt de FSM in grijze code. In beide gevallen is de telvolgorde willekeurig:bepaald door de grillen van de programmeur. Overigens hoeft de telreeks niet eens 16 stappen te hebben, aangezien de programmeur kan besluiten om de reeks bij een van de stappen helemaal naar 0000 te laten recyclen. Het is een volledig flexibel telapparaat, het gedrag wordt strikt bepaald door de software (programmering) in de ROM.

We kunnen de mogelijkheden van de FSM nog verder uitbreiden door gebruik te maken van een ROM-chip met extra adresinvoer- en gegevensuitvoerlijnen. Neem bijvoorbeeld het volgende circuit:

Hier worden de D0 t/m D3-data-uitgangen uitsluitend gebruikt voor terugkoppeling naar de A0 t/m A3-adreslijnen. Datumuitvoerlijnen D4 tot en met D7 kunnen worden geprogrammeerd om iets anders uit te voeren dan de "status" -waarde van de FSM. Omdat er vier data-uitvoerbits worden teruggekoppeld naar vier adresbits, is dit nog steeds een apparaat met 16 statussen.

Als de uitvoergegevens echter afkomstig zijn van andere gegevensuitvoerlijnen, heeft de programmeur meer vrijheid om functies te configureren dan voorheen. Met andere woorden, dit apparaat kan veel meer dan alleen tellen! De geprogrammeerde uitvoer van deze FSM is niet alleen afhankelijk van de status van de terugmeldadreslijnen (A0 tot A3), maar ook van de status van de invoerlijnen (A4 tot A7).

De kloksignaalingang van het D-type flip/flop hoeft ook niet van een pulsgenerator te komen. Om het nog interessanter te maken, kan de flip/flop worden aangesloten op de klok op een externe gebeurtenis, zodat de FSM alleen naar de volgende status gaat als een ingangssignaal dat aangeeft.

Nu hebben we een apparaat dat beter voldoet aan de betekenis van het woord 'programmeerbaar'. De gegevens die naar de ROM worden geschreven, zijn een programma in de ware zin van het woord:de uitgangen volgen een vooraf vastgestelde volgorde op basis van de invoer naar het apparaat en op welke "stap" het apparaat zich in de volgorde bevindt.

Dit komt heel dicht in de buurt van het bedieningsontwerp van de Turing Machine , een theoretisch computerapparaat uitgevonden door Alan Turing, waarvan wiskundig bewezen is dat het in staat is om elk bekend rekenkundig probleem op te lossen, met voldoende geheugencapaciteit.