Lez.
5 – Circuiti sequenziali e Macchine a Stati Finiti
Laboratorio di Architettura degli Elaboratori
Michele Lora
7 Dicembre 2023
Outline
1 Circuiti Sequenziali e Macchine a Stati Finiti
2 Circuiti sequenziali in SIS
3 Circuiti sequenziali in Verilog
4 Esercizi
Michele Lora Macchine a Stati Finiti 7 Dicembre 2023 2 / 27
Outline
1 Circuiti Sequenziali e Macchine a Stati Finiti
2 Circuiti sequenziali in SIS
3 Circuiti sequenziali in Verilog
4 Esercizi
Michele Lora Macchine a Stati Finiti 7 Dicembre 2023 3 / 27
Finite State Machine
Un circuito sequenziale può essere modellato utilizzando una macchina
a stati finiti (Finite State Machine - FSM) definita come una 6-upla
M = (S, I , O, δ, λ, s) dove:
S insieme degli stati
I insieme degli ingressi
O insieme delle uscite
δ funzione di stato prossimo che ad una coppia (ingresso, stato
presente) associa lo stato prossimo
λ funzione d’uscita che associa un valore per l’uscita ad uno
stato presente (FSM di Moore) oppure ad una coppia
(ingresso, stato presente) (FSM di Mealy )
s stato di reset (a volte potrebbe non essere definito)
Michele Lora Macchine a Stati Finiti 7 Dicembre 2023 4 / 27
State Transition Graph
Solitamente una FSM si rappresenta per mezzo di un grafo delle
transizioni (State Transition Graph - STG) dove i nodi sono gli stati e gli
archi rappresentano le transizioni da uno stato all’altro. Ad ogni transizione
corrisponde un insieme dei valori di ingresso ed un insieme dei valori di
uscita.
Michele Lora Macchine a Stati Finiti 7 Dicembre 2023 5 / 27
Sincronismo
I circuiti sequenziali possono essere sincroni se i valori delle uscite
assumono significato in corrispondenza di un evento su un segnale di
sincronismo (solitamente detto clock), oppure asincroni se i valori delle
uscite cambiano al variare degli ingressi senza tener conto del segnale di
sincronismo.
Michele Lora Macchine a Stati Finiti 7 Dicembre 2023 6 / 27
Memoria
L’uscita di un circuito sequenziale dipende dai valori in ingresso anche negli
istanti passati, occorre quindi una sorta di memoria di tale storia passata.
Questa memoria è rappresentata dallo stato.
L’elettronica digitale mette a disposizione due tipi di componenti detti
latch e flip-flop in grado di memorizzare il valore di un bit (stato binario).
Occorre quindi codificare tutti gli stati che può assumere il circuito
mediante dei numeri binari e poi utilizzare dei latch o flip-flop per
memorizzare tali numeri.
Michele Lora Macchine a Stati Finiti 7 Dicembre 2023 7 / 27
Memoria
L’uscita di un circuito sequenziale dipende dai valori in ingresso anche negli
istanti passati, occorre quindi una sorta di memoria di tale storia passata.
Questa memoria è rappresentata dallo stato.
L’elettronica digitale mette a disposizione due tipi di componenti detti
latch e flip-flop in grado di memorizzare il valore di un bit (stato binario).
Occorre quindi codificare tutti gli stati che può assumere il circuito
mediante dei numeri binari e poi utilizzare dei latch o flip-flop per
memorizzare tali numeri.
Una FSM con N stati necessita di log2 N componenti di memoria
elementari.
Michele Lora Macchine a Stati Finiti 7 Dicembre 2023 7 / 27
Outline
1 Circuiti Sequenziali e Macchine a Stati Finiti
2 Circuiti sequenziali in SIS
3 Circuiti sequenziali in Verilog
4 Esercizi
Michele Lora Macchine a Stati Finiti 7 Dicembre 2023 8 / 27
Circuiti sequenziali in SIS
Per modellare un circuito sequenziale in SIS è necessario definire la tabella
delle transizioni ed eventualmente definire manualmente la codifica degli
stati (esiste un comando che permette di eseguire la codifica in modo
automatico).
Michele Lora Macchine a Stati Finiti 7 Dicembre 2023 9 / 27
Circuiti sequenziali in SIS
1 La tabella delle transizioni deve essere descritta all’interno della
sezione delimitata dalle keyword .start_kiss e .end_kiss. Le
transizioni devono essere specificate come un insieme di righe che
riportano in ordine: valore degli ingressi, stato presente, stato
prossimo, valore delle uscite.
La tabella delle transizioni deve essere preceduta da 5 righe che
specificano:
il numero di segnali di input
il numero di segnali di output
il numero di transizioni
il numero di stati
lo stato di reset
2 Dopo la tabella delle transizioni (dopo .end_kiss) possono essere
riportate le istruzioni necessarie per definire la codifica degli stati
qualora non si decida di farla definire a SIS in modo automatico. La
keyword da utilizzare per definire la codifica è .code seguita dal nome
dello stato e dalla sua codifica binaria.
Michele Lora Macchine a Stati Finiti 7 Dicembre 2023 10 / 27
Esempio – Semaforo con Priorità
Si consideri il classico esempio di un semaforo posto all’incrocio tra una
strada principale (direttrice Nord-Sud, NS) e una secondaria (direttrice
Est-Ovest, EO). Il semaforo può assumere solo i colori verde e rosso ed è
dotato di sensori che rilevano la presenza di traffico. Il circuito che
controlla il semaforo ha 2 segnali di ingresso forniti dai sensori
(TRAFFICONS e TRAFFICOEO) e due di uscita (LUCENS e LUCEEO)
con il seguente significato:
TRAFFICONS[1]: segnala la presenza di traffico lungo la direttrice NS
assumendo il valore 1
TRAFFICOEO[1]: segnala la presenza di traffico lungo la direttrice EO
assumendo il valore 1
LUCENS[1]: deve essere posto a 1 per accendere la luce verde sulla
strada NS. Se viene posto a 0 si accende la luce rossa.
LUCEEO[1]: deve essere posto a 1 per accendere la luce verde sulla
strada EO. Se viene posto a 0 si accende la luce rossa.
Michele Lora Macchine a Stati Finiti 7 Dicembre 2023 11 / 27
Esempio – Semaforo con Priorità
Per evitare incidenti, il circuito di controllo deve garantire che le luci sulle
strade NS e EO siano sempre accese in opposizione. Il circuito assegna
priorità alla strada NS e commuta dal verde al rosso su NS solo se
TRAFFICONS=0 e TRAFFICOEO=1, in caso contrario mantiene il verde
su NS. In assenza di traffico sia su NS che su EO il semaforo non modifica
la configurazione raggiunta. Non appena giunge traffico su NS,
indipendentemente da cosa succede su EO, il semaforo assegna la luce
verde a NS e la luce rossa a EO.
Michele Lora Macchine a Stati Finiti 7 Dicembre 2023 12 / 27
Esempio – Semaforo con Priorità: STT e STG
00 01 10 11
VERDENS VERDENS/10 VERDEEO/01 VERDENS/10 VERDENS/10
VERDEEO VERDEEO/01 VERDEEO/01 VERDENS/10 VERDENS/10
Michele Lora Macchine a Stati Finiti 7 Dicembre 2023 13 / 27
Esempio – Semaforo con Priorità: Implementazione
.model SEMAFORO 00 VERDENS VERDENS 10
.inputs TRAFFICONS TRAFFICOEO 01 VERDENS VERDEEO 01
.outputs LUCENS LUCEEO 1- VERDENS VERDENS 10
.start_kiss 0- VERDEEO VERDEEO 01
.i 2 1- VERDEEO VERDENS 10
.o 2 .end_kiss
.s 2 .code VERDENS 0
.r VERDENS .code VERDEEO 1
.p 5 .end
Michele Lora Macchine a Stati Finiti 7 Dicembre 2023 14 / 27
Minimizzazione ed assegnamento degli stati
4 Dopo aver modellato il circuito, è possibile procedere con la
minimizzazione degli stati. Una volta caricato il file .blif, la
minimizzazione degli stati si esegue con il comando state_minimize
stamina.
5 Generazione logica funzioni δ e λ:
se il file contiene già la codifica binaria degli stati (.code) allora
occorre generare le funzioni δ e λ con il comando stg_to_network
altrimenti occorre assegnare automaticamente gli stati con il comando
state_assign jedi (che genera anche le funzioni δ e λ). Attenzione
che prima occorre minimizzare gli stati e poi farne l’assegnazione.
6 Eseguire la minimizzazione delle funzioni δ e λ, ad esempio lanciando
lo script [Link] come visto per la minimizzazione dei circuiti
combinatori.
Michele Lora Macchine a Stati Finiti 7 Dicembre 2023 15 / 27
Esempio
Si consideri il circuito sequenziale che è in grado di riconoscere la sequenza
di ingresso 00 01 11, (ingresso IN a 2 bit). Il circuito è attivo ed inizia ad
analizzare i valori dell’ingresso IN quando l’ingresso START passa da 0 a 1.
Nello stesso ciclo di clock in cui viene riconosciuta la sequenza 00 01 11,
l’uscita OUT passa da 0 a 1. OUT rimane a 1 fino a quando gli ingressi
assumeranno il valore 10; momento in cui il circuito viene nuovamente
posto in attesa che il segnale START passi da 0 a 1.
Michele Lora Macchine a Stati Finiti 7 Dicembre 2023 16 / 27
Esempio
Scegliendo di codificare gli stati come ATT= 000, NUL= 001, 00 = 010,
01 = 011 e 11 = 100, si ottiene la tabella di verità della funzione dello
stato prossimo e dell’uscita OUT
Michele Lora Macchine a Stati Finiti 7 Dicembre 2023 17 / 27
Outline
1 Circuiti Sequenziali e Macchine a Stati Finiti
2 Circuiti sequenziali in SIS
3 Circuiti sequenziali in Verilog
4 Esercizi
Michele Lora Macchine a Stati Finiti 7 Dicembre 2023 18 / 27
Modellare FSM in Verilog
Dopo aver dichiarato due segnali di stato: uno che contiene lo stato
corrente, e uno che contiene lo stato prossimo. Ad ogni ciclo di clock, lo
stato corrente viene aggiornato con lo stato prossimo.
Due blocchi sequenziali:
Un blocco sincrono al ciclo di clock che aggiorna lo stato utilizzando
lo stato prossimo. Eventualmente, il blocco sequenziale può utilizzare
un costrutto condizionale per gestire la fase di reset.
Un blocco asincrono, sensibile a tutti i segnali di ingresso della
funzione δ, che calcola lo stato prossimo e le uscite.
Michele Lora Macchine a Stati Finiti 7 Dicembre 2023 19 / 27
Esempio – Semaforo con Priorità: Verilog
module semaforo(
input rst, clk, trafficons, trafficoeo,
output reg lucens, luceeo);
reg stato = 1’b0,
stato_prossimo = 1’b0;
always @(posedge clk) begin : SEQ
if(rst) stato = 1’b0;
else stato = stato_prossimo;
end
...
Michele Lora Macchine a Stati Finiti 7 Dicembre 2023 20 / 27
Esempio – Semaforo con Priorità: Verilog
always @(stato, trafficons, trafficoeo) begin : COMB_OUT
case(stato)
1’b0:
if(~trafficons && trafficoeo) begin
lucens = 1’b0; luceeo = 1’b1;
stato_prossimo = 1’b1;
end else begin
lucens = 1’b1; luceeo = 1’b0;
stato_prossimo = 1’b0;
end
1’b1:
if(~trafficons) begin
lucens = 1’b0; luceeo = 1’b1;
stato_prossimo = 1’b1;
end else begin
lucens = 1’b1; luceeo = 1’b0;
stato_prossimo = 1’b0;
end
endcase
end
endmodule
Michele Lora Macchine a Stati Finiti 7 Dicembre 2023 21 / 27
Testbench per circuiti sequenziali
È necessario stimolare il segnale di clock. Si utilizza un costrutto
always temporizzato che inverte il clock.
Si consiglia di utilizzare la funzione $finish al termine del blocco
sequenziale always begin.
Michele Lora Macchine a Stati Finiti 7 Dicembre 2023 22 / 27
Testbench per circuiti sequenziali
module tb_semaforo();
reg rst, clk, trafficons, trafficoeo;
wire lucens, luceeo;
semaforo sem(rst, clk, trafficons, trafficoeo,
lucens, luceeo);
always #10 clk = ~clk;
initial begin
$dumpfile("[Link]");
$dumpvars(1);
clk = 1’b0;
... # Assegnamenti sugli ingressi.
$finish;
end
endmodule
Michele Lora Macchine a Stati Finiti 7 Dicembre 2023 23 / 27
Outline
1 Circuiti Sequenziali e Macchine a Stati Finiti
2 Circuiti sequenziali in SIS
3 Circuiti sequenziali in Verilog
4 Esercizi
Michele Lora Macchine a Stati Finiti 7 Dicembre 2023 24 / 27
Esercizio 1
Realizzare, sia in Verilog che in SIS, il circuito sequenziale (2 ingressi, 2
uscite) corrispondente alla seguente tabella degli stati. Sia A lo stato di
reset. Utilizzare l’implementazione SIS per minimizzare il numero degli stati
e ottimizzare la logica combinatoria.
Michele Lora Macchine a Stati Finiti 7 Dicembre 2023 25 / 27
Esercizio 2
Realizzare un circuito sequenziale con due ingressi binari in grado di
riconoscere la sequenza 00 11 00 01. Si verifichi il comportamento del
circuito durante il riconoscimento della sequenza 00 11 00 11 00 01.
Michele Lora Macchine a Stati Finiti 7 Dicembre 2023 26 / 27
Esercizio 3
Su due linee vengono trasmessi serialmente dei numeri binari a partire dal
bit meno significativo (un bit ogni colpo di clock). Si progetti un
sommatore seriale in grado di fornire in uscita, per ogni colpo di clock
relativo a ciascun bit trasmesso, il corrispondente bit di somma.
Minimizzare il numero degli stati e ottimizzare la logica combinatoria nei 2
casi:
1 codifica manuale degli stati
2 codifica automatica degli stati
Michele Lora Macchine a Stati Finiti 7 Dicembre 2023 27 / 27
