Fondamenti di informatica - Laurea triennale Informatica/Circuiti sequenziali e macchine a stati finiti

I circuiti sequenziali e le macchine a stati finiti, mostrando come un sistema digitale possa produrre uscite che dipendono non solo dagli ingressi correnti, ma anche dallo stato interno precedente.

Nei circuiti sequenziali, il tempo è considerato discreto: lo stato del sistema cambia a intervalli successivi. Per rappresentare la memoria del passato si introduce il ritardo unitario, un dispositivo che riceve un bit a un certo istante e lo restituisce all’istante successivo. Questo permette a un circuito di “ricordare” informazioni precedenti.

Un primo esempio è il sommatore seriale, che somma due numeri binari ricevendo una coppia di bit alla volta. Il circuito usa un sommatore full adder e un circuito di ritardo unitario per conservare il riporto prodotto al passo precedente. In questo modo, a ogni istante vengono sommati i due bit correnti più l’eventuale riporto precedente, producendo il bit di somma e un nuovo riporto.

La macchina a stati finiti

Una macchina a stati finiti è definita da:

• un insieme finito di simboli di input
• un insieme finito di simboli di output
• un insieme finito di stati
• una funzione che determina lo stato successivo
• una funzione che determina l’output e uno stato iniziale.

Questo modello rappresenta una macchina con una memoria interna limitata.

Le macchine a stati finiti possono essere descritte tramite una tabella oppure tramite un diagramma di transizione. Nel diagramma, i vertici rappresentano gli stati, mentre gli archi indicano come la macchina cambia stato in base all’input ricevuto. Ogni arco è etichettato con la forma input/output, cioè indica quale simbolo in ingresso causa quella transizione e quale simbolo viene prodotto.

Un esempio di tabella di transizione di stato per una macchina M e del corrispondente diagramma di stato è il seguente:

Tabella di transizione di stato Stato\Input 1 0 S1 S1 S2 S2 S2 S1

Diagramma di stato

Tutti i possibili input in ingresso alla macchina sono nelle colonne della tabella. Tutti i possibili stati sono nelle righe. È possibile vedere che se la macchina è nello stato S₁ (la prima riga), e l'input successivo è il carattere 1, allora la macchina rimarrà nello stato S₁. Se l'input è un carattere 0, la macchina eseguirà una transizione verso lo stato S₂, come può essere visto nella seconda colonna. Nel diagramma, lo stesso comportamento può essere osservato con la freccia diretta da S₁ verso S₂, etichettata con un carattere 0.

Il circuito Flip-Flop

Il circuito flip-flop SR che abbiamo già visto a inizio libro è un componente fondamentale dei circuiti digitali perché funziona come una memoria a un bit. Il flip-flop SR “ricorda” se l’ultimo valore attivo è stato quello di set oppure quello di reset. Anche questo dispositivo può essere modellato come una macchina a stati finiti con due stati, corrispondenti al fatto che sia stato attivato più recentemente S oppure R.