Appunti di Elettronica DigitaleAppunti di Elettronica DigitaleCapitolo 5 - Macchine asincrone
Introduzione ............................................................................................... 1Circuiti asincroni in modo fondamentale.......................................................... 5
Metodo di sintesi ........................................................................................ 5Esempio: latch asincrono di tipo J-K .................................................... 6
Esempio: misuratore di riflessi ................................................................. 14Problema dell’assegnamento nelle macchine sequenziali asincrone .......... 26
Esempio .............................................................................................. 35Esempio: misuratore di riflessi ........................................................... 39
Circuiti asincroni in modo impulsivo ............................................................. 44Introduzione ............................................................................................. 44Esempio: macchina distributrice di bibite ................................................. 45
Alee nei circuiti sequenziali asincroni............................................................ 55Introduzione ............................................................................................. 55Esempio.................................................................................................... 57
INTRODUZIONE
Sappiamo che un circuito sequenziale generico è specificato da unasequenza temporale di ingressi, di uscite e di stati, secondo lo schemadella figura seguente:
Appunti di “Elettronica dei Sistemi Digitali” - Capitolo 5
Autore: Sandro Petrizzelli2
La parte combinazionale fornisce le uscite m1 z,....,z vere e proprie del circuito sequenziale: tali
uscite sono funzioni sia degli ingressi L1 x,....,x veri e propri sia delle variabili n1 y,....,y di statopresente, in uscita dal circuito di memoria; quest’ultimo, d’altra parte, produce tali uscite in rispostaalle variabili n1 Y,....,Y di stato successivo generate dal blocco combinazionale.
Il complessivo circuito sequenziale presenta quindi, in totale, L+n ingressi e m+n uscite.Dire che il circuito sequenziale è sincrono significa dire che il suo funzionamento viene regolato
da un clock, il quale invia, in maniera periodica, un treno di impulsi: questo clock ha la funzioneper cui il circuito risente dell’applicazione di uno o più ingressisolo se tale applicazione avviene quando l’impulso di clock è alvalore alto (valore logico 1 del clock); ogni variazione dell’ingresso che avviene quando ilclock è a 0 non ha alcun effetto sul circuito. Quindi, in un circuito sequenziale sincrono, il cambiodello stato interno avviene in risposta, oltre che alle variazioni dell’ingresso vero e proprio, agliimpulsi di clock. In particolare, essendo il circuito di memoria formato da flip-flop, sappiamo che lecommutazioni avvengono solo o sui fronti di salita dei clock o sui fronti di discesa, in base alfunzionamento dei singoli flip-flop.
Un circuito sequenziale si dice invece asincrono quando il suo funzionamento è indipendentedagli impulsi di clock e, infatti, i circuiti asincroni non usano impulsi di clock: una transizione distato avviene, in questi circuiti, quando c’è un cambio delle variabili di ingresso.
In un circuito sequenziale asincrono, gli elementi di memoria sono costituiti da flip-flop, ossia daelementi sincronizzati con il clock (sono dei gated latch). Invece, in un circuito sequenzialeasincrono, gli elementi di memoria possono essere sia flip-flop svincolati dal clock (unclocked flip-flop) sia soprattutto puri elementi ritardatori (time-delay device). In questa sede, noi consideriamosolo elementi ritardatori, la cui capacità di memoria è dovuta semplicemente al tempo finito di cuiessi necessitano affinché il segnale si propaghi attraverso le porte digitali: infatti, un circuitosequenziale asincrono molto spesso non è altro che un circuitocombinazionale in cui è presente un percorso di retroazione.
I ritardatori puri non hanno, dunque, funzioni logiche, ma hanno solo la funzione di traslare neltempo, di un certo tempo (delay), il segnale ricevuto in ingresso.
Il progetto di un circuito sequenziale asincrono è più difficile di quello di un circuito sequenzialesincrono, a causa dei problemi di temporizzazione determinati dal percorso di retroazione. In unsistema sincrono opportunamente progettato, i problemi di temporizzazione sono eliminatisemplicemente triggerando tutti i flip-flop ai fronti di salita o di discesa del clock: in questo modo,abbiamo visto che il passaggio da uno stato al successivo avviene durante il breve tempo necessarioil clock passi dal livello basso a quello alto (positive edge-triggered) o viceversa (negative edge-triggered). Dato che, invece, un circuito asincrono non usa alcun clock, lo stato del sistema puòcambiare immediatamente non appena cambia l’ingresso.
I circuiti sequenziali asincroni sono utili in molte applicazioni. Essi sono usati quando èimportante la velocità di funzionamento, specialmente in quei casi in cui il sistema digitale deverispondere velocemente senza dover aspettare un impulso di clock. Sono più economici da usare neipiccoli sistemi indipendenti che richiedono solo pochi componenti hardware e per i quali non èconsigliabile affrontare le spese necessarie per realizzare un generatore di impulsi di clock. I circuitiasincroni sono anche utili in applicazioni dove i segnali di ingresso possono cambiare in qualsiasimomento, indipendentemente da un clock interno: la comunicazione tra due unità, ognuna avente unproprio clock indipendente, devono essere necessariamente realizzate tramite circuiti asincroni. Iprogettisti di sistemi digitali spesso realizzano sistemi misti, dove alcune parti del sistema sincronohanno le caratteristiche di un circuito asincrono.
Tornando adesso a quanto detto prima, abbiamo osservato che gli elementi di memoria, in uncircuito sequenziale sincrono, non sono più dei flip-flop sincronizzati con il clock, ma dei semplicielementi ritardatori. Lo schema generale di un circuito sequenziale asincrono diventa dunque ilseguente:
Macchine asincrone
Autore: Sandro Petrizzelli3
Abbiamo dunque ancora una volta un circuito combinatorio, cui siaggiunge una parte di memoria formata da elementi di ritardo. Talielementi di ritardo hanno il solo scopo di formare un anello di retroazione per il circuitocombinatorio, come vedremo meglio in seguito.
Le variabili di stato presente y1,y2,...,yn e le variabili di stato successivo Y1,Y2,...,Yn assumononuovi nomi nei circuiti sequenziali asincroni: si parla, rispettivamente, di variabili di statointerno (o anche variabili secondarie) e di variabili di eccitazione. Queste ultime non vannoperò confuse con le variabili di ingresso vere e proprie del circuito, che vengono perciò dette anchevariabili di stato esterno.
E’ evidente che, quando una variabile di ingresso commuta, le variabili secondarie non cambianoistantaneamente:
• in primo luogo, ci vuole un certo intervallo di tempo affinché il segnale si propaghi daiterminali di ingresso, attraverso il circuito combinatorio, alle variabili di eccitazione Y;
• queste variabili Y si propagano a loro volta nei rispettivi elementi ritardatori, in modo che,dopo un certo ritardo, le variabili secondarie y assumano proprio il valore delle corrispondentivariabili di eccitazione Y.
E’ importante notare che, quando il circuito è in condizioni di regime (steady-state condition), levariabili y ed Y sono le stesse; invece, durante le transizioni, esse sono diverse. Per unassegnato valore delle variabili di ingresso, il sistema si diceallora stabile se il circuito raggiunge una condizione di regime incui yi=Yi per i=1,2,...,n. Altrimenti, il circuito è in una continua transizione e si diceperciò che è instabile.
Quindi, al contrario dei circuiti sequenziali sincroni, in quelli sequenziali asincroni abbiamo statistabili e stati instabili.
E’ importante capire che una transizione da uno stato stabile ad un altro avviene solo in rispostaad un cambio di una variabile di ingresso. Questo è evidentemente in contrasto con quanto avvienenei sistemi sincroni, nei quali invece le transizioni di stato avvengono in risposta all’applicazione diun impulso di clock. Non solo, ma il passaggio da uno stato stabile ad unaltro non avviene, in generale, immediatamente, come nei circuitisincroni, ma attraverso una successione di stati instabili
Appunti di “Elettronica dei Sistemi Digitali” - Capitolo 5
Autore: Sandro Petrizzelli4
attraverso cui il circuito passa per giungere allo stato stabilefinale. In generale, quindi, partendo da un generico stato A stabile, a seguito di una variazionedi ingresso si passerà prima attraverso un certo numero di stati instabili, per poi giungere, dopo untempo più o meno lungo (dipendente da quanti stati intermedi vengono attraversati) allo stato stabilefinale B desiderato:
A Bstatiinstabili
stato Binstabile
Per garantire il funzionamento regolare della macchina, bisogna fare in modo che i circuitisequenziali raggiungano uno stato stabile prima che l’ingresso venga nuovamente cambiato. A causadei ritardi di propagazione insiti sia nei collegamenti sia nelle porte, non è possibile avere due o piùvariabili di ingresso che cambiano esattamente nello stesso istante di tempo: c’è sempre unaincertezza su quale variabile abbia commutato per prima. Di conseguenza, commutazionisimultanee di due o più ingressi sono generalmente proibite neicircuiti sequenziali asincroni.
Questa limitazione significa quindi che solo una variabile di ingresso per volta può commutare e iltempo tra una commutazione e l’altra deve essere maggiore del tempo di cui il circuito necessita perraggiungere uno stato stabile. In altre parole, una volta verificatasi unacommutazione di una variabile di ingresso, ogni eventualecommutazione successiva, della stessa variabile o di un’altra, nondeve avvenire prima che il circuito abbia raggiunto uno statostabile corrispondente al prima commutazione. Questo modo di operare è dettomodo fondamentale: le operazioni in modo fondamentale (fundamental-mode operations)presumono dunque che i segnali di ingresso cambino uno per volta e solo quando il circuito è in unacondizione stabile. In realtà, le operazioni in modo fondamentale hanno una ulteriore caratteristicache le distingue dalle operazioni cosiddette in modo impulsivo: dire che il circuito lavora in modoimpulsivo significa dire non solo che le variabili di ingresso commutano sempre una per volta, masignifica anche dire che le commutazioni corrispondono a variazioni solo temporanee del livellologico. Per capirci meglio, se xk è una generica variabile di ingresso, il circuito sequenzialeasincrono lavora in modo impulsivo se l’andamento temporale di xk è del tipo seguente:
xk
t
Ci sono cioè impulsi rettangolari, per cui il generico ingresso è quasi sempre a 0, tranne breviintervalli di tempo in cui si trova ad 1. Se il circuito è in grado di rispondere a queste sollecitazioniimpulsive, allora si dice che lavora in modo impulsivo. Al contrario, se il circuito risponde solo avariazioni durature1 del generico ingresso, si dice che il circuito lavora in modo fondamentale:
1 E’ ovvio che le variazioni del generico ingresso devono essere durature, ma in generale non saranno permanenti, nel senso che il
suddetto ingresso, una volta passato da 0 ad 1, in generale non rimarrà ad 1, ma avrà altre transizioni, in base a come vieneutilizzata la macchina: quindi, il funzionamento in modo impulsivo prevede che l’ingresso passi ad un nuovo livello logico e simantenga ad esso per un tempo sufficiente a che il circuito raggiunga un nuovo stato stabile, dopo di che lo stesso ingresso o unaltro possono nuovamente variare.
Macchine asincrone
Autore: Sandro Petrizzelli5
xk
t
Torniamo adesso al fatto che le variabili di ingresso possono variare una sola per volta. Percomprendere praticamente il significato di quanto detto prima, consideriamo un generico circuitosequenziale asincrono avente 4 ingressi e supponiamo che, in un certo istante, la configurazione diingresso sia 1011: l’applicazione di questo ingresso comporta che il circuito, dopo un certo tempo, siporti in un determinato stato stabile; una volta raggiunto questo stato stabile, è possibile applicareuna variazione di ingresso, ma non potrà essere una variazione qualsiasi: essa deve corrispondere aduna configurazione di ingresso a distanza 1 dalla precedente, ossia da 1011; è evidente che lepossibilità sono solo 4, a seconda di quale bit cambia:
cambia il primo ingresso→0011cambia il secondo ingresso→1111cambia il terzo ingresso→1001cambia il quarto ingresso→1010
Nessun’altra configurazione di ingresso è ammessa come successiva a 10112. Questo significaanche che le macchine asincrone sono macchine non completamentespecificate, proprio perché noi escludiamo alcune variazioni diingresso, rendendo possibili solo delle altre. Di conseguenza, quandodovremo passare alla minimizzazione di una macchina sequenziale asincrona, potremo servirci ditecniche del tutto analoghe a quelle viste per le FSM non completamente specificate: in particolare,ci riferiamo al fatto che ricercheremo anche in questo caso gli stati compatibili e non quelliequivalenti, che invece valgono solo per le FSM completamente specificate.
Circuiti asincroni in modo fondamentaleCircuiti asincroni in modo fondamentale
METODO DI SINTESI
I metodi di sintesi dei circuiti sequenziali asincroni funzionanti in modo fondamentale3 sono permolti versi simili a quelli per i circuiti sequenziali sincroni e, in particolare, per le considerazionifatte poco fa, ai circuiti sequenziali sincroni non completamente specificati.
Per esempio, anche in questo caso si fa riferimento ad una tabella degli stati, che però prendeadesso il nome di tabella di flusso primitiva. La differenza principale con la tabella degli statinei circuiti sincroni è nel fatto che la tabella di flusso primitiva comprende sia stati stabili sia stati
2 In pratica, le configurazioni applicate in ingresso devono susseguirsi secondo un codice Grey, cioè appunto differendo sempre di
un bit una dall’altra.
3 Nel seguito, salvo diverso avviso, ometteremo di specificare il funzionamento in modo fondamentale, dandolo per scontato
Appunti di “Elettronica dei Sistemi Digitali” - Capitolo 5
Autore: Sandro Petrizzelli6
instabili: gli stati stabili corrispondono ad ingressi stabili, mentre quelli instabili corrispondono adingressi che variano.
Nel seguito, per distinguere, nella tabella di flusso primitiva, gli stati instabili da quelli stabili,indicheremo questi ultimi in grassetto: ad esempio, i simboli A ed AA indicano, rispettivamente lostato A instabile e lo stato A stabile.
La tabella di flusso primitiva comprende anche i valori dell’uscita da associare a ciascuno stato ein corrispondenza di ciascuna configurazione di ingresso: tuttavia, come si vedrà, i valoridell’uscita possono essere specificati in un primo tempo solo pergli stati stabili, mentre successivamente, con opportuni criteri chevedremo, vanno specificate anche le uscite per gli stati instabili.
Una volta che la tabella di flusso primitiva sia stata minimizzata, si ripresenta il solito problemadell’assegnamento, ossia della codifica binaria dei vari stati. Nel caso delle macchine sincrone,abbiamo visto che l’assegnamento poteva essere fatto in modo casuale oppure, volendo semplificarela parte combinatoria del circuito finale, seguendo il metodo di Hartmanis. Nel caso, invece, dellemacchine asincrone, non si può assolutamente fare un assegnamento casuale, per un motivofondamentale: nei circuiti asincroni, a meno di non adottare degli assegnamenti opportunamentericavati (nel modo che vedremo), è possibile che il funzionamento finale differisca da quello teorico,a causa di transizioni di stato diverse da quelle desiderate. Come vedremo meglio in seguito, perevitare che ci siano transizioni di stato indesiderate, è spesso necessario complicare la struttura dellaparte combinatoria del circuito come è anche spesso necessario aumentare il numero di variabili distato necessario per la codifica binaria degli stati.
Esempio: latch asincrono di tipo J-K
Per comprendere a pieno i metodi di sintesi di una macchina sequenziale sincrona, facciamoriferimento ad un esempio concreto.
In precedenza, noi abbiamo già trattato una macchina asincrona, che era il latch, ad esempioquello di tipo S-R indicato nella figura seguente:
I1
I2Q
Q
Questo circuito, fin quando non è sincronizzato ad un segnale di clock4, è proprio un circuitoasincrono: infatti, sono evidenti i cammini di retroazione che riportano in ingresso i valoridell’uscita.
4 Un latch sincronizzato ad un segnale di clock è stato definito gated-latch e, in particolare, si tratta di un dispositivo level-
triggered, in grado cioè di commutare in un qualsiasi istante in cui il clock è ad 1; al contrario, un latch non sincronizzato ad unsegnale di clock è detto non-gated latch.
Macchine asincrone
Autore: Sandro Petrizzelli7
Anziché considerare un latch di tipo S-R, consideriamo un latch appena appena più complicato,come ad esempio un latch di tipo J-K:
Ricordiamo la tabella di verità (a sinistra) e quella di pilotaggio (a destra) di questo circuito:
RESET010111
SET101011
100101
SET101001
RESET010110
000010
100100
000000
QRSQKJ +
0X11
RESET1X01
SETX110
X000
KJQQ +
(nella tabella di verità ci interessano, in effetti, solo le prime 3 colonne e l’ultima, ma abbiamovoluto evidenziare anche i valori via via assunti dagli ingressi S ed R).
Il nostro obbiettivo è adesso quello di determinare il grafo orientato associato a tutte le possibilitransizioni di stato, dovute alla variazione di una variabile d’ingresso per volta.
Quanti stati dobbiamo considerare? In base alle considerazioni fatte in precedenza, non potremopiù individuare ogni stato semplicemente mediante il valore di Q, ma dovremo anche considerare ivalori degli ingressi che hanno portato Q ad avere il valore considerato.
Cominciamo da uno stato iniziale A in cui Q=0 e J=0 e K=0:
• se, partendo da A, applichiamo la configurazione di ingresso J=0 e K=0, Q rimane a 0, per cuila macchina rimane nello stato A;
• se invece, sempre partendo da A, applichiamo la configurazione di ingresso J=1 e K=0, alloral’uscita va ad 1, per cui passiamo in uno stato che indichiamo con D;
• se, infine, applichiamo J=0 e K=1, allora l’uscita rimane a 0, ma non siamo più nello stato A,in quanto gli ingressi sono adesso J=0 e K=1 e non più J=K=0.
Possiamo perciò cominciare la costruzione del grafo nel modo seguente:
Appunti di “Elettronica dei Sistemi Digitali” - Capitolo 5
Autore: Sandro Petrizzelli8
A
DC
01 10
0/00
Adesso, partendo dallo stato D, cui siamo giunti applicando J=1 e K=0 partendo da A, seapplichiamo nuovamente J=1 e K=0 rimaniamo nello stesso stato: infatti, l’uscita corrispondente a Dabbiamo detto essere Q=1, ma questa uscita rimane tale se applichiamo nuovamente J=1 e K=0.Possiamo perciò tracciare un arco che parte e si chiude nello stato D. Stesso discorso per lo stato C,corrispondente a Q=0 e al quale si giunge, partendo da A, applicando 01: l’uscita rimane ancora a 0.
Possiamo dunque perfezionare il grafo:
DC
01 10
0/00
1/100/01
Adesso, supponiamo di applicare, partendo da C, la configurazione J=0 e K=0: come si nota dallatabella di funzionamento, l’uscita rimane a 0, ma, essendo J=K=0, si torna nello stato A:
A
DC
01 10
0/00
1/100/01 00
Adesso, è evidente che da A non possiamo più operare transizioni di stato: infatti, avendo dettoche le variabili di ingresso possono variare solo una per volta, non è possibile che, dallaconfigurazione 00 corrispondente ad A, si passi alla configurazione 11. Discorso analogo vale per Ce D: partendo da C, che corrisponde a J=0 e K=1, non possiamo applicare J=1 e K=0, così come,partendo da D, che corrisponde a J=1 e K=0, non possiamo applicare J=0 e K=1.
Dobbiamo allora considerare le seguenti situazioni:
• partendo da C, applichiamo J=1 e K=1;• partendo da D, applichiamo J=1 e K=1.
Seguendo questi criteri, il grafo finale risulta essere il seguente:
Macchine asincrone
Autore: Sandro Petrizzelli9
A
DC
01 10
0/00
1/100/01 00
E
1110
1/11
F
0/11
01
01 1011
B
01
1/00
00
10
In questo grafo si notano una serie di cose interessanti:
• in primo luogo, si nota la presenza di autoanelli; tali autoanelli non sono da intendersi con lostesso significato che si aveva nelle macchine sincrone: in quel caso, infatti, un autoanelloindicava che, per la specificata sequenza di ingresso, la macchina compiva effettivamente ilciclo indicato; in questo caso, invece, un autoanello rappresenta, per convenzione, lapermanenza della macchina in uno stato stabile;
• in secondo luogo, si osserva che i valori delle uscite sono stati indicati solo in corrispondenzadegli stati stabili e non per i vari archi orientati; questo lascerebbe pensare che la macchina èuna macchina di Moore, ma in realtà non è così, in quanto le uscite, come vedremo, dipendonoeffettivamente anche dagli ingressi oltre che dagli stati; abbiamo però detto, in precedenza, chein questa fase iniziale di progetto della macchina, si possono specificare solo le uscite relativeagli stati stabili, mentre invece quelle relative agli stati instabili andranno specificate inseguito.
A questo punto, sulla base del diagramma tracciato prima, costruiamo la tabella di flussoprimitiva, la cui struttura è identica a quella vista per le macchine sincrone:
F
E
D
C
B
A
1011010010110100JK\.p.s
Appunti di “Elettronica dei Sistemi Digitali” - Capitolo 5
Autore: Sandro Petrizzelli10
Per prima cosa, riempiamo la tabella indicando gli stati stabili i corrispondenti valori delle uscite:
00FF11EE
11DD00CC
11BB00AA
F
E
D
C
B
A
1011010010110100JK\.p.s
Come si vede, lo stato A è stabile (indicato con AA) in corrispondenza dell’applicazionedell’ingresso 00 e, in corrispondenza dello stesso ingresso, risulta anche stabile lo stato B (indicatocon BB), che però si distingue da A per una diversa uscita (1 al posto di 0).
Adesso, possiamo ulteriormente riempire la tabella indicando gli stati instabili. Che cosa significaquesto? Consideriamo, come stato di partenza, lo stato A: se applichiamo l’ingresso 01, lo stato A siporta nello stato C, il quale, per le considerazioni fatte in precedenza, non si stabilizzaimmediatamente, ma solo dopo un certo tempo. Di conseguenza, la casella corrispondente allo statoA ed all’ingresso 01 va riempita con lo stato C instabile:
00FF11EE
11DD00CC
11BB00AA
F
E
D
C
B
CA
1011010010110100JK\.p.s
−
La lettura della tabella, in base alla casella appena riempita, è la seguente: dato lo stato A stabiledi partenza, variando l’ingresso da 00 a 01, si giunge in C instabile, il quale, dopo un certo tempo, sistabilizza.
In modo analogo vanno riempite le rimanenti caselle, con l’accortezza di riempire con un “-”(trattino orizzontale) le caselle corrispondenti a configurazioni di ingresso non ammesse (come adesempio la configurazione 11 partendo da AA oppure la configurazione 00 partendo da EE oppure da
FF):
−−−−−−−−
−−−−−−−−−−−−−−−−
00FF11EE
11DD00CC
11BB00AA
DCF
DCE
FBD
EAC
DCB
DCA
1011010010110100JK\.p.s
Macchine asincrone
Autore: Sandro Petrizzelli11
Nota la tabella di flusso primitiva, possiamo passare alla sintetizzazione circuitale della macchina,per giungere alla quale dobbiamo però minimizzare la macchina stessa. A tal fine, ci serviamoancora una volta della tabella triangolare, mediante la quale individuare eventuali coppie di staticompatibili (ricordiamo che parliamo di stati compatibili in quanto queste macchine non sonocompletamente specificate, per cui non ha senso parlare di stati equivalenti):
EDCBA
F
\\E
\\\\D
\\\\\\C
\\\\\\\\B
Possiamo immediatamente riempire con delle X le caselle corrispondenti a coppie di stati conuscite diverse; in particolare, ci riferiamo ad uscite diverse in corrispondenza delle stesseconfigurazioni di ingresso, in quanto non possiamo confrontare due stati come, ad esempio B e C,per i quali i valori specificati per l’uscita corrispondono a configurazioni di ingresso diverse. Nelnostro caso, risultano quindi sicuramente distinguibili gli stati A e B e gli stati E ed F, che hannovalori di uscita diversi in corrispondenza delle stesse configurazioni di ingresso:
EDCBA
XF
\\E
\\\\D
\\\\\\C
\\\\\\\\XB
Il riempimento delle successive caselle avviene con le regole classiche:
EDCBA
XVXVVF
\\XVVVE
\\\\XVXD
\\\\\\XVC
\\\\\\\\XB
EDCBA
XVF,EVVF
\\F,EVVVE
\\\\B,AVB,AD
\\\\\\B,AVC
\\\\\\\\XB
→
Le coppie di stati da considerare sono dunque le seguenti:
colonna A → (A,F),(A,E),(A,C)colonna B → (B,F),(B,E),(B,D)colonna C → (C,E)colonna D → (D,F)colonna E → niente
Appunti di “Elettronica dei Sistemi Digitali” - Capitolo 5
Autore: Sandro Petrizzelli12
Con queste coppie dobbiamo formare i massimi compatibili:
(A,E),(A,C),(C,E) → (A,C,E)(B,F),(B,D),(D,F) → (B,D,F)(B,E)(A,F)
Adesso, dobbiamo scegliere il numero minimo di massimi compatibili che soddisfano a dueproprietà:
• in primo luogo, devono garantire la copertura di tutti gli stati della macchina di partenza;
• in secondo luogo, devono verificare la proprietà di chiusura, in base alla quale, data unaqualsiasi coppia di stati appartenente ad uno qualsiasi dei massimi compatibili selezionati,anche la corrispondente coppia di stati 1-successori appartiene ad uno dei massimi compatibili.
Si verifica facilmente che questi due requisiti sono rispettati dai massimi compatibili (A,C,E) e(B,D,F), per cui consideriamo questi come nuovi e unici stati della macchina indicandolirispettivamente con M e N.
Con queste posizioni, la tabella di flusso primitiva si riduce alla seguente:
101MN
100NM
1011010010110100JK\.p.s
−−
NNNNNNMMMMMM
Come si nota, abbiamo indicato i valori dell’uscita solo in corrispondenza degli stati stabili. Inrealtà, a questo punto dobbiamo fissare i valori dell’uscita anche per gli stati instabili, seguendo uncriterio ben preciso: dobbiamo fare in modo che, nelle transizioni da uno stato stabile ad un altro,non ci siano spike, ossia variazioni intermedie dell’uscita.
Vediamo allora cosa accade nel nostro caso. Consideriamo l’uscita corrispondente allo stato N edall’ingresso 01: partendo dallo stato N stabile per 11, se variamo l’ingresso da 11 a 01, la macchinapassa prima ad M instabile e poi ad M stabile; sia nello stato di partenza sia nello stato di arrivo,l’uscita vale 0, per cui dovrà valere 0 anche durante la transizione:
1001MN
100NM
1011010010110100JK\.p.s
←↑
←↑
−
NNNNNN
MMMMMM
In modo analogo, partendo dallo stato M stabile per 11 e portando l’ingresso ad 10, la macchinapassa prima per N instabile e poi per N stabile; dato che l’uscita vale 1 sia per lo stato iniziale sia perquello finale, dovrà valere 1 anche durante la transizione:
1001MN
110N
101100100100\..s
MMM↓
→↓
→
Macchine asincrone
Autore: Sandro Petrizzelli13
Il grafo orientato associato alla macchina (minima) così ottenuta è dunque il seguente:
F
B
1001
111
001
00
011
110
00
A questo punto, abbiamo praticamente finito con la parte difficile, in quanto l’assegnamento èimmediato: avendo due soli stati, ci basterà 1 sola variabile y (cui quindi corrisponderà 1 solavariabile Y). Ponendo ad esempio M=0 ed N=1, la tabella diventa la seguente
100111011N
110010000M
1011010010110100JK\.p.s
==
Usando le mappe di Karnaugh, possiamo sintetizzare le due funzioni Y (stato) e Z (uscita):
'yKyJ'JKY
1
0
10110100JK\y
++=→111
1
'yK'JyZ
1
0
10110100JK\y
+=→11
11
Come era logico aspettarsi, l’espressione ottenuta per Z è la stessa ricavata a suo tempo per unlatch di tipo J-K, con questa volta y al posto di Q.
Lo schema logico della macchina è dunque il seguente:
Appunti di “Elettronica dei Sistemi Digitali” - Capitolo 5
Autore: Sandro Petrizzelli14
In questo schema, abbiamo inserito il ritardo puro ( ) che rappresenta la parte di memoria delcircuito sequenziale. In effetti, molto spesso questo componente è assente, in quanto si sfrutta
a blocchi di un circuito sequenziale asincrono reale, possiamo considerare il seguente:
Ingressi Uscite
∆y yY
In base a questo schema, le variabili Y generate dal circuito combinazionale subiscono un ritardoall’interno dello stesso circuito combinazionale, all’uscita del quale, quindi preleviamo direttamentele corrispondenti y da riportare in ingresso.
ESEMPIO: MISURATORE DI RIFLESSI
Consideriamo una macchina per provare i riflessi. Il suo funzionamento è il seguente: quando lamacchina è in condizioni di attesa, dobbiamo inserire una moneta al suo interno; dopo aver inseritola moneta, quest’ultima impiega un certo tempo T ad arrivare nel contenitore delle monete: la provadei riflessi consiste nel riuscire a premere e rilasciare un pulsante P prima del tempo T, ossia primache la moneta vada ad aggiungersi a tutte le altre.
Volendo sintetizzare questa macchina, possiamo intanto schematizzarla come un macchina avente2 ingressi e due uscite:
Macchine asincrone
Autore: Sandro Petrizzelli15
R
P
z1
z2
L’ingresso R possiamo vederlo come un ingresso di riferimento corrispondente all’introduzionedella moneta: infatti, dato che abbiamo la possibilità di spingere il pulsante P solo tra l’istante in cuiinseriamo la moneta e l’istante in questa raggiunge il proprio contenitore, possiamo vedere R comeun segnale che mantiene il livello logico 1 solo per il tempo T a nostra disposizione:
R
t
Abbiamo dunque la possibilità di spingere il pulsante P solo mentre R è ad 1, il che avvienedall’istante t=0 (preso come riferimento) all’istante t=T.
Per quanto riguarda l’ingresso P, esso corrisponde appunto alla pressione del pulsante: se ilpulsante è premuto, P sarà al livello logico 1, mentre altrimenti sarà al livello logico 0. Il test per iriflessi avrà dunque successo che P avrà un andamento del tipo seguente:
P
tT
Non avrà invece successo per una situazione del tipo seguente:
P
tT
In questo caso, infatti, abbiamo rilasciato il pulsante P dopo che l’ingresso di riferimento ècessato, ossia oltre il tempo limite T a nostra disposizione.
I valori delle uscite ci dicono se il test ha avuto esito positivo o esisto negativo. Per esempio,possiamo supporre che tali uscite corrispondano all’accensione o allo spegnimento di 2 lampadine,una rossa (z1) ed una verde(z2):
• inizialmente, quando la macchina è in condizioni di attesa, supponiamo che solo la lampadinarossa sia accesa: questa è dunque la situazione in cui ci troviamo ogni volta che la macchina
Appunti di “Elettronica dei Sistemi Digitali” - Capitolo 5
Autore: Sandro Petrizzelli16
subisce un RESET (azionabile mediante un apposito tasto che non ci interessa nella nostraschematizzazione), per cui è pronta ad eseguire un nuovo test;
• se il test riesce, allora la luce verde si deve accendere e quella rossa si deve spegnere;
• se invece il test non riesce, allora supponiamo che entrambe le luci si debbano spegnere.
• infine, per indicare che il test è stato completato, supponiamo che entrambe le luci si debbanoaccendere.
inatotest termaccesaaccesa
riuscitonon test spentaspenta
riuscitotest accesaspenta
by standspentaaccesa
zz 21
Possiamo arbitrariamente codificare in binario queste 4 possibili situazioni:
inatotest term11
riuscitonon test 01
riuscitotest 10
by stand00
zz 21
A questo punto, dobbiamo tracciare il diagramma degli stati di questa macchina, che èevidentemente una macchina asincrona, visto che gli ingressi R e P commutano in istanti qualsiasi (Rva ad 1, per un tempo T, tutte le volte che qualcuno effettua il test, mentre P va ad 1 solo quandoviene premuto il pulsante) e non sono vincolati ad alcun clock. Non solo, ma è praticamenteimpossibile che questi ingressi commutino insieme: così come ci vuole un certo tempo per premere ilpulsante P dopo aver inserito la moneta (per cui P andrà ad 1 solo dopo che R è andato ad 1), allostesso modo è difficile (anche se non impossibile) che il pulsante P venga rilasciato esattamentenello stesso istante in cui la moneta arriva nel proprio raccoglitore (cioè difficilmente l’ingresso Ptornerà a 0 nello stesso istante in cui anche R torna a 0).
E’ evidente che dobbiamo partire da uno stato di partenza corrispondente alla macchina incondizioni di stand by: le due lampadine sono entrambe spente (uscita 00) e gli ingressi sonoentrambi a 0 (ingressi 00, dove il primo bit indica R ed il secondo indica P). Indichiamo questo statocon A.
Supponiamo adesso di cominciare il test, inserendo la moneta in un certo istante: stiamo dunqueapplicando l’ingresso R=1 e P=0, il che ci porta in uno stato successivo, che indichiamo con B, nelquale le uscite sono sempre 0 (in quanto il test è appena cominciato). Una volta giunti in B, finquando non premiamo il pulsante P, cioè fin quando P=0, rimaniamo nello stesso stato. Se, invece,premiamo P, per cui applichiamo l’ingresso R=1 e P=1, ci portiamo in un nuovo stato C: a partire daquesto stato, finche non rilasciamo P, lasciando cioè l’ingresso R=1 e P=1, la macchina rimane nellostesso stato (caratterizzato ancora da uscite entrambe =0). Se, invece, partendo da C, rilasciamo ilpulsante P, per cui R=1 e P=0, allora giungiamo in uno stato D che corrisponde alla riuscita del test(in quanto abbiamo rilasciato il pulsante P prima che la moneta sia giunta a destinazione, ossia primache R=0), per cui le uscite sono z1=0 e z2=1 (corrispondenti a luce rossa spenta e luce verde accesa)
Partendo dallo stato D, corrispondente dunque a test riuscito, arriva l’istante in cui la monetagiunge nel contenitore, per cui R torna ad 0, con P che è già andato a 0. Giungiamo così in un nuovostato, E, corrispondente a “test terminato”, nel quale le uscite valgono entrambe 1.
Macchine asincrone
Autore: Sandro Petrizzelli17
La situazione appena descritta corrisponde ai seguenti andamenti di R e P:
R
tP
tT
A B C D E
Nella figura è anche indicata la successione temporale degli stati.In questo stato E rimaniamo fin quando non viene premuto il tasto di RESET della macchina, in
modo da portarci nuovamente nello stato A di partenza. Ciò significa che lo stato E è uno statoterminale, adottando una espressione già citata in precedenza: da questo stato si può uscire solotramite una operazione di RESET che è esterna, per così dire, al funzionamento che noi stiamoconsiderando per la macchina.
In base a queste considerazioni, possiamo cominciare a costruire il grafo della macchina,inserendo gli stati A,B,C,D ed E appena descritti:
A
00/00
B
10
10/00
C11/00
11
D10
10/01
E00
00/11
Questo grafo va adesso completato contemplando tutte le altre possibilità.Una prima possibilità è quella in cui premiamo il pulsante P prima di aver inserito la moneta (per
cui R=0 e P=1): giungiamo in uno stato F caratterizzato da uscite entrambe a 0, visto che R non ènemmeno andato ad 1. Da questo stato F abbiamo due possibilità:
• se rilasciamo il pulsante P prima ancora di inserire la moneta (ingresso 00), abbiamo ancora lapossibilità di fare il test, per cui torniamo in A;
• se invece manteniamo premuto il pulsante P dopo aver inserito la moneta (ingresso 11), alloraci portiamo in un nuovo stato, G, caratterizzato ancora da lampade entrambe spente.
Appunti di “Elettronica dei Sistemi Digitali” - Capitolo 5
Autore: Sandro Petrizzelli18
Se, in G, rilasciamo il pulsante P (ingresso 10), il test è chiaramente fallito, per cui andiamo inuno stato H (con uscite 00), dal quale torniamo nello stato finale E non appena anche R va a 0(ingresso 00).
La situazione appena descritta è la seguente:
R
tP
tT
A F G H E
Andiamo allora ad aggiungere questi nuovi stati F,G ed H al grafo:
A
00/00
B
10
10/00
C11/00
11
D10
10/01
E00
00/11
F
01/00
01 G
11/00
11 H
10/00
10
00
00
A questo punto, osserviamo che per alcuni stati abbiamo già considerato tutte le possibilità,mentre per altri no: infatti, da A e da F partono 3 archi orientati, corrispondenti alle 3 possibilicombinazioni di ingresso5, mentre dagli altri stati partono solo 2 archi. Andiamo allora a considerarele possibilità rimanenti. 5 Il motivo per cui sono solo 3 le possibili configurazioni di ingresso a partire da ciascuno stato è evidente: sappiamo infatti che, in
una macchina asincrona, si può avere solo 1 variazione per volta degli ingressi, per cui, se siamo giunti in uno stato con una dataconfigurazione di ingresso a 2 bit (R e P nel caso considerato), la successiva configurazione potrà essere scelta solo tra altre 3.Ad esempio, giungendo in F con ingresso 01, la successiva combinazione di ingresso potrà essere solo 01 (cioè l’ingresso rimaneinvariato), 00 o 11, mentre non potrà essere mai essere 10, in quanto quest’ultima presuppone la variazione sia di R sia di P, ilche non è ammesso nelle macchine sincrone.
Macchine asincrone
Autore: Sandro Petrizzelli19
Cominciamo dallo stato B, che è stabile per l’ingresso 10: abbiamo già considerato cosa avvienequando si applica l’ingresso 11, per cui resta da vedere cosa accade quando si applica 00. Ingresso00, partendo da B, significa che il segnale di riferimento R è andato a 0 prima che il pulsante P siastato premuto, per cui non possiamo far altro che giungere nello stato terminale E, da cui poieventualmente riprendere la prova dopo un RESET della macchina.
R
tP
tT
A B E
E’ evidente che, una volta tornato a 0 il segnale di riferimento R, qualunque cosa noi facciamo colpulsante P, la macchina rimane nello stesso stato E (con entrambe le lampadine accese), in quanto iltempo a disposizione per il test (corrispondente al tempo T durante il quale R=1) è finito, per cui nonsi può far altro che resettare e ripartire.
Passiamo adesso allo stato C, stabile per 11, per il quale rimane da considerare la transizionedovuta ad ingresso 01: C è uno stato corrispondente a pulsante P premuto mentre R è ad 1; applicare01 significa che R torna a 0 mentre stiamo ancora premendo il pulsante, per cui dobbiamo andare inuno stato duale di D (che corrispondeva all’aver rilasciato P prima che R tornasse a 0). Indicandoquesto nuovo stato con I, è evidente che da I (stabile per 01) applicando l’ingresso 00 (checorrisponde adesso a rilasciare P dopo che R è già tornato a 0), andiamo ancora in E, dal qualepotremo poi ripartire, col solito RESET, per un nuovo test.
R
tP
tT
A B C EI
Andiamo dunque a perfezionare il grafo in base alle considerazioni appena fatte:
Appunti di “Elettronica dei Sistemi Digitali” - Capitolo 5
Autore: Sandro Petrizzelli20
A
00/00
B
10
10/00
C11/00
11
D10
10/01
E00
00/11
F
01/00
01 G
11/00
11 H
10/00
10
00
00
00
I01/00
00
11
01
E’ interessante osservare, come si nota nella figura, che dallo stato I c’è una transizione che non èpossibile6: infatti, partendo da I, non è possibile che venga applicato l’ingresso 11, in quanto, mentrepossiamo premere o rilasciare P come ci pare, il segnale R, una volta che è tornato a 0, non può mairitornare ad 1, a meno di non resettare la macchina.
Quindi, abbiamo introdotto il nuovo stato I, ma per esso abbiamo già considerato tutte le possibilitransizioni.
Proseguendo secondo questi criteri, il completamento del grafo porta ad altri 3 nuovi stati (L,M edN). Anziché riportare il grafo per intero, consideriamo la corrispondente tabella di flusso primitiva,che contiene dunque ben 12 stati:
1111NN0101MM
0101LL0000II
0000HH0000GG
0000FF1111EE
0101DD0000CC
0000BB0000AA
N
M
L
I
H
G
F
E
D
C
B
A
1011010010110100RP\.p.s
6 E’ importante distinguere le transizioni “non permesse” da quelle “non possibili”: le prime non si verificano perché non sono
possibili variazioni contemporanee dei due ingressi; le altre non si verificano in base al particolare funzionamento dellamacchina.
Macchine asincrone
Autore: Sandro Petrizzelli21
Evidentemente, abbiamo cominciato a riempire la tabella solo con gli stati stabili e lecorrispondenti uscite. Il passo successivo è quello di riempire la tabella con gli stati instabili, con letransizioni non permesse (indicate con \\) e con quelle non possibili (indicate con X, visto checorrispondono a condizioni don’t care):
1111NN0101MM
0101LL0000II
0000HH0000GG
0000FF1111EE
0101DD0000CC
0000BB0000AA
\\XEN
\\XEM
DM\\L
\\XEI
G\\EH
HI\\G
\\GAF
X\\NE
L\\ED
DI\\C
C\\EB
B\\FA
1011010010110100RP\.p.s
Potremmo anche inserire le uscite degli stati instabili, imponendo l’assenza di spike, ma non ènecessario in questo momento, in quanto non sappiamo ancora se la macchina appena ricavata è unamacchina minima.
Andiamo allora a verificare questo, usando ancora una volta la tabella triangolare, nella qualeinserire eventuali compatibilità, distinguibilità o indistinguibilità tra i vari stati.
Le prime caselle da riempire, nella tabella triangolare, sono quelle relative a coppie di stati chehanno uscite stabili, in corrispondenza delle stesse configurazioni di ingresso, diverse tra loro:
MLIHGFEDCBA
XXXN
\\XXM
\\\\XXL
\\\\\\I
\\\\\\\\XH
\\\\\\\\\\G
\\\\\\\\\\\\F
\\\\\\\\\\\\\\XE
\\\\\\\\\\\\\\\\XD
\\\\\\\\\\\\\\\\\\C
\\\\\\\\\\\\\\\\\\\\B
A questo punto, dobbiamo riempire le rimanenti caselle mediante le corrispondenti compatibilità,distinguibilità o indistinguibilità (indicate con V):
Appunti di “Elettronica dei Sistemi Digitali” - Capitolo 5
Autore: Sandro Petrizzelli22
MLIHGFEDCBA
XN,MXVN,IXVVN,IVN,F
E,AN
\\VXVM,IXM,NVM,IVM,F
E,AM
\\\\M,IH,D
L,GX
L,G
M,FN,MVX
D,B
L,C
D,B
M,FL
\\\\\\VVE,AN,IVVVI,F
E,AI
\\\\\\\\VE,AVXH,D
G,CG,C
H,B
H,AH
\\\\\\\\\\I,FI,NH,D
L,GH,D
H,B
G,C
H,B
I,FG
\\\\\\\\\\\\N,F
E,A
L,G
E,A
G,C
I,F
G,C
E,AVF
\\\\\\\\\\\\\\VN,IVXE
\\\\\\\\\\\\\\\\L,CXD,B
E,AD
\\\\\\\\\\\\\\\\\\D,BD,B
I,FC
\\\\\\\\\\\\\\\\\\\\E,AB
Ora dobbiamo controllare se le distinguibilità (indicate con X) individuate ne implicano dellealtre: seguendo questo criterio in modo iterativo (nel senso che ogni nuova distinguibilità puòcomportarne delle altre), si arriva al seguente risultato:
MLIHGFEDCBA
XXXVXXVVXVXN
\\VXVXXXVXVXM
\\\\XXXXXVXXXL
\\\\\\VVXXVVVXI
\\\\\\\\VXVXXXXH
\\\\\\\\\\XXXXXXG
\\\\\\\\\\\\XXXXVF
\\\\\\\\\\\\\\VXVXE
\\\\\\\\\\\\\\\\XXXD
\\\\\\\\\\\\\\\\\\XXC
\\\\\\\\\\\\\\\\\\\\XB
Possiamo ricavare, in base a questa tabella, le coppie di stati compatibili:
colonna A → (A,F)colonna B → (B,N),(B,M),(B,I),(B,E)colonna C → (C,I)colonna D → (D,N),(D,M),(D,L),(D,I),(D,E)colonna E → (E,N),(E,H)
Macchine asincrone
Autore: Sandro Petrizzelli23
colonna F → nientecolonna G → (G,I), (G,H)colonna H → (H,N),(H,M),(H,I)colonna I → nientecolonna L →(L,M)colonna M → niente
Con queste coppie dobbiamo formare i massimi compatibili:
(A,F)(B,N),(B,E),(E,N)→ (B,E,N)(B,M)(B,I)(C,I)(D,N),(E,N),(D,E)→(D,E,N)(D,M),(D,M),(D,L)→(D,L,M)(D,I)(E,H),(H,N),(E,H)→(E,H,N)(G,I),(G,H),(H,I)→(G,H,I)(H,M)
Abbiamo dunque 11 massimo compatibili. Per scegliere quelli che andranno a costituire lamacchina minima, dobbiamo considerare il minimo numero di massimi compatibili che coprono tuttigli stati della macchina di partenza e che soddisfano la proprietà di chiusura. Partiamo allora dallacondizione secondo cui i massimi compatibili devono garantire la copertura di tutti gli stati:
• lo stato A è contenuto solo nel massimo compatibile (A,F), che quindi andrà presonecessariamente;
• lo stato C compare solo in (C,I), che quindi andrà preso;• stesso discorso per gli stati G ed L, contenuti rispettivamente solo in (G,H,I) e (D,L,M), che
quindi vanno presi necessariamente.
Detto questo, rimangono solo gli stati B,E ed N che sono peraltro contenuti nel massimocompatibile (B,E,N). Prendiamo allora anche quest’ultimo.
Abbiamo dunque selezionato i seguenti massimi compatibili:
(A,F) - (C,I) - (G,H,I) - (D,L,M) - (B,E,N)
Dobbiamo verificare che questi soddisfino alla proprietà di chiusura ed è facile verificare che larisposta è affermativa. Deduciamo, quindi, che questi massimi compatibili rappresentano gli statidella macchina minima. Facciamo allora le seguenti posizioni:
1=(A,F) - 2=(C,I) - 3=(G,H,I) - 4=(D,L,M) - 5=(B,E,N)
. La tabella di flusso primitiva di questa macchina minima risulta essere la seguente:
Appunti di “Elettronica dei Sistemi Digitali” - Capitolo 5
Autore: Sandro Petrizzelli24
000000000000555555010101010101444444
000000003333000011111111222222
000000001111
25
24
423
32
251
1011010010110100RP\.p.s
Ancora una volta, ci siamo limitati ad inserire solo le uscite relative agli stati stabili. Per fissare leuscite relative agli stati stabili, dobbiamo imporre che non ci siamo spike:
• cominciamo a considerare il passaggio dallo stato 1 stabile per 01 allo stato 3 stabile per 11: lerispettive uscite sono entrambe 00, per cui anche nello stato 5 instabile per 11 dovremo imporreche l’uscita sia 00:
000000000000555555010101010101444444
000000003333000011111111222222
000000001111
25
24
423
32
00251
1011010010110100RP\.p.s
↓→
• stesso discorso per le seguenti altre transizioni: passaggio da 1 stabile per 00 a 2 stabile per 10e passaggio da 2 stabile per 01 a 3 stabile per 11:
000000000000555555010101010101444444
000000003333000011111111222222
000000001111
25
24
423
0032
0000251
1011010010110100RP\.p.s
• passiamo adesso a quello che accade nella prima colonna delle uscite e, in particolare, alpassaggio dallo stato 2 stabile per 00 allo stato 4 stabile per 01 (passaggio che avvieneattraverso lo stato 2 instabile per 00): le rispettive uscite sono 11 e 01, per cui dobbiamoimporre che anche lo stato 2 instabile per 00 abbia la seconda uscita ad 1:
000000000000555555010101010101444444
000000003333000011111111222222
000000001111
25
1_24
423
0032
0000251
1011010010110100RP\.p.s
Macchine asincrone
Autore: Sandro Petrizzelli25
• analogo discorso per il passaggio dallo stato 3 stabile per 11 allo stato 4 stabile per 10(passaggio che avviene attraverso lo stato 4 instabile per 10): le rispettive uscite sono 00 e 01,per cui dobbiamo imporre che anche lo stato 4 instabile per 10 abbia la prima uscita a 0:
000000000000555555010101010101444444
000000003333000011111111222222
000000001111
25
1_24
_0423
0032
0000251
1011010010110100RP\.p.s
A questo punto, abbiamo rispettato tutti i vincoli per evitare spike, ma ci sono rimaste, però,ancora vuote delle caselle relative alle uscite: queste caselle sono vuote in quanto corrispondono auscite che cambiano dallo stato stabile di partenza allo stato stabile di arrivo. Allora, un modo diriempirle è quello di imporre che la transizione dell’uscita, dal valore iniziale a quello finale,avvenga subito, cioè nel passaggio dallo stato stabile di partenza allo stato instabile intermedio. Adesempio, consideriamo il passaggio dallo stato 3 stabile per 11 allo stato 4 stabile per 10 (passaggioche avviene attraverso lo stato 4 instabile per 10): abbiamo visto poco fa che le rispettive uscite sono00 e 01, per cui abbiamo imposto che anche lo stato 4 instabile per 10 abbia la prima uscita a 0;possiamo adesso imporre che lo stesso stato 4 instabile per 10 abbia la seconda uscita a 1, in mododa anticipare la transizione di uscita che si avrebbe nel passaggio allo stato finale 4 stabile per 10:
000000000000555555010101010101444444
000000003333000011111111222222
000000001111
25
1_24
01423
0032
0000251
1011010010110100RP\.p.s
Procedendo con lo stesso criterio per le altre 5 caselle rimaste vuote, abbiamo quanto segue:
000000000000555555010101010101444444
000000003333000011111111222222
000000001111
0025
1124
0100423
0032
0000251
1011010010110100RP\.p.s
Siamo dunque arrivati alla tabella di flusso primitiva. Il passo successivo è quellodell’assegnamento, ossia la codificazione binaria dei vari stati, in modo da poter poi passare allasintetizzazione della parte combinatoria del circuito mediante le opportune mappe di Karnaugh.Come facciamo l’assegnamento? In base alle considerazioni fatte nel paragrafo precedente, nonpossiamo fare un assegnamento casuale, in quanto questo porterebbe il rischio di malfunzionamentinella macchina. I prossimi paragrafi sono allora dedicati appunto ai criteri di sceltadell’assegnamento, dopo di che torneremo a questa macchina per vedere una applicazione pratica diquesti criteri.
Appunti di “Elettronica dei Sistemi Digitali” - Capitolo 5
Autore: Sandro Petrizzelli26
PROBLEMA DELL’ASSEGNAMENTO NELLE MACCHINE SEQUENZIALI
ASINCRONE
Data la tabella di flusso primitiva della macchina (minima) sequenziale asincrona in esame, non èpossibile fare un assegnamento casuale, in quanto si possono verificare 2 situazioni moltoparticolari.
Cominciamo dalla prima situazione. Supponiamo che la nostra macchina contenga un certonumero di stati, tra i quali individuiamo i generici stati A,I e J. Supponiamo anche che la tabella diflusso primitiva, relativa a tali stati, sia la seguente:
JJ
II
AA
J
I
IA
110100xx\.p.s 21
Abbiamo cioè supposto che, per una stessa configurazione di ingresso (in questo caso 01), ci sianodue stati stabili (in questo caso J e K). Supponiamo di aver adottato, per questa macchina, unassegnamento casuale, che ha portato ai seguenti codici: A=000, I=101, J=001. La tabella di flussoprimitiva si modifica allora nel modo seguente:
001001
101101
000000
001J
101I
101000A
110100xx\yyy 21321
=
=
=
Consideriamo allora il passaggio dallo stato A stabile per 00 allo stato I stabile per 01: nel variarel’ingresso da 00 a 01, dovrebbero variare contemporaneamente due variabili di stato interno (y1 deveandare da 0 a 1 e lo stesso deve fare y3) affinché si passi da A stabile per 00 ad I instabile per 01 equindi poi a I stabile per 01. Il problema è che le variabili di stato internonon potranno mai variare contemporaneamente, dato che i ritardi dipropagazione dei segnali sono in generale diversi; allora, nel casoconsiderato, se y3 variasse per prima, si otterrebbe il passaggio da A stabile per 00 a J instabile equindi a J stabile per 01: essendo quest’ultimo uno stato stabile, non sarebbe più possibile giungerein I, che era lo stato voluto. Questo è un tipico caso di malfunzionamento di una macchina asincrona.
E’ abbastanza intuitivo capire come si possa fare per rimediare a questi malfunzionamenti:basta fare in modo che ogni transizione di stato avvenga tra unostato stabile di partenza ed uno stato stabile di arrivocaratterizzati da codici binari a distanza 1. In questo modo, infatti, saràsempre 1 sola variabile di stato interno a dover cambiare. Se non fosse così, se cioè dovesserocambiare più variabili di stato interno, ad esempio 2 come nel caso appena considerato. si creerebbela cosiddetta corsa tra variabili di stato interno: a seconda di quale cambia prima, la macchina puòcomportarsi o meno nel modo desiderato.
Macchine asincrone
Autore: Sandro Petrizzelli27
Vediamo un altro esempio. Consideriamo una macchina sequenziale asincrona (minima) avente laseguente tabella di flusso primitiva (riferita ai soli stati, che in questo contesto sono gli unici adinteressarci):
CCD
DAC
DACB
BDCA
10110100xx\.p.s 21
DDDDCCCCBB
AA
Supponiamo di effettuare un assegnamento generico per questa macchina, come ad esempio ilseguente: A=00, B=01, B=11, D=10. La tabella di flusso primitiva diventa la seguente:
111110
100011
10001101
01101100
10110100xx\yy 2121
10101010111111110101
0000
Supponiamo di trovarsi nello stato C stabile per 00: passando dall’ingresso 00 all’ingresso 01,andiamo (teoricamente) prima nello stato A instabile per 01 e quindi nello stato A stabile per 01. Ilproblema è che, in questa transizione, dovrebbero variare entrambe le variabili di stato interno (sia y1
sia y2 dovrebbero passare da 1 a 0). Dato che le due variabili non potranno mai commutare insieme,il passaggio da 11 a 00 dovrà avvenire necessariamente in 2 passi: 11→01→00 oppure 11→10→00.
Consideriamo il primo percorso, ossia 11→01→00: da 11 stabile per 00 andiamo in 01 instabile,quindi in 00 instabile per 01 e infine in 00 stabile per 01:
00
01
11
10
11
11
11
11
00
00
00
10
10
10
10
10
01
00
11
11
00 01 11 10
Dato che arriviamo nello stato finale desiderato, questo percorso non ci crea problemi, ossia nondetermina malfunzionamenti.
Consideriamo adesso l’altro percorso, ossia 11→10→00: da 11 stabile per 00 andiamo in 10instabile, quindi in 10 stabile per 11. Da quest’ultimo non ci possiamo più muovere, per cui nongiungiamo nello stato finale desiderato, a meno di non variare ulteriormente l’ingresso.
Appunti di “Elettronica dei Sistemi Digitali” - Capitolo 5
Autore: Sandro Petrizzelli28
00
01
11
10
11
11
11
11
00
00
00
10
10
10
10
10
01
01
11
11
00 01 11 10
Quindi, ancora una volta, si è verificata una corsa tra le due variabili di stato interno: se variaprima y1 (primo caso), giungiamo nello stato finale desiderato, mentre invece se varia prima y2
(secondo caso), giungiamo in uno stato finale diverso da quello desiderato, ottenendo unmalfunzionamento. In questo caso, si parla di corsa critica.
E’ anche possibile che non ci sia alcuna corsa critica, come per esempio nel passaggio dallo statoB stabile per 10 allo stato D stabile per 11: i possibili percorsi delle variabili di stato interno sono
01→00→10→10 oppure 01→11→10→10
00
01
11
10
11
11
11
11
00
00
00
10
10
10
10
10
01
01
11
11
00 01 11 10
00
01
11
10
11
11
11
11
00
00
00
10
10
10
10
10
01
01
11
11
00 01 11 10
Nel primo caso varia per prima la y2, mentre nel secondo varia prima la y1. In entrambi i casi,però, si giunge nello stato finale desiderato, per cui c’è una corsa, ma non è critica: si parla invece diciclo. Un ciclo può quindi essere definito come la sequenza dellevariazioni delle variabili di stato interno che porta dallo stato(stabile) iniziale fissato allo stato (stabile) finale desiderato.Detto anche in altro modo, un ciclo è un insieme di stati attraverso cui la macchina deve passare perraggiungere lo stato finale desiderato partendo da quello iniziale prefissato. I cicli, per quanto detto,non creano dunque alcun malfunzionamento nella macchina e vedremo infatti che spesso è possibileeliminare i malfunzionamenti proprio introducendo degli opportuni cicli. Nel peggiore dei casi, icicli possono comportare solo dei ritardi diversi a seconda del numero di stati da attraversare perogni percorso contenuto nel ciclo stesso: nel caso considerato poco fa, il ciclo comprende 2 percorsi,ciascuno formato da due stati instabili intermedi, per cui il ritardo è lo stesso in entrambi i casi. Seinvece i due percorsi comprendono un numero diverso di stati instabili intermedi, allora icorrispondenti ritardi saranno necessariamente diversi.
Abbiamo dunque capito che dobbiamo evitare le corse critiche, il che è possibile solo con unopportuno assegnamento. Consideriamo allora nuovamente la tabella di flusso primitiva dell’ultimoesempio:
Macchine asincrone
Autore: Sandro Petrizzelli29
CCD
DAC
DACB
BDCA
10110100xx\.p.s 21
DDDDCCCCBB
AA
E’ evidente, in questo caso, che le corse critiche possono nascere solo in corrispondenza di quellecolonne della tabella in cui compaiono più di uno stato stabile: nella fattispecie, si tratta dellacolonna 01 (dove 01 è l’ingresso) e della colonna 10. Non danno invece problemi le colonne in cuicompare 1 solo stato stabile, in quanto, in questi casi, il peggio che può capitare è un ciclo, ossia,come detto prima, una corsa delle variabili di stato interno che però porta comunque allo stato stabiledesiderato.
Quindi, come prima considerazione da fare, possiamo affermare che è immediato riconoscerel’eventuale presenza di possibili corse critiche: se la tabella di flusso primitivacontiene colonne comprendenti più di uno stato stabile, allora èpossibile che ci siano corse critiche; al contrario, se tutte lecolonne contengono 1 solo stato stabile, allora non ci potrannoessere corse critiche e l’assegnamento potrà essere fatto in modoarbitrario.
Nel caso che stiamo considerando, 2 colonne contengono più di uno stato stabile, per cui ci sonodelle possibili corse critiche. Per rimediare al problema della corse critiche, come già anticipatoprima, dobbiamo rendere adiacenti gli stati coinvolti in tali corse,ossia dobbiamo fare in modo che le transizioni di stato avvenganosempre tra stati la cui codifica binaria sia a distanza 1.
Consideriamo le varie colonne:
• cominciamo dalla colonna 00 (dove 00 è la corrispondente colonna di ingresso): partendo dallostato C stabile per 00, possiamo andare o in A instabile per 01 o in C instabile per 10; perquest’ultimo non abbiamo problemi, essendo stabile, mentre invece ci sono problemi per Ainstabile per 01, in quanto esso è contenuto in una colonna con 2 stati stabili; di conseguenza,dobbiamo rendere adiacenti A e C;
• passiamo alla colonna 01, che contiene due stati stabili: dato che le colonne adiacenti, cioèquella per 00 e quella per 11, presentano ciascuna un solo stato stabile, non ci sono probleminel movimento da A stabile per 01 oppure da D stabile per 01, per cui questa colonna nonimpone delle adiacenze;
• nella colonna 11, l’unico stato stabile è D: da questo stato possiamo andare in D stabile per 01,il che non ci da problemi, oppure in C instabile per 10; dato che, però, quest’ultimo stato sitrova in una colonna con 2 stati stabili, dobbiamo imporre l’adiacenza tra D e C;
• infine, la colonna 10 comprende gli stati stabili B e C: tuttavia, le due colonne adiacenti hannoentrambe un solo stato stabile, per cui non ci sono adiacenze da rispettare.
Andiamo allora a costruire un grafo, detto diagramma delle adiacenze, in cui indichiamoquali sono le adiacenze da rispettare:
Appunti di “Elettronica dei Sistemi Digitali” - Capitolo 5
Autore: Sandro Petrizzelli30
A B
CD
01
10
In questo grafo, gli archi indicano le adiacenze e su tali archi sono indicate anche leconfigurazioni di ingresso in corrispondenza delle quali si creano eventuali corse critiche: adesempio, nell’adiacenza tra D e C, il problema è che, partendo da D stabile per 11 e cambiandol’ingresso in 10, si va in uno stato C che si trova in una colonna (appunto la 10) in cui sono presenti2 stati stabili. Analogo discorso per le altre due adiacenze: ad esempio, per l’adiacenza tra A e C, ilproblema è nel fatto che A si trova nella colonna 01, nella quale ci sono 2 stati stabili.
E’ importante non confondere i bit indicati sugli archi con i codici da assegnare.Una volta ricavate le adiacenze da rispettare, il modo più
immediato di assegnare i codici rispettando tali adiacenze è quellodi usare mappe di Karnaugh, che sono caratterizzate proprio dall’adiacenza tra le variecaselle: inserendo, in modo opportuno, i vari stati nelle caselle dellemappe di Karnaugh, assoceremo, a ciascuno stato, il codice binariocorrispondente all’indirizzo binario della casella in cui si trova.
Avendo in questo caso a che fare con 4 stati, possiamo considerare una mappa di Karnaugh a 2variabili, comprendente cioè 4 caselle:
1
0
10y\y 21
Per riempire questa mappa, bisogna fare una ipotesi di partenza, assegnando arbitrariamentel’indirizzo 00 ad uno qualsiasi degli stati interessati. Sappiamo allora che, nelle macchine asincrone,conviene sempre assegnare l’indirizzo 00 al primo stato, che in questo caso è A, per cui possiamocominciare a riempire la tabella:
1
A0
10y\y 21
Adesso dobbiamo imporre il rispetto delle adiacenze: dato che ogni casella di una mappa diKarnaugh a 2 variabili è adiacente ad altre 2, possiamo rispettare 2 adiacenze per ogni stato: nelnostro caso, lo stato A deve essere adiacente solo allo stato C, per cui possiamo proseguire nelriempimento nel modo seguente:
C1
A0
10y\y 21
Macchine asincrone
Autore: Sandro Petrizzelli31
Restano due caselle da riempire mediante gli stati B e D: dato che D deve essere adiacente a C,l’unica possibilità è
DC1
BA0
10y\y 21
Così facendo, D risulta adiacente a C, come deve effettivamente essere.Abbiamo dunque ottenuto il seguente assegnamento: A=00, B=01, C=10, D=11. Con questo
assegnamento, siamo certi di aver evitato possibili corse critiche: in pratica, quello che abbiamo fattoè stato imporre noi quali variabili di stato devono cambiare per prime, in modo appunto da evitare lecorse critiche.
Possiamo a questo punto riscrivere la tabella di flusso primitiva nel modo seguente:
101011D
110010C
11001001B
01111100A
10110100xx\yy 2121
11111111101010100101
0000
====
Da qui possiamo procedere alla sintetizzazione della parte combinatoria del circuito.Notiamo una cosa importante: quando abbiamo riempito l’ultima casella della mappa di Karnaugh
con lo stato D, siamo stati “fortunati”, in quanto D doveva essere adiacente soltanto a C. Se, percaso, D avesse dovuto essere adiacente anche ad A, non saremmo stati in grado di rispettare questaadiacenza. In questi casi, come vedremo tra un attimo, l’unica possibilità di evitare le corse critiche èquella di “complicare” la macchina, facendo in modo che uno o più stati vengano rappresentati,ciascuno, da più di un codice. Questo modo di procedere comporta un aumento del numero degli statied è chiaro che questo aumento può comportare anche un aumento delle variabili di stato internonecessarie per la codifica binaria: se, per esempio, la macchina minima comprende 8 stati, per i qualibastano 3 variabili y, e siamo costretti ad aggiungere un nuovo stato, avremo bisogno di 4 variabili y,con la conseguente complicazione della struttura della macchina.
Vediamo subito un esempio che chiarisca quanto appena detto.Consideriamo una macchina sequenziale asincrona minima che abbia la seguente tabella di flusso
primitiva:
123
312
31
10110100xx\.p.s 21
33332222111111
Questa macchina può presentare delle corse critiche, visto che ci sono 3 colonne della tabella checomprendono più di uno stato stabile.
Allora, per effettuare l’assegnamento, andiamo ad individuare le adiacenze:
colonna 00 → ci sono due stati stabili in questa colonna, che sono 1 e 3:
• dallo stato 1 possiamo andare in 3 instabile per 01, ma non abbiamo problemi inquanto la colonna 01 presenta un solo stato stabile che è anche uguale agli altristati instabili presenti, oppure nello stato 1 stabile per 10, e nemmeno quiabbiamo problemi in quanto lo stato di arrivo è stabile;
Appunti di “Elettronica dei Sistemi Digitali” - Capitolo 5
Autore: Sandro Petrizzelli32
• al contrario, partendo dallo stato 3, possiamo andare in 3 stabile per 01 e nonabbiamo problemi, ma possiamo anche andare in 1 instabile per 10: dato che lacolonna 10 presenta 2 stati stabili, dobbiamo rendere adiacenti gli stati 3 ed 1;
colonna 01 → c’è un solo stato stabile, ossia 3: da qui possiamo passare in 3 stabile per 00 e nonabbiamo problemi, ma possiamo anche passare in 2 instabile per 11; dato chequesta colonna contiene 2 stati stabili, dobbiamo rendere adiacenti 3 e 2;
colonna 11 → ci sono due stati stabili in questa colonna, che sono 1 e 2:
• dallo stato 1 possiamo andare in 3 instabile per 01, ma non abbiamo problemiper quanto detto prima, oppure nello stato 1 stabile per 10, e nemmeno quiabbiamo problemi in quanto lo stato di arrivo è stabile;
• in modo analogo, dallo stato 2 possiamo andare in 3 instabile per 01, ma nonabbiamo problemi, oppure nello stato 2 stabile per 10, e nemmeno qui abbiamoproblemi in quanto lo stato di arrivo è stabile;
colonna 10 → ci sono anche qui gli stati stabili 1 e 2:
• dallo stato 1 possiamo andare in 1 stabile sia per 11 sia per 00, per cui nonabbiamo problemi;
• dallo stato 2 possiamo andare in 2 stabile per 11 e non abbiamo problemi, mapossiamo anche andare in 1 instabile per 00: dato che questa colonna contienedue stati stabili, dobbiamo rendere adiacenti gli stati 2 ed 1;
Il diagramma delle adiacenze è dunque il seguente:
1
23
10
11
00
Usiamo ancora una volta una mappa di Karnaugh a 2 variabili; assegnando il codice 00direttamente allo stato 1, per rispettare le adiacenze di 1 con 2 e con 3 possiamo riempire la mappanel modo seguente:
31
210
10y\y 21
Tuttavia, dovremmo adesso rispettare l’adiacenza di 2 e 3, che non si può invece rispettare innessun modo: infatti, per rendere adiacenti 2 e 3, dovremmo non rispettare o l’adiacenza di 1con 2 oquella di 1 con 3.
In generale, quindi, siamo in una situazione in cui non è comunque possibile rispettare 1 delle 3adiacenze previste.
Macchine asincrone
Autore: Sandro Petrizzelli33
Abbiamo allora 2 possibilità di procedere:
• la prima possibilità è quella di associare allo stato 2 due diversi codici, ossia duplicare lo stato2 all’interno della tabella:
231
210
10y\y 21
Così facendo, abbiamo garantito tutte le adiacenze;
• in modo del tutto analogo, la seconda possibilità è quella di associare allo stato 3 due diversicodici, ossia duplicare lo stato 3 all’interno della tabella:
331
210
10y\y 21
Anche in questo caso, abbiamo garantito tutte le adiacenze.
Con questo metodo, quindi, garantiamo tutte le adiacenze, ma introduciamo una riga in più nellatabella di flusso primitiva. Per esempio, adottando la duplicazione di 3, la riga in più corrisponde alfatto che lo stato 3 viene codificato con 2 codici:
12113
12103
31012
3001
10110100xx\.p.s 21
33333333
2222111111
====
Dobbiamo adesso associare i vari codici. Possiamo intanto indicare i codici degli stati stabili:
1111111110101010
01010101000000000000
113
103
012
001
10110100xx\.p.s 21
====
Adesso dobbiamo riempire le caselle corrispondente a stati instabili. Possiamo senz’altro riempirele caselle che non hanno a che fare con lo stato 3:
1111111110101010
01010101000000000000
113
103
00012
001
10110100xx\.p.s 21
====
Appunti di “Elettronica dei Sistemi Digitali” - Capitolo 5
Autore: Sandro Petrizzelli34
Adesso, consideriamo ad esempio lo stato 1 stabile per 00 e supponiamo di variare l’ingresso da00 a 01: la variazione porta nello stato 3 instabile per 01 da cui poi si giunge allo stato 3 stabile per01; dato che il codice scelto per lo stato 1 è 00, lo stato 3 instabile intermedio andrà codificato conun codice adiacente a 00, ossia con il codice 10:
1111111110101010
01010101000000000000
113
103
00012
10001
10110100xx\.p.s 21
====
Se avessimo scelto il codice 11, si sarebbe ricreato il problema della corsa critica.Adottando lo stesso criterio, possiamo riempire altre caselle:
01113
00103
1100012
10001
10110100xx\.p.s 21
1111111110101010
01010101000000000000
====
Rimangono ancora vuote due caselle: per continuare a rispettare le adiacenze, dobbiamo fare inmodo che vari una sola variabile di stato interno per volta, per cui la scelta è obbligata:
1001113
0011103
1100012
10001
10110100xx\.p.s 21
1111111110101010
01010101000000000000
====
In pratica, abbiamo riempito le ultime due caselle imponendo due cicli, ossia due corse cheportano comunque dallo stato iniziale prefissato allo stato finale desiderato.
Osserviamo che, in questo caso, la duplicazione dello stato 3 (oppure dello stato 2), non hacomportato alcun aumento del numero di variabili di stato: abbiamo infatti bisogno di 4 codici, checi vengono garantiti da 2 variabili di stato interno. Se, per esempio, avessimo dovuto raddoppiare sia3 sia 2, allora avremmo avuto bisogno di 5 codici, ossia quindi di 3 variabili di stato interno.
Quello appena descritto è un primo modo di procedere, nel quale, come si vede, abbiamofondamentalmente introdotto dei nuovi stati stabili rispetto alla tabella di flusso primitiva iniziale.C’è anche un altro modo di procedere, che andiamo a vedere.
Intanto, una volta accertata la necessità di duplicare lo stato 3 (oppure lo stato 2), nonnecessariamente dobbiamo introdurre, in entrambe le righe corrispondenti allo stato 3, degli statistabili. Partiamo dunque dalla situazione seguente:
Macchine asincrone
Autore: Sandro Petrizzelli35
01113
00103
1100012
10001
10110100xx\.p.s 21
====
1010101001010101000000000000
Abbiamo duplicato lo stato 3, ma abbiamo lasciato vuota la seconda riga ad esso corrispondente.Possiamo adesso riempire questa riga, solo dove è necessario, cioè in modo da garantire leadiacenze:
0110113
0011103
1100012
10001
10110100xx\.p.s 21
====
1010101001010101000000000000
Così facendo, abbiamo garantito le adiacenze, ma abbiamo anche lasciato vuote due caselle, chequindi corrisponderanno, nella sintetizzazione, a delle condizioni don’t care che potrebbero essereutili per la sintetizzazione stessa.
Esempio
Consideriamo un altro esempio:
ACD
AAC
DAB
BAAA
10110100xx\.p.s 21
DDDDCCCCBBBBAA
Questa macchina è soggetta a possibili corse critiche, in quanto le ultime due colonne della tabelladi flusso primitiva contengono ciascuna più di uno stato stabile. Andiamo allora ad individuare leadiacenze da rispettare:
colonna 00 → gli stati D e A vanno resi adiacenti, in quanto A instabile per 10 si trova in unacolonna con 3 stati stabili;
colonna 01 → gli stati D e C vanno resi adiacenti, in quanto C instabile per 11 si trova in unacolonna con 2 stati stabili;
colonna 11 → gli stati B e D vanno resi adiacenti in quanto D instabile per 01 si trova in unacolonna dove, pur essendo presente 1 solo stato stabile, gli stati instabili non sonotutti uguali; per lo stesso motivo, vanno resi adiacenti gli stati C ed A, dove iproblemi vengono proprio da A instabile per 01;
colonna 10 → gli stati A e B vanno resi adiacenti, in quanto B instabile per 11 si trova in unacolonna con 2 stati stabili;
Appunti di “Elettronica dei Sistemi Digitali” - Capitolo 5
Autore: Sandro Petrizzelli36
Il diagramma delle adiacenze è dunque il seguente:
A B
CD
00
00
11
10 01
Usando una mappa di Karnaugh a 4 caselle (2 variabili) è evidente che non possiamo rispettaretutte le adiacenze:
D1
BA0
10y\y 21
Non possiamo nemmeno fare duplicazioni, in quanto non abbiamo caselle vuote a disposizione.Osserviamo allora che, in base al diagramma delle adiacenze, lo stato A e lo stato D devono essere
adiacenti a 3 stati diversi: dato allora che una mappa di Karnaugh a 3 variabili (8 caselle), comprendecelle adiacenti ciascuna ad altre 3, proviamo con tale mappa:
C1
DBA0
10110100yy\y 321
Con la disposizione appena indicata, abbiamo garantito le adiacenze relative allo stato A. Pergarantire quelle relative allo stato D, non possiamo fare altre che duplicare uno o più stati. Adesempio, possiamo duplicare sia B sia D, nel modo seguente:
DC1
DBBA0
10110100yy\y 321
Così facendo, si vede che tutte le adiacenze sono state rispettate. Potevamo anche procedere inaltro modo: per rispettare l’adiacenza D-B, potevamo duplicare D, ponendolo nella casella diindirizzo 011, mentre, per rispettare l’adiacenza D-C, potevamo duplicare C, ponendo nella caselladi indirizzo 110.
Ad ogni modo, comunque scegliamo di procedere, il risultato è che le adiacenze possono essererispettate solo al prezzo di un aumento delle variabili di stato, da 2 a 3: infatti, abbiamo bisogno di 6codici binari diversi.
Il passo successivo è di costruire, mediante i codici appena individuati, la tabella di flussoprimitiva. Cominciamo a riempire quest’ultima con gli stati stabili:
Macchine asincrone
Autore: Sandro Petrizzelli37
)A()C(110D
)A()C(010D
000000100C
)D()A(011B
)D()A(001B
)B(000000000A
10110100xx\yyy 21321
110110110110010010010010
100100100100011011011011001001001001000000
======
Adesso possiamo completare le rimanenti caselle inserendo le configurazioni opportune, cioè inmodo da rispettare le adiacenze:
)A(100110D
000)C(010D
000000100C
010)A(011B
)D(000001B
001000000000A
10110100xx\yyy 21321
110110110110010010010010
100100100100011011011011001001001001000000
======
Restano evidentemente da riempire 4 caselle e lo possiamo fare inserendo delle configurazioni chediano luogo a dei cicli:
010100110D
000110010D
000000100C
010001011B
011000001B
001000000000A
10110100xx\yyy 21321
110110110110010010010010
100100100100011011011011001001001001000000
======
Questa è dunque la prima possibilità, cioè quella di inserire degli stati stabili. L’altra possibilità,come si è visto nel paragrafo precedente, è quella di non inserire nuovi stati stabili, ma solo deglistati instabili laddove necessario, in modo da creare dei cicli. Vediamo allora cosa si ottiene inquesto caso.
Intanto, dobbiamo partire dalla tabella di flusso primitiva riempita nel modo seguente:
)A()C()D()D(110D
)A()C(010D
000000100C
)B()B()D()A(011B
)D()A(001B
)B(000000000A
10110100xx\yyy 21321
======
010010010010100100100100
001001001001000000
Appunti di “Elettronica dei Sistemi Digitali” - Capitolo 5
Autore: Sandro Petrizzelli38
Possiamo adesso riempire la tabella inserendo, dove necessario, degli stati instabili che dianoluogo a dei cicli:
110D
000110010D
000000100C
010011B
011000001B
001000000000A
10110100xx\yyy 21321
======
010010010010100100100100
001001001001000000
Così facendo, abbiamo evitato di inserire stati stabili inutili, garantendo però, nel contempo,l’assenza di corse critiche. Le caselle rimaste vuote sono per noi molto utili in quanto corrispondonochiaramente a condizioni don’t care che possiamo utilizzare per la successiva sintetizzazione dellaparte combinatoria del circuito mediante le mappe di Karnaugh. Non ci occupiamo, però, di questoaspetto, almeno in questo caso, in quanto dovremmo ricorrere a mappe di Karnaugh a 5 variabili (y1,y2, y3, x1,x2), che non sono molto comode da manipolare.
Osserviamo, invece, che, nel passaggio eseguito poco fa, abbiamo scelto si conservare solo laprima riga corrispondente allo stato B e la prima corrispondente allo stato D. In effetti, abbiamo altre3 possibilità. Una di queste, ad esempio, è quella di considerare la seconda riga per entrambi gli stati:
)A()C(110D
)A()C()D()D(010D
000000100C
)D()A(011B
)B()B()D()A(001B
)B(000000000A
10110100xx\yyy 21321
110110110110
100100100100011011011011
000000
======
In questo caso, l’introduzione di stati instabili (e quindi di cicli) porta al seguente riempimento:
010100110D
000010D
000000100C
010001011B
000001B
001000000000A
10110100xx\yyy 21321
110110110110
100100100100011011011011
000000
======
Ancora una volta, abbiamo evitato corse critiche e, allo stesso tempo, abbiamo introdotto unaserie di utili condizioni don’t care.
Macchine asincrone
Autore: Sandro Petrizzelli39
Esempio: misuratore di riflessi
Ritorniamo adesso a trattare la macchina misuratrice di riflessi considerata in precedenza.Abbiamo, in particolare, già ricavato la tabella di flusso primitiva della macchina minima:
000000000000555555010101010101444444
000000003333000011111111222222
000000001111
0025
1124
0100423
0032
0000251
1011010010110100RP\.p.s
Dobbiamo allora procedere all’assegnamento, per cui dobbiamo per prima cosa individuare leadiacenze:
colonna 00→ vanno resi adiacenti gli stati 1 e 2;colonna 01→ vanno resi adiacenti gli stati 1 e 5, 2 e 3, 4 e 2, 5 e 2;colonna 11→ vanno resi adiacenti gli stati 3 e 4 più altre adiacenze già considerate;colonna 10→ nessuna adiacenza oltre quelle considerate.
Il diagramma delle adiacenze è dunque fatto nel modo seguente:
1
2
4
5
10
3
11
1100
00
10
E’ evidente che lo stato 2 necessita di quattro adiacenze, per cui possiamo provare ad utilizzareuna mappa di Karnaugh a tre variabili, ossia a 8 caselle:
1
10
10110100yy\y 321
Abbiamo già inserito lo stato 1 nella casella di indirizzo 000, come consuetudine. Dato che lostadio 2 deve essere adiacente a tutti gli altri stati, per cui possiamo cominciare con il seguenteriempimento:
1
2310
10110100yy\y 321
Così facendo abbiamo garantito l’adiacenza di 1 con 2 e di 2 con 3. Dato, adesso, che 3 deveessere adiacente con 4, ma deve esserlo anche 2, possiamo procedere nel modo seguente:
Appunti di “Elettronica dei Sistemi Digitali” - Capitolo 5
Autore: Sandro Petrizzelli40
241
2310
10110100yy\y 321
Infine, dobbiamo garantire l’adiacenza di 5 sia con 1 sia con 2 ed abbiamo evidentemente 1 solapossibilità:
2451
2310
10110100yy\y 321
Ce la siamo dunque cavata con la duplicazione di un solo stato (lo stato 2): l’assegnamentoottenuto è 1=000, 2=010 oppure 2=110, 3=011, 4=111 e 5=100. Rimangono invece non assegnate leconfigurazioni 001 e 101, le quali, in fase di sintetizzazione, daranno origine a delle condizioni don’tcare.
La tabella di flusso primitiva assume dunque il seguente aspetto:
000000000000100100100100100100010101010101111111111111111111
00000000011011011011000011111111110110110110110110000011111111010010010010010010
00000000000000000000
11)2(1005
11)2(1114
0111111)2(0113
00)3(1102
00)3(0102
0000)2()5(0001
1011010010110100RP\yyy 321
======
Abbiamo evidentemente inserito solo gli stati stabili, scegliendo di duplicare la rigacorrispondente a 2. Andiamo adesso a riempire le caselle rimaste vuote:
000000000000100100100100100100010101010101111111111111111111
00000000011011011011000011111111110110110110110110000011111111010010010010010010
00000000000000000000
111101005
111101114
01111110100113
00)3(1102
000110102
00000101000001
1011010010110100RP\yyy 321
======
E’ rimasta libera una casella, nella quale non possiamo rispettare l’adiacenza tra i codici;: l’unicapossibilità è allora quella di introdurre un ciclo:
Macchine asincrone
Autore: Sandro Petrizzelli41
000000000000100100100100100100010101010101111111111111111111
00000000011011011011000011111111110110110110110110000011111111010010010010010010
00000000000000000000
111101005
111101114
01111110100113
000101102
000110102
00000101000001
1011010010110100RP\yyy 321
======
Con questa scelta, dallo stato 2 (=110) stabile per 01 passiamo allo stato 2(=010) instabile per 11,quindi allo stato 2(=011) instabile per 11 e infine allo stato 2(=011) stabile per 11. Stesso discorso separtiamo dallo stato 2 (=110) stabile per 10 e vogliamo giungere in 2(=011) stabile per 11.
L’altro modo di procedere, come sappiamo, è quello di non introdurre stati stabili inutili e diintrodurre stati instabili (e quindi cicli) la dove serve. Dobbiamo allora partire dalla tabella postanella forma seguente:
000000000000100100100100100100010101010101111111111111111111
00000000011011011011
00001111111101001001001001001000000000000000000000
)11()2(1005
)11()2(1114
01)11(111)2(0113
)00()00()11()11()2()3()2()2(1102
)00()3(0102
0000)2()5(0001
1011010010110100RP\yyy 321
======
Possiamo intanto riempire le caselle dove non abbiamo alternative, giungendo così agli stessirisultati del caso precedente:
000000000000100100100100100100010101010101111111111111111111
00000000011011011011
00001111111101001001001001001000000000000000000000
)11()2(1005
)11()2(1114
01111110110113
)00()00()11()11()2()3()2()2(1102
000110102
0000)2()5(0001
1011010010110100RP\yyy 321
======
Dopo di che, dobbiamo introdurre stati instabili dove servono:
000000000000100100100100100100010101010101111111111111111111
00000000011011011011
00001111111101001001001001001000000000000000000000
111101005
111101114
01111110110113
110101102
000110102
0000)2()5(0001
1011010010110100RP\yyy 321
======
Appunti di “Elettronica dei Sistemi Digitali” - Capitolo 5
Autore: Sandro Petrizzelli42
Con queste scelte, abbiamo imposto che due precise transizioni avvengano mediante un ciclo:
• la transizione da 4 stabile per 01 (o per 10) a 2 stabile per 00 avviene passando prima per2(=110) instabile per 00, poi per 2(=010) instabile per 00 e infine giungendo in 2(010) stabileper 00;
• la transizione da 5 stabile per 01 (o per 10) a 2 stabile per 00 avviene passando prima per2(=110) instabile per 00, poi per 2(=010) instabile per 00 e infine giungendo in 2(010) stabileper 00;
A questo punto, volendo sintetizzare la macchina, dobbiamo scegliere quale delle due soluzioniadottare. Vediamo ad esempio cosa accade scegliendo la prima soluzione, ossia adottando laseguente tabella di flusso primitiva:
000000000000100100100100100100010101010101111111111111111111
00000000011011011011000011111111110110110110110110000011111111010010010010010010
00000000000000000000
111101005
111101114
01111110100113
000101102
000110102
00000101000001
1011010010110100RP\yyy 321
======
Dobbiamo sintetizzare 5 funzioni (Y1,Y2,Y3,z1,z2) di 5 variabili (y1,y2,y3,R,P), per cui utilizziamomappe di Karnaugh a 5 variabili, ossia coppie di mappe di Karnaugh a 4 variabili.
1y10
11
01
00
10110100RP\yy
0y10
11
01
00
10110100RP\yy
1
101198
14151312
6754
231032
1
101198
14151312
6754
231032
==
In queste mappe di Karnaugh, a prescindere da quale sia la funzione sintetizzata, comparirannodelle condizioni don’t care corrispondenti alle configurazioni binarie non assegnate per gli stati, valea dire 001 e 101:
1y10
11
XXXX01
00
10110100RP\yy
0y10
11
XXXX01
00
10110100RP\yy
1
101198
14151312
6754
231032
1
101198
14151312
6754
231032
==
Consideriamo adesso, per esempio, la funzione Y1, che va sintetizzata semplicementeconsiderando per quali combinazioni delle variabili y e degli ingressi il primo bit dello statosuccessivo vale 1:
Macchine asincrone
Autore: Sandro Petrizzelli43
1y11110
111111
XXXX01
111100
10110100RP\yy
0y10
111
XXXX01
100
10110100RP\yy
1
101198
14151312
6754
2310
32
1
101198
14151312
6754
2310
32
==
Si trova facilmente che l’espressione booleana della funzione è la seguente:
3132111 yy'RPyRP'y'Py'RyY ++++=
Adesso, anziché proseguire con le altre 4 funzioni, che si sintetizzano con lo stesso criterio (apatto, ovviamente, di considerare l’opportuno bit dello stato successivo, che sarà il secondo per Y2
ed il terzo per Y3, e l’opportuno bit per l’uscita, che sarà il primo per z1 ed il secondo per z2),vediamo quale espressione viene fuori per la Y1 se adottiamo la strada dell’introduzione dei cicli,ossia se facciamo riferimento alla seguente tabella di flusso primitiva:
000000000000100100100100100100010101010101111111111111111111
00000000011011011011
00001111111101001001001001001000000000000000000000
111101005
111101114
01111110110113
110101102
000110102
0000)2()5(0001
1011010010110100RP\yyy 321
======
La differenza con il caso precedente è dovuta fondamentalmente che alcuni 1 che la funzionepresentava prima sono adesso diventati delle nuove condizioni don’t care, da aggiungere a quelle chederivano dalle configurazioni binarie non assegnate per gli stati. In particolare, abbiamo 3 condizionidon’t care in più, corrispondenti alle 3 caselle vuote nella tabella appena riportata (ovviamente, cisono 3 caselle vuote nella parte relativa agli stati e le corrispondenti 3 nella parte relativa alleuscite). Le mappe di Karnaugh, per la sintetizzazione delle funzioni, avranno dunque le seguenticondizioni don’t care:
1yXXX10
11
XXXX01
00
10110100RP\yy
0y10
11
XXXX01
00
10110100RP\yy
1
101198
14151312
6754
2310
32
1
101198
14151312
6754
2310
32
==
La mappa di sinistra (per y1=0) è rimasta invariata rispetto a prima, mentre l’altra presenta le 3nuove condizioni don’t care.
Dobbiamo adesso vedere solamente per quali combinazioni delle variabili y e degli ingressi ilprimo bit dello stato successivo vale 1, come fatto prima:
Appunti di “Elettronica dei Sistemi Digitali” - Capitolo 5
Autore: Sandro Petrizzelli44
1yXXX10
111111
XXXX01
111100
10110100RP\yy
0y10
111
XXXX01
100
10110100RP\yy
1
101198
14151312
6754
2310
32
1
101198
14151312
6754
2310
32
==
Si trova facilmente che l’espressione booleana della funzione è in questo caso
2131321 'yyyy'RPyRP'yY +++=
Rispetto all’espressione trovata prima, abbiamo evidentemente risparmiato un termine, conconseguente semplificazione del circuito combinatorio.
Circuiti asincroni in modo impulsivoCircuiti asincroni in modo impulsivo
INTRODUZIONE
Quando abbiamo cominciato a parlare dei circuiti (sequenziali) asincroni, abbiamo detto che se nedistinguono 2 categorie fondamentali:
• i circuiti asincroni che lavorano in modo fondamentale sono caratterizzati dal fatto che gliingressi si manifestano sotto forma di variazioni permanenti del livello logico:
tIn altre parole, l’ingresso di un circuito asincrono che lavora in modo fondamentale rimanecostantemente sullo stesso livello logico dopo ogni commutazione: per esempio, conriferimento alla figura, se c’è una commutazione da 0 ad 1, l’ingresso rimane sul valore logico1 fino ad una successiva commutazione;
• al contrario, nei circuiti sincroni che lavorano in modo impulsivo, gli ingressi si manifestanosotto forma di variazioni limitate (nel tempo) di livello logico, da 0 ad 1, ossia appunto comeimpulsi rettangolari di breve durata:
x
t
Macchine asincrone
Autore: Sandro Petrizzelli45
Questo tipo di circuiti, per poter essere sintetizzati, richiedono una caratteristica moltoparticolare: gli impulsi di ingresso non possono mai sovrapporsi, neanche parzialmente.Quindi, se il circuito considerato ha più ingressi, non potranno esserci impulsi che coinvolganopiù di 1 ingresso per volta. Questa è chiaramente una caratteristica che ci aiuta a distinguere uncircuito asincrono che lavora in modo fondamentale da uno che lavora in modo impulsivo:dovendo implementare un circuito sequenziale asincrono, se ciaccorgiamo che il suo funzionamento deve prevedere che gliimpulsi di ingresso si possano sovrapporre, allora possiamosicuramente escludere che si tratti di un circuito che lavora inmodo impulsivo; viceversa, se siamo certi che non ci possanoessere sovrapposizioni tra gli impulsi di ingresso, allorapotremo optare per un circuito che lavora in modo impulsivo.
Come si vedrà meglio nell’esempio che seguirà, un circuito sequenziale asincrono in modoimpulsivo funziona a patto di poter tenere traccia degli ingressi: a questo scopo, la parte di memoriadel circuito sequenziale è sempre costituita da latch di tipo S-R, per cui, nella sintetizzazione,dovremo sempre ricorrere alla tabella di pilotaggio di questi latch.
ESEMPIO: MACCHINA DISTRIBUTRICE DI BIBITE
Supponiamo di voler sintetizzare il circuito digitale che presiede al funzionamento di unamacchina distributrice di bibite, che funziona secondo le seguenti specifiche:
• in primo luogo, tutte le bibite che la macchina è in grado di erogare hanno un costo di £ 600;
• in secondo luogo, la macchina accetta solo 3 tipi di monete e precisamente quelle da £ 100, £200 e £ 500.
Per la sintetizzazione del circuito di controllo di questa macchina, possiamo intanto pensare cheesso abbia 3 ingressi, a seconda di quale moneta è stata inserita, e abbia 1 sola uscita, che comandala distribuzione della bibita richiesta. Indichiamo allora i 3 ingressi con x100, x200 e x300 e l’uscitasemplicemente con z.
Possiamo allora cominciare a costruire una tabella che indica il comportamento della macchina intermini di stati in cui la macchina stessa si trova di volta in volta:
• possiamo per esempio supporre che la macchina si trovi in uno stato iniziale A in cui non èstata inserita alcuna moneta, per cui non viene fornita alcuna bibita (z=0);
• supponiamo adesso di inserire una moneta da £100: passeremo in uno stato B in cui lamacchina ha incamerato £ 100, ma, non essendo queste sufficienti all’erogazione di unabevanda, l’uscita è ancora z=0;
• partendo adesso da B (che corrisponde a £100 di credito) e mettendo altre £100, si passa in unostato successivo C (corrispondente ad un credito di £200), nel quale l’uscita è ancora 0;
• proseguendo in questo modo, si arriva ad uno stato F corrispondente ad un credito di £500: aquesto punto, l’eventuale inserimento di una ulteriore moneta da £100 provoca il passaggio inun nuovo stato G, in cui, essendo il credito giunto a £600, la macchina fornire una bibita, percui z=1.
Appunti di “Elettronica dei Sistemi Digitali” - Capitolo 5
Autore: Sandro Petrizzelli46
Possiamo dunque cominciare la costruzione della tabella di cui si diceva nel modo seguente:
1G600£
0GF500£
0FE400£
0ED300£
0DC200£
0CB100£
0BA0£
zxxxstatocredito 500200100
Adesso vediamo cosa succede quanto introduciamo monete da £200: partendo da A e inserendo£200, andiamo in C, dopodiché andiamo in E e quindi poi in G, dove avviene l’erogazione dellabibita. Possiamo perciò proseguire il riempimento della macchina nel modo seguente:
1G600£
0GF500£
0GFE400£
0ED300£
0EDC200£
0CB100£
0CBA0£
zxxxstatocredito 500200100
Discorso analogo possiamo fare anche se inseriamo £200 quando abbiamo già inserito £100, ossiaquando siamo in B: da B passiamo in D, da D passiamo in F e poi succede una cosa particolare, inquanto, se inseriamo £200 quando siamo in F, la macchina accumula un credito di £700, che non èstato previsto nei 7 stati finora considerati. Dobbiamo allora aggiungere un nuovo stato H, che avràle seguenti caratteristiche: dato che esso corrisponde ad un credito di £700, l’uscita vale sicuramente1, in quanto il credito è sufficiente all’erogazione di una bibita; restano però altre £100 e si tratta distabilire cosa vogliamo che la macchina faccia con queste £100: se la macchina desse il resto, nonavremmo problemi; supponiamo, invece, che la macchina non dia resto, ma dia la possibilità di usareil credito residuo (che in questo caso è appunto di £100) per una ulteriore bibita.
Macchine asincrone
Autore: Sandro Petrizzelli47
Quindi, la tabella si perfeziona nel modo seguente:
1H700£
1G600£
0HGF500£
0GFE400£
0FED300£
0EDC200£
0DCB100£
0CBA0£
zxxxstatocredito 500200100
E’ ovvio che dobbiamo proseguire il riempimento, con riferimento agli stati G ed H, sia dellacolonna relativa a x100 sia quello relativo alla colonna x200. Proseguendo allora con i criteri visti finoad ora, il riempimento della tabella risulta essere il seguente:
1DCH700£
1CBG600£
0HGF500£
0GFE400£
0FED300£
0EDC200£
0DCB100£
0CBA0£
zxxxstatocredito 500200100
Adesso dobbiamo ripetere ancora gli stessi ragionamenti per quanto riguarda la colonna x500, ossiaper l’introduzione, di volta in volta, di monete da £500. In questo caso, si verifica la necessità diaggiungere altri 3 stati, che portano al seguente completamento della tabella:
Appunti di “Elettronica dei Sistemi Digitali” - Capitolo 5
Autore: Sandro Petrizzelli48
1LGFM1000£
1IFEL900£
1HEDI800£
1GDCH700£
1FCBG600£
0MHGF500£
0LGFE400£
0IFED300£
0HEDC200£
0GDCB100£
0FCBA0£
zxxxstatocredito 500200100
Questa è dunque la tabella che descrive il funzionamento degli stati. La caratteristica che si notaimmediatamente è che l’uscita dipende univocamente dallo stato e non dipende dall’ingresso.
Eventualmente, potremmo anche tradurre la tabella appena ricavata in un diagramma degli stati,evidenziando i vari passaggi di stato. Tra le cose principali che tale diagramma metterebbe in risalto,ce quella per cui lo stato iniziale A è uno stato sorgente, ossia uno stato da cui la macchina parte, manel quale la macchina non può più tornare. Non c’è infatti alcuna transizione di stato che abbia Acome stato di arrivo; di conseguenza, possiamo pensare che tale stato sia ottenibile solo tramite unRESET della macchina, esterno al funzionamento della macchina stessa, proprio perchél’inserimento delle monete non può mai portare la macchina in A; ci sarà, perciò, un appositopulsante sulla macchina tramite il quale effettuare il RESET7; ai fini pratici, dato che il circuitosequenziale asincrono che ci accingiamo a progettare avrà la parte di memoria formata da latch ditipo S-R, l’azione del RESET sarà quella di inviare un impulso di clear a tutti i latch S-R presenti, inmodo da cancellare la memoria della macchina.
A questo punto, una volta individuati gli stati della macchina e le rispettive transizioni in funzionedegli ingressi, possiamo passare alla fase di sintetizzazione, il cui primo passaggio consiste nel solitoassegnamento, cioè nella codifica binaria degli stati. In questo tipo di circuiti sequenziali, non c’èalcun criterio particolare da seguire per scegliere la codifica degli stati, per cui ci si può ad esempiolimitare ad una codifica di Grey: ci basta cioè codificare ogni stato in modo che quello successivodifferisca, nella propria codifica, per un 1 solo bit.
Adottando questo criterio e considerando che gli stati sono 11 (per cui servono 4 variabili distato), il codice sarà allora il seguente:
11111101110001000101011101100010001100010000codice
MLIHGFEDCBAstato
Abbiamo evidentemente lasciato inutilizzate le configurazioni binarie 1000,1001,1010,1011,1110. Come in tutti i metodi visti per i precedenti circuiti, queste configurazionidaranno luogo a condizioni don’t care sulle mappe di Karnaugh che utilizzeremo per sintetizzare laparte combinatoria del circuito.
7 Ad esempio, si può pensare ad una operazione di RESET quando la macchina, per un certo tempo ∆ da fissare a priori, non riceve
alcuna moneta in ingresso: in questo caso, però, il RESET non sarebbe manuale, tramite apposito pulsante, ma sarebbeautomatico e verrebbe impostato da un circuito contatore, il quale misura il tempo dall’ultimo inserimento di una moneta e avviail RESET dopo un tempo pari a ∆.
Macchine asincrone
Autore: Sandro Petrizzelli49
Con questo codice, la tabella degli stati e delle uscite diventa la seguente:
11101010101111111M
11100011101101101L
10100011000101100I
10101001000110100H
10111001100010101G
01111010001010111F
01101010101110110E
01100011101100010D
00100011000100011C
00101001000110001B
00111001100010000A
zxxxyyyystato 5002001004321
Evidentemente, avendo usato 4 variabili di stato, la parte di memoria del circuito sarà costituita da4 latch di tipo S-R.
A questo punto, dobbiamo capire con quale criterio va sintetizzata la parte combinatoria delcircuito, la quale avrà il compito di generare, in funzione degli ingressi e delle variabili di statopresente y1,y2,y3,y4, sia l’uscita z (il che è abbastanza immediato) sia il pilotaggio dei 4 latch, vale adire le funzioni S1,R1, S2,R2, S3,R3, S4,R4.
Ci ricordiamo allora della proprietà caratteristica dei circuiti asincroni in modo impulsivo, in basealla quale gli impulsi di ingresso non si possono mai sovrapporre: ciò significa, in termini concreti,che, in ogni istante, si può trovare ad 1 un solo ingresso, mentre tutti gli altri saranno sicuramente a 0(con riferimento alla macchina, ciò significa che possiamo introdurre una moneta per volta e non piùmonete contemporaneamente). In base a questa proprietà, le commutazioni dei latch avverranno oquando x100=1 o quando x200=1 o quando x500=1. Ciò significa che, le funzioni di pilotaggio S1,R1,S2,R2, S3,R3, S4,R4 potranno essere espresse nella seguente forma:
( ) ( ) ( )( ) ( ) ( )( ) ( ) ( )( ) ( ) ( )
...............
xy,y,y,yfxy,y,y,yfxy,y,y,yfR
xy,y,y,yfxy,y,y,yfxy,y,y,yfS
xy,y,y,yfxy,y,y,yfxy,y,y,yfR
xy,y,y,yfxy,y,y,yfxy,y,y,yfS
5004321500,2R2004321200,2R1004321100,2R2
5004321500,2S2004321200,2S1004321100,2S2
5004321500,1R2004321200,1R1004321100,1R1
5004321500,1S2004321200,1S1004321100,1S1
⋅+⋅+⋅=
⋅+⋅+⋅=
⋅+⋅+⋅=
⋅+⋅+⋅=
e così via.Il nostro compito è allora sintetizzare le funzioni fS1,100, fS1,200,... e lo facciamo con i metodi
tradizionali, ossia basandoci sulle commutazioni yk→Yk tra stato presente e stato successivo e sullatabella di pilotaggio dei latch S-R, che ricordiamo essere la seguente:
1X11
RESET1001
SET0110
X000
RSQQ +
Appunti di “Elettronica dei Sistemi Digitali” - Capitolo 5
Autore: Sandro Petrizzelli50
Cominciamo dal latch numero 1, le cui funzioni di pilotaggio sono le seguenti:
( ) ( ) ( )( ) ( ) ( ) 5004321500,1R2004321200,1R1004321100,1R1
5004321500,1S2004321200,1S1004321100,1S1
xy,y,y,yfxy,y,y,yfxy,y,y,yfR
xy,y,y,yfxy,y,y,yfxy,y,y,yfS
⋅+⋅+⋅=
⋅+⋅+⋅=
Dobbiamo dunque sintetizzare le 6 funzioni ( ) ( ) ( )4321500,1S4321200,1S4321100,1S y,y,y,yf,y,y,y,yf,y,y,y,yf ,
( ) ( ) ( )4321500,1R4321200,1R4321100,1R y,y,y,yf,y,y,y,yf,y,y,y,yf .
Le funzioni ( )4321100,1S y,y,y,yf e ( )4321100,1R y,y,y,yf si costruiscono basandosi, oltre che sulla
tabella di pilotaggio del latch, sulla prima colonna dello stato presente (cioè il valore di y1) e sullaprima colonna dello stato successivo (cioè sul valore di Y1) relativo all’ingresso x100:
1001
1001
1001
X000
X000
X000
X000
X000
X000
X000
X000
RSetransizion
111010101111111M
111000111110101L
101000110010100I
101010010011100H
101110011001101G
011110100101111F
011010101111110E
011000111110010D
001000110010011C
001010010011001B
001110011001000A
zxxxyyyystato 115002001004321
→→→→→→→→→→→
→
00110011001100000000000000000000000000000000
La tabella disegnata a destra ci dà i mintermini della funzione 100,1Sf (corrispondente alla colonna
S1) e della funzione 100,1Rf (corrispondente alla colonna R1); le rispettive mappe di Karnaugh sono le
seguenti8:
1f
10
11111
XXXX01
XXXX00
10110100yy\yy
0f
10
11
01
00
10110100yy\yy
100,1R
101198
14151312
6754
2310
4321
100,1S
101198
14151312
6754
2310
4321
=↓
=↓
XXXXX
XXXXX
Come si nota, la determinazione delle espressioni booleane è immediata.Adesso analogo discorso dobbiamo fare per le funzioni ( )4321200,1S y,y,y,yf e ( )4321200,1R y,y,y,yf ,
che si costruiscono basandosi sempre sulla tabella di pilotaggio del latch, ma anche sulla prima
8 Ricordiamo che, in tali mappe con in quelle di tutte le altre funzioni, compaiono le condizioni don’t care corrispondenti alle
configurazioni binarie non utilizzate per la codifica degli stati della macchina. Per distinguere queste condizioni don’t care daquelle derivanti dal pilotaggio del latch S-R, sono state indicate in grassetto.
Macchine asincrone
Autore: Sandro Petrizzelli51
colonna dello stato presente (cioè il valore di y1) e sulla prima colonna dello stato successivo (cioèsul valore di Y1) relative questa volta all’ingresso x200:
1001
1001
1001
X000
X000
X000
X000
X000
X000
X000
X000
RSetransizion
111011010111111M
111001110110101L
101001100010100I
101010100011100H
101110110001101G
011111000101111F
011011010111110E
011001110110010D
001001100010011C
001010100011001B
001110110001000A
zxxxyyyystato 115002001004321
→→→→→→→→→→→
→
00110011001100000000000000000000000000000000
E’ evidente che le due funzioni sono identiche a prima, per cui 0f 200,1S = e 1f 200,1R = .
Infine, per il pilotaggio del latch 1, dobbiamo sintetizzare ( )4321500,1S y,y,y,yf e
( )4321500,1R y,y,y,yf , basandoci sempre sulla tabella di pilotaggio del latch, ma anche sulla prima
colonna dello stato presente (cioè il valore di y1) e sulla prima colonna dello stato successivo (cioèsul valore di Y1) relative questa volta all’ingresso x500:
0X11
0X11
1001
X000
X000
0110
0110
0110
X000
X000
X000
RSetransizion
110101010111111M
110001110110101L
110001100010100I
110100100011100H
111100110001101G
011101000101111F
010101010111110E
010001110110010D
010001100010011C
010100100011001B
011100110001000A
zxxxyyyystato 115002001004321
→→→→→→→→→→→
→
11111111001100000000110011001100000000000000
Andiamo allora a costruire le rispettive mappe di Karnaugh:
43500,1R
101198
14151312
6754
23104321
3243500,1S
101198
14151312
6754
23104321
'y'yf
10
111
XX01
XXX00
10110100yy\yy
yy'yyf
10
XX11
1101
100
10110100yy\yy
=↓
+=↓
XXXXX
XXXXX
Appunti di “Elettronica dei Sistemi Digitali” - Capitolo 5
Autore: Sandro Petrizzelli52
Siamo a questo punto in grado di trovare le espressioni complete delle funzioni di pilotaggio delprimo latch:
( )( ) 500432001001
50032431
x'y'yxxR
xyy'yyS
⋅++=
⋅+=
Sulla base di queste espressioni, possiamo disegnare la parte combinatoria che serve a pilotare ilprimo latch:
Con identici discorsi dobbiamo poi andare a determinare le funzioni di pilotaggio degli altri 3latch. Consideriamo ad esempio il latch 2, le cui funzioni di pilotaggio sono le seguenti:
( ) ( ) ( )( ) ( ) ( ) 5004321500,2R2004321200,2R1004321100,2R2
5004321500,2S2004321200,2S1004321100,2S2
xy,y,y,yfxy,y,y,yfxy,y,y,yfR
xy,y,y,yfxy,y,y,yfxy,y,y,yfS
⋅+⋅+⋅=
⋅+⋅+⋅=
Dobbiamo dunque sintetizzare le 6 funzioni ( ) ( ) ( )4321500,2S4321200,2S4321100,2S y,y,y,yf,y,y,y,yf,y,y,y,yf ,
( ) ( ) ( )4321500,2R4321200,2R4321100,2R y,y,y,yf,y,y,y,yf,y,y,y,yf .
Le funzioni 100,2Sf e 100,2Rf si costruiscono basandosi, oltre che sulla tabella di pilotaggio del latch,
sulla seconda colonna dello stato presente (cioè il valore di y2) e sulla seconda colonna dello statosuccessivo (cioè sul valore di Y2) relativo all’ingresso x100:
Macchine asincrone
Autore: Sandro Petrizzelli53
0X11
0X11
1001
1001
1001
0X11
0X11
0110
X000
X000
X000
RSetransizion
111010101110111M
111000111100011L
101000110100001I
101010010110000H
101110011010010G
011110100010110F
011010101110100E
011000111100100D
001000110100110C
001010010110010B
001110011010000A
zxxxyyyystato 225002001004321
→→→→→→→→→→→
→
11111111001100110011111111111100000000000000
La tabella disegnata a destra ci dà quindi i mintermini della funzione 100,2Sf (corrispondente alla
colonna S2) e della funzione 100,2Rf (corrispondente alla colonna R2); le rispettive mappe di Karnaugh
sono le seguenti:
31100,2R
101198
14151312
6754
23104321
43100,2S
101198
14151312
6754
23104321
'y'yf
10
111
1101
XXX00
10110100yy\yy
'yyf
10
XX11
XX01
100
10110100yy\yy
=↓
=↓
XXXXX
XXXXX
Le funzioni 200,21Sf e 200,2Rf si costruiscono basandosi sulla seconda colonna dello stato presente e
sulla seconda colonna dello stato successivo relative questa volta all’ingresso x200:
0X11
0X11
0X11
1001
1001
0X11
0X11
0110
0110
X000
X000
RSetransizion
111010100111111M
111001100110011L
101001000010001I
101011000011000H
101111100001010G
011110000101110F
011010100111100E
011001100110100D
001001000010110C
001011000011010B
001111100001000A
zxxxyyyystato 225002001004321
→→→→→→→→→→→
→
11111111111100110011111111111100110000000000
La tabella disegnata a destra ci dà quindi i mintermini della funzione 200,2Sf (corrispondente alla
colonna S2) e della funzione 200,2Rf (corrispondente alla colonna R2); le rispettive mappe di
Karnaugh sono le seguenti:
Appunti di “Elettronica dei Sistemi Digitali” - Capitolo 5
Autore: Sandro Petrizzelli54
31200,2R
101198
14151312
6754
23104321
3200,2S
101198
14151312
6754
23104321
'y'yf
10
11
1101
XX00
10110100yy\yy
yf
10
XXX11
XX01
1100
10110100yy\yy
=↓
=↓
XXXXX
XXXXX
Infine, per il pilotaggio del latch 2 dobbiamo sintetizzare 500,2Sf e 500,2Rf , basandoci sempre sulla
tabella di pilotaggio del latch, ma anche sulla seconda colonna dello stato presente e sulla secondacolonna dello stato successivo relative questa volta all’ingresso x500:
1011
0X11
0X11
0X11
0X11
0X11
1011
0110
0110
0110
0110
RSetransizion
101101010111111M
100101110110011L
100001100010001I
101000100011000H
111000110001010G
011101000101110F
001101010111100E
000101110110100D
000001100010110C
001000100011010B
011000110001000A
zxxxyyyystato 225002001004321
→→→→→→→→→→→
→
11111111111111111111111111111100110011001100
Andiamo allora a costruire le rispettive mappe di Karnaugh:
43231500,2R
101198
14151312
6754
23104321
2500,2S
101198
14151312
6754
23104321
'yyyyyf
10
111
101
00
10110100yy\yy
'yf
10
XX11
XXX01
111100
10110100yy\yy
+=↓
=↓
XXXXX
XXXXX
Siamo dunque in grado di trovare anche le espressioni complete delle funzioni di pilotaggio delseconda latch:
( )( ) ( ) ( ) 5004323120031100312
50022003100432
x'yyyyyx'y'yx'y'yR
x'yxyx'yyS
⋅++⋅+⋅=
⋅+⋅+⋅=
Lasciamo stare, adesso, il resto del procedimento per il pilotaggio dei latch 3 e 4.
Macchine asincrone
Autore: Sandro Petrizzelli55
Resta infine da sintetizzare il circuito combinatorio che genera l’uscita in funzione delle variabilidi stato presente y, ma qui la cosa è immediata, visto che l’uscita presenta solo 5 mintermini, che siaggiungono alle solite 5 condizioni don’t care:
3231
101198
14151312
6754
23104321
'yy'yyz
10
11111
1101
00
10110100yy\yy
+=→
XXXXX
Perfezioniamo dunque lo schema logico del circuito, lasciando in sospesa la parte combinatorianecessaria al pilotaggio dei latch 2, 3 e 4:
Alee nei circuiti sequenziali asincroniAlee nei circuiti sequenziali asincroni
INTRODUZIONE
Concludiamo l’argomento dei circuito sequenziali osservando quanto segue: abbiamo visto che uncircuito sequenziale, sincrono o asincrono, si compone di una parte di memoria e di una partecombinatoria; abbiamo inoltre visto, in precedenza, che i circuiti combinatori sono soggetti alfenomeno delle alee, ossia a variazioni indesiderate (e temporanee) delle uscite; ha senso allorachiedersi se anche la parte combinatoria di un circuito sequenziale possa essere soggetta al fenomenodelle alee:
• nel caso di un circuito sequenziale sincrono, generalmente non si hanno problemi di alee;
Appunti di “Elettronica dei Sistemi Digitali” - Capitolo 5
Autore: Sandro Petrizzelli56
• nel caso, invece, di un circuito sequenziale asincrono, se si verifica una momentanea ed erratavariazione di una variabile y che viene trasferita in ingresso, questo può causare dei problemi,in quanto il circuito potrebbe finire in uno stato stabile diverso da quello desiderato.
Consideriamo, ad esempio, un circuito sequenziale asincrono caratterizzato da 2 soli stati interni(che quindi possiamo immediatamente codificare in binario con 0 ed 1) e 2 ingressi e supponiamoche abbia la seguente tabella di flusso primitiva:
111111000000
01
10
10110100xx\y 21
La sintetizzazione della parte combinatoria del circuito è immediata, in quanto dobbiamosintetizzare una sola funzione Y di stato successivo. La mappa di Karnaugh di questa funzione èimmediata:
1111
10
10110100xx\y 21
L’espressione booleana minima della funzione è evidentemente 212 xx'yx)7,3()6,4(Y +=+= .Scegliendo questa espressione, abbiamo evidentemente considerato due mintermini adiacenti, il 6
ed il 7, coprendoli con due implicanti diversi. Sappiamo, allora, che questa scelta può comportarel’insorgere di alee statiche di tipo 1. Vediamo se questo accade, considerando lo schema logico delcircuito che implementa l’espressione booleana appena trovata:
Supponiamo che il circuito si trovi inizialmente nello stato stabile y=1 per x1=1 e x2=1.Supponiamo quindi di far variare x2, passando perciò dall’ingresso 11 all’ingresso 10: in base allatabella di flusso primitiva, lo stato stabile successivo dovrebbe essere 1, stabile appunto per 10 (ilpassaggio avviene direttamente dall’uno all’altro stato). Tuttavia, a causa di una possibile aleastatica, l’uscita Y potrebbe andare momentaneamente a 0: se questo accade, anche y, dopo un ritardo,andrà a 0. Consideriamo allora la porta 2: se la y va a 0 prima che l’uscita della porta NOT vada ad1, l’uscita della porta 2 rimane a 0 e il circuito commuta nello stato 0 per 10, diverso da quellodesiderato.
Il modo di eliminare questo tipo di funzionamento è ancora una volta quello visto a suo tempo peri circuiti combinatori: dobbiamo cioè eliminare l’alea introducendo l’ implicante primo nonessenziale che copre i mintermini adiacenti 6 e 7, in modo da ottenere
Macchine asincrone
Autore: Sandro Petrizzelli57
1212 yxxx'yx)7,6()7,3()6,4(Y ++=++=
ESEMPIO
A questo punto, siamo in grado di condurre il progetto completo di un circuito sequenzialeasincrono. Consideriamo allora un esempio che risulta poi utile come riferimento per il progetto dialtri simili circuiti.
Per prima cosa, descriviamo le specifiche del progetto: vogliamo progettare un flip-flop di tipo Tche sia negative-edge-triggered, che cioè commuti sui fronti di discesa del clock. Il circuito dovràdunque avere 2 ingressi, che sono T (toggle) e C (clock), ed una sola uscita Q. Il funzionamento èquello per cui l’uscita Q viene complementata tutte le volte che T=1 e, ovviamente, lacomplementazione va fatta sui fronti di discesa del clock. Per tutte le altre combinazioni di ingresso(considerando appunto T e C come ingressi) l’uscita rimane invariata. Ricordiamo, infatti, che latabella di pilotaggio di un flip-flop di tipo T è la seguente:
RESET101
011
SET110
000
TQQ +
Nonostante questo circuito possa essere usato come un flip-flop in un circuito sequenzialesincrono, il progetto interno del flip-flop è un tipico problema asincrono (e il discorso vale perqualunque altro tipo di flip-flop).
Il primo passo del progetto consiste, come sappiamo, nel tracciare la tabella di flusso primitiva delcircuito. In questo, possiamo facilitarci se disegniamo una tabella in cui elenchiamo tutte i possibilistati della macchina, corrispondenti alle combinazioni degli ingressi T e C e dell’uscita Q:
• cominciamo dalla condizione di ingresso TC=11, che assegniamo allo stato A, caratterizzato dauscita Q=0; affinché si possa avere una commutazione dell’uscita, ci deve essere un fronte didiscesa del clock, il che significa che T deve rimanere ad 1, mentre C deve andare a 0: quindi,il circuito passa in uno stato B, caratterizzato da Q=0, quando TC=10;
Appunti di “Elettronica dei Sistemi Digitali” - Capitolo 5
Autore: Sandro Petrizzelli58
• consideriamo adesso nuovamente la condizione di ingresso TC=11, ma consideriamo un nuovostato C che associ uscita Q=1 a questo stato: in modo analogo a prima, si avrà unacommutazione (1→0) dell’uscita non appena il clock torna a 0, per cui avremo un nuovo statoD caratterizzato da TC=10 e Q=0;
• le due appena elencate sono le uniche possibilità di transizione dell’uscita; in tutti gli altripossibili casi, nei quali cioè T=0, non ci possono essere variazioni dell’uscita.
Possiamo dunque compilare la tabella nel modo seguente:
110H
100G
010F
000E
001D
111C
101B
011A
QCTstato
uscitaingressi
A questo punto, possiamo andare a compilare la tabella di flusso primitiva, nella qualeindicheremo gli 8 stati appena ricavati:
11HH11GG
00FF00EE
00DD11CC
11BB00AA
H
G
F
E
D
C
B
A
1011010010110100TC\.p.s
Abbiamo per il momento indicato solo gli stati stabili e le rispettive uscite.Possiamo anche inserire dei trattini orizzontali (“-”) in quelle caselle che corrispondono a
variazioni contemporanee di entrambe le variabili di ingresso:
Macchine asincrone
Autore: Sandro Petrizzelli59
−−−−
−−−−
−−−−
−−−−
11HH11GG
00FF00EE
00DD11CC
11BB00AA
H
G
F
E
D
C
B
A
1011010010110100TC\.p.s
Infine, dobbiamo indicare gli stati instabili (ai quali per il momento non associamo alcuna uscita,in quanto questo andrà fatto solo sulla macchina minima): per esempio, partendo dallo stato Astabile per 11, la variazione dell’ingresso a 01 può portare o nello stato F o nello stato H: in realtà,può portare solo in F, che ha uscita Q=0 con A, in quanto T è passato da 1 a 0; se invece variamol’ingresso da 11 ad 10, andiamo in B. Consideriamo poi lo stato B stabile per 10 e con uscita 1:variando l’ingresso da 10 a 11, l’uscita non deve commutare, in quanto si considera un fronte disalita del clock, per cui andiamo nello stato C; l’uscita non commuta nemmeno se variamo l’ingressoda 10 a 00, per cui andiamo in G.
Seguendo questo criterio, la tabella si riempie nel modo seguente:
−−−−
−−−−
−−−−
−−−−
11HH11GG
00FF00EE
00DD11CC
11BB00AA
CGH
BHG
AEF
DFE
AED
DHC
CGB
BFA
1011010010110100TC\.p.s
Il passo successivo è quello di minimizzare la macchina e ricorriamo perciò alla tabellatriangolare, che avrà 7 righe e 7 colonne. Il riempimento risulta essere il seguente:
GFEDCBA
VXH,F
G,E
C,A
G,EVV
C,A
H,FH
\\H,F
G,EX
D,B
G,ED,BVH,FG
\\\\VVC,A
H,F
C,A
G,EVF
\\\\\\VH,FD,B
G,ED,BE
\\\\\\\\C,AXD,BD
\\\\\\\\\\D,BXC
\\\\\\\\\\\\C,AB
Appunti di “Elettronica dei Sistemi Digitali” - Capitolo 5
Autore: Sandro Petrizzelli60
Controllando se le caselle contrassegnate con X (stati distinguibili, data l’uscita diversa)comportano altre distinguibilità, si perviene al seguente risultato finale:
GFEDCBA
VXXXVVXH
\\XXXXVXG
\\\\VVXXVF
\\\\\\VXXXE
\\\\\\\\XXXD
\\\\\\\\\\XXC
\\\\\\\\\\\\XB
Le coppie di stati da considerare sono quelle contrassegnate con V (stati indistinguibili):
colonna A → (A,F)colonna B → (B,H), (B,G)colonna C → (C,H);colonna D → (D,F), (D,E)colonna E → (E,F);colonna F → nientecolonna G → (G,H)
Con queste coppie possiamo formare i seguenti massimi compatibili:
(A,F)(B,H),(B,G),(G,H)→(B,G,H)(C,H)(D,F),(D,E),(E,F)→(D,E,F)
Abbiamo ottenuto 4 massimi compatibili. Dobbiamo scegliere il minimo numero di massimicompatibili che garantisce intanto la copertura di tutti gli stati della macchina di partenza: è evidenteche tale copertura è garantita solo se li prendiamo tutti e 4, per cui essi costituiranno gli stati dellamacchina minima. Li indichiamo nel modo seguente: a=(A,F), b=(B,G,H), c=(C,H), d=(D,E,F);
Possiamo allora di segnare la tabella di flusso primitiva della macchina minima:
000000dddddd1111cccc
111111bbbbbb0000aaaa
a)F,E,D(d
db)H,C(c
c)H,G,B(b
bd)F,A(a
1011010010110100TC\.p.s
==
==
E’ evidente che, nel compilare questa tabella, abbiamo fatto una scelta, in quanto gli stati F ed Hsono contenuti, ciascuno, in 2 massimi compatibili diversi: quando compare lo stato F, abbiamoscelto di indicare il massimo compatibile a se ci troviamo nella riga corrispondente ad a, oppure d seci troviamo nella riga corrispondente a d; stesso discorso per lo stato H: nella riga corrispondente al
Macchine asincrone
Autore: Sandro Petrizzelli61
massimo compatibile b, abbiamo considerato b, mentre nella riga corrispondente al massimocompatibile c abbiamo considerato c.
Dobbiamo adesso riempire le caselle relative alle uscite degli stati stabili e dobbiamo farlo inmodo da evitare spike (quando l’uscita di partenza è uguale a quella di arrivo):
000000dddddd1111cccc
111111bbbbbb0000aaaa
ad
1dbc
1cb
bda
1011010010110100TC\.p.s
Rimangono 4 uscite instabili non specificate e le possiamo riempire in modo, ad esempio, daanticipare la transizione di uscita, ossia in modo da imporre che l’uscita vari nel passaggio dallostato iniziale stabile allo stato intermedio instabile:
000000dddddd1111cccc
111111bbbbbb0000aaaa
1ad
01dbc
1cb
11bda
1011010010110100TC\.p.s
Adesso c’è da affrontare il problema dell’assegnamento. Il fatto che tutte le colonne contenganopiù di uno stato stabile ci dice che ci possono essere corse critiche, per cui siamo costretti a ricercare(e poi garantire) le adiacenze:
colonna 00 → nessuna adiacenza;colonna 01 → vanno resi adiacenti gli stati a e d e gli stati c e d;colonna 11 → vanno resi adiacenti gli stati a e b e gli stati c e d (che però sono stati già
considerati);colonna 10 → vanno resi adiacenti gli stati b e c.
Il diagramma delle adiacenze è fatto nel modo seguente:
A B
CD
Possiamo evidentemente utilizzare una mappa di Karnaugh a 2 sole variabili:
CD1
BA0
10y\y 21
Appunti di “Elettronica dei Sistemi Digitali” - Capitolo 5
Autore: Sandro Petrizzelli62
L’assegnamento ottenuto è dunque il seguente: A=00, B=01, C=11, D=10.La corrispondente tabella di flusso primitiva è la seguente:
000000101010101010111111111111
111111010101010101000000000000
10010d
01100111c
11101b
11011000a
1011010010110100TC\yy 21
====
Non resta, a questo punto, che sintetizzare la parte combinatoria del circuito, che deve dar luogoalle 3 funzioni Y1,Y2 e Q delle 4 variabili y1,y2, T e C. Usiamo dunque mappe di Karnaugh a 4variabili:...............................
Autore: SANDRO PETRIZZELLIe-mail: [email protected]
sito personale: http://users.iol.it/sandrysuccursale: http://digilander.iol.it/sandry1