Appunti di Elettronica Digitale -...

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


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



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


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



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


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:



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


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



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


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



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


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:



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


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



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


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.



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


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:



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


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):



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


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:



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


• 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.



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


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.



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


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:



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


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;



• 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


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

====



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


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;



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


)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



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


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:



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


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

======



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


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:



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


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.



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£


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


Quindi, la tabella si perfeziona nel modo seguente:

1H700£

1G600£

0HGF500£

0GFE400£

0FED300£

0EDC200£

0DCB100£

0CBA0£


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£


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:



1LGFM1000£

1IFEL900£

1HEDI800£

1GDCH700£

1FCBG600£

0MHGF500£

0LGFE400£

0IFED300£

0HEDC200£

0GDCB100£

0FCBA0£


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


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



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 +



Cominciamo dal latch numero 1, le cui funzioni di pilotaggio sono le seguenti:

( ) ( ) ( )( ) ( ) ( ) 5004321500,1R2004321200,1R1004321100,1R1

5004321500,1S2004321200,1S1004321100,1S1



⋅+⋅+⋅=

⋅+⋅+⋅=

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


→→→→→→→→→→→

→

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


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


→→→→→→→→→→→

→

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


→→→→→→→→→→→

→

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



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



⋅+⋅+⋅=

⋅+⋅+⋅=

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


0X11

0X11

1001

1001

1001

0X11

0X11

0110

X000

X000

X000

RSetransizion

111010101110111M

111000111100011L

101000110100001I

101010010110000H

101110011010010G

011110100010110F

011010101110100E

011000111100100D

001000110100110C

001010010110010B

001110011010000A


→→→→→→→→→→→

→

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


→→→→→→→→→→→

→

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:



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


→→→→→→→→→→→

→

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


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;



• 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


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;



• 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


−−−−

−−−−

−−−−

−−−−

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



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


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):



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:



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



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

Appunti di Elettronica Digitale -...

Documents

Transcript of Appunti di Elettronica Digitale -...