Modellazione e minimizzazione circuiti sequenziali

Laboratorio di Architettura degli Elaboratori
Graziano Pravadelli, Davide Quaglia
Dipartimento di Informatica – Università di Verona
Modellazione e minimizzazione
di Circuiti Sequenziali
In questa lezione vengono riassunti i concetti fondamentali per la modellazione e la
minimizzazione dei circuiti sequenziali mediante SIS.
Concetti fondamentali sulla modellazione di circuiti sequenziali
I circuiti sequenziali sono circuiti il cui comportamento dipende non solo dai valori
assunti dai segnali di ingresso nel momento presente ma anche dai loro valori negli
istanti passati.
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 è l’insieme degli stati;
- I è l’insieme degli ingressi;
- O è l’insieme delle uscite;
-  è la funzione di stato prossimo che ad una coppia (ingresso, stato presente)
associa lo stato prossimo;
-  è la funzione d’uscita che
o ad una coppia (ingresso, stato presente) associa un valore per l’uscita
(FSM di Mealy);
o ad uno stato presente associa un valore per l’uscita (FSM di Moore);
- s è lo stato di reset (a volte potrebbe non essere definito).
Quando il valore delle uscite dipende sia dallo stato presente sia dagli ingressi parliamo
di FSM di Mealy, quando invece il valore delle uscite dipende solo dallo stato presente
parliamo di FSM di Moore. In seguito tratteremo solo FSM di Mealy.
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.
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.
Siccome il comportamento delle uscite di un circuito sequenziale dipende dai valori in
ingresso anche negli istanti passati occorre che esso contenga una sorta di memoria di
tale storia passata. Questa memoria è rappresentata dallo stato. La realizzazione pratica
di un circuito sequenziale pertanto richiede la presenza di elementi di memoria per la
memorizzazione dello 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 ⌈log 2 N ⌉ componenti di memoria elementari.
La codifica scelta ha un notevole impatto sulla possibile minimizzazione del circuito.
Esistono diverse regole che permettono di assegnare la codifica in modo da minimizzare
la logica del circuito in base a area, ritardo, consumo di potenza, ecc.
Di seguito vengono riassunti i passi da eseguire per modellare, minimizzare e mappare
su una libreria tecnologica un circuito sequenziale di cui sia nota una descrizione
informale.
1. Rappresentare il diagramma degli stati.
2. Estrarre la tabella degli stati dal diagramma degli stati
3. Minimizzare gli stati della FSM mediante l’algoritmo di Paull-Unger (tabella
delle implicazioni).
4. Assegnare una codifica agli stati.
5. Estrarre la tabella delle transizioni a partire dalla tabella degli stati e dalla
codifica scelta.
6. Estrarre la tabella delle eccitazioni da cui è possibile estrarre la logica
combinatoria che descrive la funzione di stato prossimo e la funzione di uscita.
7. Effettuare la minimizzazione delle logica combinatoria.
8. Effettuare il mapping tecnologico.
Per approfondimenti sulle operazioni sopra elencate si faccia riferimento ai capitoli 5, 6
del libro “Progettazione digitale” (2a edizione) di F. Fummi, C. Silvano, M. Sami.
Modellazione e minimizzazione di circuiti sequenziali in SIS
Per modellare un circuito sequenziale in SIS è necessario definire la tabella delle
transizioni ed eventualmente la codifica degli stati (esiste un comando che permette di
eseguire la codifica in modo automatico).
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 e lo stato di reset. 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.
Dopo aver modellato il circuito, è possibile procedere con la minimizzazione degli stati.
Una volta caricato il file .blif con il comando read_blif, la minimizzazione degli
stati si esegue con il comando state_minimize stamina. Se il file contiene già la
codifica binaria degli stati (.code) allora occorre generare le funzioni  e  col
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.
Quindi è possibile eseguire la minimizzazione delle funzioni  e , ad esempio
lanciando lo script script.rugged come visto per la minimizzazione dei circuiti
combinatori.
Eseguendo print_stats dopo stg_to_network oppure state_assign
jedi si noterà che viene valorizzato il campo latches che indica il numero di
elementi di memoria utilizzati nel circuito per memorizzare lo stato.
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. La seguente figura
illustra il grafo di transizione degli stati.
Nello stato ATT, il circuito è in attesa che il segnale di start commuti da 0 a 1. Gli altri 4
stati indicano che una porzione della sequenza è stata riconosciuta. Si noti che se nello
stato 01 viene applicato l’input 00, l’automa anziché portarsi nello stato NUL si sposta
nello stato 00 riconoscendo l’inizio di una sequenza valida. Scegliendo di codificare gli
stati come ATT = 000, NUL = 001, 00 = 010, 01 = 011 e 11 = 100, si riporta di seguito
la tabella di verità della funzione dello stato prossimo e dell’uscita OUT. Lo stato
attuale è codificato mediante i bit a2 a1 a0, mentre lo stato prossimo è codificato con
i bit s2 s1 s0.
La rappresentazione nel formato blif è la seguente:
.model automa
.inputs START IN1 IN0
.outputs OUT
.start_kiss
.i 3
.o 1
.s 5
.p 15
.r ATT
#numero di segnali di ingresso
#numero di segnali di uscita
#numero di stati
#numero di transizioni
#stato di reset
#tabella delle transizioni
#(ingressi, stato presente, stato prossimo, uscita)
0-- ATT ATT 0
1-- ATT NUL 0
--1 NUL NUL 0
-1- NUL NUL 0
-00 NUL 00 0
-00 00 00 0
-1- 00 NUL 0
-01 00 01 0
-00 01 00 0
-10 01 NUL 0
-01 01 NUL 0
-11 01 11 1
--1 11 11 1
-0- 11 11 1
-10 11 ATT 0
.end_kiss
#codifica degli stati.
#E’ opzionale perché può essere calcolata automaticamente
#tramite il comando state_assign jedi
.code ATT 000
.code NUL 001
.code 00 010
.code 01 011
.code 11 100
.end
Una volta caricato il file blif con il comando read_blif, è possibile creare le funzioni
per lo stato prossimo e per l’output con il comando stg_to_network in quanto
l'assegnazione degli stati è già stata fatta manualmente.
Comandi utili di SIS
read_blif
simulate i0 i1 i2 …
print_stats
write_blif
write_eqn
stg_to_network
state_assign jedi
state_minimize stamina
write_kiss
Carica la descrizione blif del circuito
Simula il circuito in base ai valori forniti per gli
ingressi. Esecuzioni successive del comando
considerano lo stato in cui il circuito si è portato
dopo l’ultima esecuzione
Visualizza informazioni sul circuito
Visualizza la descrizione blif del circuito.
Visualizza le equazioni booleane corrispondenti ai
nodi del circuito
Costruisce le funzioni di stato prossimo e di uscita a
partire dalla tabella delle transizioni e dalla codifica
degli stati
Usa l’algoritmo jedi per effettuare automaticamente
la codifica degli stati; costruisce anche le funzioni di
stato prossimo e di uscita
Usa l’algoritmo stamina per minimizzare gli stati
della FSM
Visualizza la tabella delle transizioni
Utilizzo di BVE per la definizione del diagramma degli stati
BVE è un’applicazione realizzata da un gruppo di studenti dell’Università di Verona
che permette di progettare graficamente circuiti digitali. Con il BVE è possibile
realizzare circuiti digitali in formato blif semplicemente utilizzando il mouse e
“disegnando” il circuito sullo schermo. E’ possibile progettare sia una FSM che un
datapath.
Un nuovo progetto in BVE
1. Lanciare il BVE con il comando bve.
2. Selezionare New Project… dalla schermata iniziale ( nella versione Beta non è
implementata la funzione Load Project…, i progetti vanno aperti singolarmente
dall’interno delle due sezioni distinte).
3. Selezionare il tipo di progetto: Data Path o FSM.
Creazione di un circuito combinatorio con BVE: Half-Adder
1. Nella finestra Set In&Out inserire inputs e ouputs del circuito con il relativo
numero di bits. L’Half-Adder riceve in ingresso due bit A e B e ne calcola la
somma restituendo in uscita SUM e il riporto CARRY. Perciò è necessario creare
due input da 1 bit, A e B, e due output da 1 bit, SUM e CARRY.
2. Gli ingressi e le uscite vengono visualizzati su di un foglio all’interno della
finestra del progetto. Sulla sinistra nella parte superiore vi è la libreria dei
sottocircuiti, nella parte inferiore l’Object Browser che mostra gli oggetti inseriti
sul foglio, come inputs, outputs, bus e sottocircuiti.
3. Per generare le uscite sono necessarie due porte logiche: un AND per generare
CARRY e uno XOR per generare SUM. Poiché tali porte non sono presenti nella
libreria, è necessario procedere al loro inserimento utilizzando il tool di disegno.
4. Sulla destra in alto cliccare sull’icona Load a Subckt. Viene visualizzata una
finestra che richiede l’inserimento del sottocircuito. Per crearne uno nuovo fare
click su Editor. Viene visualizzata una finestra simile a quella del Set In&Out.
5. Generare un sottocircuito per la porta logica AND inserendo due inputs, IN1 e
IN2, e un output, OUT, dopo aver inserito il nome della porta (AND) nel textbox
Module Name.
6. Viene ora richiesto di inserire la tabella delle verità per la porta AND. E’
necessario definire on-set e don’t-care-set. Order specifica per quale uscita si sta
specificando la tabella delle verità. Nel nostro caso l’uscita è unica, pertanto la
tabella delle verità richiesta è una sola. Introdurre il seguente testo controllando
di inserire uno spazio tra gli ingressi e le uscite: 11 1.
7. Cliccando su Ok viene visualizzata una piccola finestra dove è possibile
disegnare l’immagine che rappresenterà la porta AND all’interno del circuito. Gli
ingressi vengono posti sul lato superiore dell’immagine e le uscite sul lato
inferiore. E’ possibile, ad esempio, disegnare un ovale (rispettando i limiti
dell’area di disegno) e inserire al suo interno l’etichetta di testo “AND”.
8. Una volta terminato il disegno si procede al salvataggio dal menu File, Save
as… Il salvataggio crea due files, un .BVG che contiene i dati grafici e un .BLIF
che è l’effettivo formato blif utilizzato in SIS. Salvare AND.bvg e AND.blif.
9. Una volta salvati i files chiudere la finestra del BVE Graphic Editor. La porta
AND è stata creata. E’ necessario inserirla nella libreria di progetto in modo da
poterla importare ad ogni necessità. All’interno della finestra da dove è stato
lanciato l’editor grafico inserire il nome della porta AND. Tramite Choose
scegliere il file bvg appena creato e il relativo file blif. Cliccando su Ok, la porta
AND viene aggiunta all’interno della libreria.
10. Eseguire la stessa procedura per creare la porta XOR, creando il sottocircuito
mediante il BVE Graphic Editor e inserendo i file BVG e BLIF all’interno della
libreria.
11. E’ possibile salvare la libreria di oggetti in modo tale da poterla caricare ad ogni
apertura del BVE.
12. Ora tutte le porte necessario per la realizzazione dell’Half-Adder sono pronte. E’
possibile procedere alla sua progettazione.
13. Selezionare dalla libreria la porta AND e cliccare sull’icona di inserimento
Subckt
nella barra degli strumenti in alto. Ciccare all’interno del foglio dove
si vuole inserire la porta AND. Eventualmente spostare a piacimento il
sottocircuito mediante l’icona
.
14. Ora procedere al collegamento. Selezionare l’icona Draw Bus
. Cliccare
sull’input A, all’interno del cerchio, e tracciando delle linee ortogonali collegarsi
al quadratino blu sulla parte alta della porta AND. Notare che non è possibile
creare linee oblique, perciò non bisogna assolutamente cercare di collegare un
input ad un subckt con una linea non ortogonale. In caso contrario, il
collegamento viene effettuato, ma la linea, essendo obliqua, non viene
visualizzata poiché non è riproducibile in un circuito. Ciò potrebbe dare origine
ad errori in fase di scrittura del file blif.
15. Allo stesso modo creare il collegamento tra l’ingresso B e l’input del subckt
AND. Viene visualizzata una finestra dove è possibile gestire e modificare il
collegamento tra il bus e l’ingresso del subckt. Nel nostro della porta AND non vi
è alcuna differenza tra input 1 e 2, perciò lasciare tutto invariato.
16. Collegare l’uscita della porta AND all’uscita CARRY.
17. Ripetere lo stesso procedimento per la porta XOR e collegarla all’uscita SUM.
18. La creazione dell’ Half-Adder è terminata. Procedere al salvataggio. Viene
generato un file blif contenente tutte le informazioni riguardanti il progetto
appena definito. Il file Blif generato è compatibile con SIS ma per sicurezza si
consiglia di controllarlo manualmente visualizzandolo con un editor di testo. Le
linee che iniziano con il carattere # sono commenti e vengono ignorate da SIS
mentre sono essenziali per la riapertura del progetto tramite BVE, quindi non
modificarle.
Creazione di un circuito sequenziale con BVE: 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.
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.
Per realizzare il circuito usando BVE eseguire i seguenti passi:
1. Creare un nuovo progetto di tipo Finite State Machine. Nella prima finestra
introdurre il nome del progetto: Semaforo, gli input: TRAFFICONS e
TRAFFICOEO, e gli outputs: LUCENS e LUCEEO. Cliccando su Ok viene
visualizzata la finestra con l’area di disegno.
2. Generare i due stati della FSM: quello dove la luce verde e assegnata alla
direttrice NS (VERDENS) e quello dove il verde è assegnato alla direttrice EO
(VERDEEO). Lo stato di reset è VERDENS.
3. Cliccare sull’icona rossa nella barra strumenti e cliccare sull’area di disegno.
Viene visualizzato l’Object Inspector. Inserire come Label VERDENS e
selezionare Set as Reset. Cliccare su Apply e poi su Close.
4. Ripetere la stessa procedura per creare lo stato VERDEEO, ma non selezionare
Set as Reset.
5. Cliccare sull’icona a forma di freccia che si trova alla destra dell’icona Stato per
inserire le transizioni. Cliccare sullo stato VERDENS e poi sullo stato VERDEEO
per generare la relativa transizione tra i 2 stati. Si apre una finestra dove
specificare gli input e gli output. Ricordando l’ordine compilare gli input e gli
output di tale transizione.
6. Ripetere la procedura per tutte le transizioni della FSM fino ad ottenere quella
completa.
7. Una volta terminato il disegno, salvare il progetto. Verrà generato un file blif
perfettamente compatibile con SIS, salvo imperfezioni sintattiche da verificare
manualmente.
Esercizi
Esercizio 1:
Realizzare il circuito sequenziale (2 ingressi, 2 uscite) corrispondente
alla seguente tabella degli stati. Sia A lo stato di reset.
Minimizzare il numero degli stati e ottimizzare la logica combinatoria.
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.
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:
a) codifica manuale degli stati;
b) codifica automatica degli stati.