Appunti di Elettronica Digitale - Libero...

Appunti di Elettronica DigitaleAppunti di Elettronica DigitaleCapitolo 6 - Macchine a stati algoritmiche

Introduzione ............................................................................................... 1Diagramma di flusso di una ASM............................................................... 2

Operazioni sui registri .......................................................................... 5Considerazioni sulla temporizzazione ................................................... 6

Esempio: contatore binario a 4 bit .............................................................. 6Diagramma di flusso............................................................................. 7Sequenza temporale delle operazioni e relativa tabella ...................... 11Diagramma degli stati del circuito di controllo .................................. 13Sintetizzazione del circuito di controllo .............................................. 16Sintesi del circuito di pilotaggio di E ed F.......................................... 20

INTRODUZIONE

Le informazioni digitali memorizzate in un sistema digitale possono essere classificate sia comedati sia come informazioni di controllo:

• i dati sono elementi discreti di informazione che sono manipolati per realizzare procedurearitmetiche, logiche, di spostamento e così via. Queste operazioni sono implementate concomponenti digitali come sommatori, decoder, multiplexer, contatori e registri a scorrimento;

• le informazioni di controllo forniscono segnali di comando che supervisionano alle varieoperazioni sui dati, in modo che vengano svolte le operazioni desiderate sui dati stessi.

In base a questa divisione, il progetto logico di un sistema digitale può essere diviso in due partidistinte:

• una parte riguarda il progetto dei circuiti digitali che realizzano le operazioni di elaborazionedei dati;

• l’altra parta riguarda il prodotto del circuito di controllo che supervisiona alle operazioni edalla sequenza con cui vengono svolte.

La relazione tra il controllo logico ed il processore di dati vero e proprio, in un sistema digitale, èmostrata nella figura seguente:

Circuitodi

controllo

Elaboratoredeidati

Ingressiesterni

Dati diingresso

Dati diuscita

Condizioni di stato

Appunti di “Elettronica dei Sistemi digitali” - Capitolo 6

Autore: Sandro Petrizzelli2

Il sottosistema elaboratore dei dati manipola i dati nei registri in accordo ai requisiti del sistema.Il circuito di controllo avvia, nel modo opportuno, la sequenza di comandi per l’elaboratore: esso usale condizioni di stato dell’elaboratore per impostare la sequenza di controllo sullo stesso elaboratore.In altre parole, “osserva”, prelevando opportuni segnali elettrici, il comportamento dell’elaboratore epredispone segnali di controllo che impongono all’elaboratore un certo funzionamento.

Il circuito di controllo è dunque un circuito sequenziale, il cui stato interno determina il valore deivari segnali di controllo del sistema. In ogni istante, lo stato del circuito di controllo inizializza unprefissato insieme di comandi. In dipendenza dalle condizioni di stato e da altri ingressi esterni, ilcircuito di controllo passa in uno stato successivo per avviare nuove operazioni.

La sequenza di controllo (control sequence) e le operazioni di elaborazione dati (data-processingtasks) di un sistema digitale sono specificate dal contenuto di un algoritmo hardware. Sappiamoche un algoritmo consiste in un numero finito di passi procedurali che specifica come ottenere lasoluzione di un dato problema. In modo analogo, un algoritmo hardware è unaprocedura per implementare il problema in esame con un assegnato setdi dispositivi.

Un diagramma di flusso è il modo più conveniente di descrivere la sequenza dei passi proceduralie dei percorsi di decisione previsti da un algoritmo, sia esso un algoritmo software (da usare perstilare un programma) oppure un algoritmo hardware: in quest’ultimo caso, il diagramma di flussotraduce le istruzioni da eseguire in un diagramma informativo che elenca la sequenza di operazioniinsieme alle condizioni necessarie alla loro esecuzione. Un particolare diagramma di flusso che èstato sviluppato specificamente per definire algoritmi hardware digitali è detto diagramma di unamacchina a stati algoritmica (ASM - Algorithmic State Machine). Parlare di macchinaa stati equivale a parlare di un circuito sequenziale, che è la strutturabase di ogni sistema digitale.

Il diagramma di una ASM rappresenta un convenzionale diagramma di flusso, ma va interpretatoin modo leggermente diverso. Un diagramma di flusso convenzionale descrive la sequenza di passiprocedurali e i percorsi di decisione per un algoritmo, senza però tener conto della relazionetemporale tra i vari passi. Al contrario, il diagramma di una ASM descrive la sequenza degli eventiinsieme alla relazione temporale che intercorre tra gli stati di un controllore sequenziale e gli eventiche si verificano nel passaggio tra uno stato e l’altro. Un simile diagramma è perciò specificatamenteadatto per definire accuratamente la sequenza di controllo e le operazioni di elaborazione dei dati inun sistema digitale, tenendo conto delle caratteristiche dell’hardware digitale.

In questi paragrafi ci occupiamo allora di presentare un metodo per progettare un sistema digitaleusando un diagramma di una ASM, secondo lo schema indicato nella figura precedente. Le relazionitemporali tra i vari blocchi saranno spiegate mediante un esempio.

DIAGRAMMA DI FLUSSO DI UNA ASMIl diagramma di flusso di una ASM è un tipo speciale di diagramma di flusso, utilizzabile per

descrivere le operazioni sequenziali in un sistema digitale. Il diagramma è composto di 3 elementifondamentali, variamente combinati a seconda del sistema che si intende realizzare: i 3 blocchi sonoil blocco di stato, il blocco decisionale e il blocco condizionale. Ognuno di questi blocchi èchiaramente rappresentato da un proprio simbolo.

Il blocco di stato indica lo stato in cui si trova la macchina:

Macchine a stati algoritmiche


Operazioni sui registriGenerazione di uscite

nome dellostato

codifica binariadello stato

Il simbolo è dunque un rettangolo con una serie di indicazioni: in alto a sinistra, viene indicato ilnome convenzionale che abbiamo attribuito allo stato considerato (ad esempio A, T1, S3 e così via);in alto a destra, viene indicata la codifica binaria dello stesso stato; all’interno del rettangolovengono indicate le operazioni su registri o i nomi dei segnali di uscita che il circuito di controllogenera quando la macchina raggiunge lo stato considerato: per esempio, se lo stato considerato èstato chiamato A e prevede che un certo registro R debba essere inizializzato a 0, il blocco conterràla scritta R←0, che sta appunto ad indicare che, non appena la macchina giunge nello stato A, ilregistro R viene riempito con l’informazione 0 (sulle operazioni sui registri torneremo in seguito). Aldi sotto della scritta R←0, potrebbe esserci poi una scritta del tipo START, che può ad esempioindicare un segnale di uscita che avvia una certa operazione.

Il blocco decisionale descrive invece l’effetto di un ingresso sul sottosistema di controllo:

Condizione0 1

Percorso di uscitaper condizionenon verificata

Percorso di uscitaper condizione

verificata

Si tratta dunque di un rombo con due percorsi di uscita, all’interno del quale è indicata una certacondizione (ad esempio il controllo del contenuto di un registro o di un singolo flip-flop oppure lalettura di un ingresso oppure quella di una uscita): se la condizione è verificata, allora si segue ilramo corrispondente, mentre, in caso contrario, si segue l’altro ramo.

Il blocco di stato ed il blocco decisionale sono dunque familiari, dato l’uso che se ne fa neinormali diagrammi a blocchi. Il terzo elemento, detto blocco decisionale, è invece caratteristicodelle ASM:



Operazioni sui registriGenerazione di uscite

Dall'uscita diblocco condizionale

Il simbolo è una figura ovale, dove gli angoli arrotondati servono a distinguerlo dal blocco distato.

Il percorso di ingresso ad un blocco decisionale deve provenire dall’uscita di un bloccocondizionale: infatti, le operazioni indicate all’interno del blocco decisionale sono realizzateimmediatamente dopo l’effettuazione della decisione, senza aspettare tempi ulteriori.

In altre parole, esiste una fondamentale differenza che distingue un blocco decisionale da unblocco di stato: le operazioni indicate in un blocco di stato vengono effettuate solo al colpo di clocksuccessivo a quello che ha determinato lo stato precedente; al contrario, una volta raggiunto un datostato ed eseguite le corrispondenti operazioni, vengono anche effettuati tutti i confronti successivi eeventuali operazioni inserite in blocchi decisionali dipendenti dai confronti stessi.

Per capire meglio la questione, facciamo un semplice esempio, rappresentato dal seguentediagramma:

START

T1

E0 1

Rç0

FçE

T2

Il circuito di controllo genera un segnale di START quando la macchina si trova nello statoindicato T1 (non abbiamo indicato la corrispondente codifica binaria in quanto, per ora, non ciinteressa). Non appena la macchina è nello stato T1, il controllo va a verificare il valore di una uscitaindicata con E: se risulta E=1, il registro R viene posto a 0; altrimenti, R conserva il propriocontenuto. Al colpo di clock successivo al raggiungimento dello stato T1, la macchina si portacomunque in T2, in corrispondenza del quale l’uscita indicata con F assume lo stesso valore di E.



La differenza tra il blocco di stato e il blocco decisionale è allora evidente: non appena lamacchina giunge nello stato T1, a seguito di un colpo di clock, viene effettuato subito il controllodell’uscita E e, nel caso in cui E=1, viene anche inizializzato il registro R; solo, però, al successivocolpo di clock la macchina si porta nello stato T2.

In realtà, il comportamento è ancora più sottile. Supponiamo che R sia un singolo flip-flop esupponiamo che, ad un dato colpo di clock, la macchina sia giunta nello stato T1; una volta raggiuntolo stato T1, il controllore esegue il controllo di E, ma, in caso E=1, non può, di fatto, inizializzare R,in quanto c’è comunque bisogno di un ulteriore colpo di clock per impostare il contenuto di questoflip-flop1. Di conseguenza, quello che realmente viene fatto dal controllore, come vedremo meglionell’esempio che seguirà, è predisporre l’ingresso o gli ingressi (nel caso di un J-K) del flip-flop inmodo che esso commuti, nel modo desiderato, non appena arriva il successivo colpo di clock. Da unpunto di vista concettuale, però, rimane la differenza con il blocco di stato.

Appare a questo punto evidente che il diagramma di flusso di una ASM è moltosimile ad un diagramma degli stati: ogni blocco di stato è infatti equivalente ad unostato in un circuito sequenziale; il blocco decisionale è equivalente all’informazione binaria scrittasugli archi orientati (directed lines) che connettono due stati in un diagramma di stato. Diconseguenza, è spesso conveniente convertire il diagramma di flusso inun diagramma di stato e quindi usare le procedure tipiche deicircuiti sequenziali per progettare il circuito di controllo. Ad ognimodo, è anche evidente che il diagramma di una ASM è più completo di un diagramma di stato,proprio perché indica le relazioni temporali tra le varie operazioni.

Operazioni sui registri

Abbiamo detto che all’interno del blocco di stato e/o del blocco decisionale sono indicateoperazioni su registri e/o uscite. In particolare, le operazioni su registri possono essere solo 6:

• azzeramento di un registro (clear): indicato il registro con A, l’operazione di azzeramento èrappresentata dall’espressione A←0;

• settaggio di un registro (set): l’operazione di settaggio è rappresentata dall’espressione A←1;

• trasferimento dati tra due registri: indicati con A e B due registri aventi la stessa capacità dimemoria (ad esempio due registri a scorrimento entrambi con lo stesso numero di bit), iltrasferimento dei dati da B ad A sarà indicato da A←B;

• incremento del contenuto di un registro: lo si indica con A←A+1

• decremento del contenuto di un registro: lo si indica con A←A-1

• somma di due registri: se il risultato della somma dei registri A e B va memorizzato in A,l’operazione sarà indicata da A←A+B.

Un sistema digitale è molto spesso definito dai registri che contiene e dalle operazioni che sonorealizzate sui dati memorizzati in tali registri. Un registro, nel suo significato più completo, includeregistri di memorizzazione (storage registers), registri a scorrimento, contatori a flip-flop singoli.

1 Ricordiamo che i flip-flop commutano sui fronti di salita o di discesa del clock, per cui, se l’impulso di clock è già arrivato, non è

possibile compiere alcuna operazione su un flip-flop finché non arriva il colpo di clock successivo.



Considerazioni sulla temporizzazione

La temporizzazione di tutti i registri e flip-flop contenuti in un sistema digitale è controllata da ungeneratore di clock principale (master-clock generator). Gli impulsi di clock sonoapplicati non solo ai registri del sottosistema di elaborazione deidati, ma anche a tutti i flip-flop del circuito logico di controllo.

Anche gli ingressi sono sincronizzati con gli impulsi di clock, dato che essi sono normalmentegenerati come uscite di un altro circuito che usa lo stesso segnale di clock. Se il segnale di ingressocambia in un istante arbitrario, indipendente dal clock, possiamo parlare di ingresso asincrono.Dato che gli ingressi asincroni possono comportare una serie di problemi, dei quali si è parlato nelcapitolo sui circuiti sequenziali asincroni, noi supporremo, d’ora in poi, che tutti gli ingressi sianosincronizzati con il clock e cambino eventualmente valore solo in corrispondenza delle transizioni(edge transition) del clock. In modo analogo, saranno anche sincronizzati allo stesso clock ogniuscita che è funzione dello stato presente e ogni ingresso sincrono.

ESEMPIO: CONTATORE BINARIO A 4 BIT

Supponiamo di dover realizzare un sistema digitale che costituisce un contatore binario a 4 bit,avendo a disposizione il contatore binario vero e proprio e 2 flip-flop. Le specifiche che questocontatore deve rispettare sono le seguenti:

• l’operazione di conteggio inizia non appena viene posto ad 1 un segnale di START (cheindicheremo con S): quando S=1, il contatore (che indicheremo con A) viene azzerato e vieneanche azzerato uno dei due flip-flop (precisamente quello che indicheremo con F, distintodall’altro, che invece indicheremo con E);

• indicati con A4,A3,A2,A1 i 4 bit del conteggio (dove quindi A4 è il bit più significativo e A1

quello meno significativo), la prima specifica è che risulti E=0 fin quando A3=0;

• la prima situazione particolare si deve verificare quando la seconda cifra significativa delconteggio diventa 1; la specifica da rispettare è quella per cui, non appena risulta A3=1 (quindial 4° colpo di clock, 0100), il flip-flop E va posto ad 1 (E←1), dopo di che il conteggio puòessere ripreso;

• la seconda situazione particolare si deve invece verificare quando sia la prima sia la secondacifra significativa del conteggio risultano 1; la specifica da rispettare è quella per cui, nonappena risulta A4=A3=1 (quindi al 12° colpo di clock, 1100), il flip-flop F va posto ad 1 (F←1)ed il conteggio va interrotto.

Queste sono le specifiche che la macchina deve avere. E’ allora evidente una cosa: affinché questespecifiche vengano rispettate, deve necessariamente esserci un circuito di controllo che, leggendo ivalori di A3 ed A4, deve di volta in volta stabilire le operazioni da compiere sui flip-flop E ed F edeve anche stabilire se avviare, proseguire o interrompere il conteggio. Ecco dunque che si ripresentalo stesso schema citato in precedenza:



Circuitodi

controllo

Contatore AFlip-flop EFlip-flop F

Ingressodi START

Clock

Valore delconteggio

Condizioni di stato

In questo caso, abbiamo indicato anche il fatto che il segnale clock è comune al circuito dicontrollo ed al circuito per l’elaborazione e abbiamo inoltre tenuto conto che l’ingresso del circuitoper l’elaborazione non è un ingresso di dati vero e proprio, ma è rappresentato dallo stesso clock (inquanto lo scopo è proprio quello di contare gli impulsi di clock). Adesso ci occuperemo di conoscerei dettagli dei due circuiti da sintetizzare, per cui potremo perfezionare, fino al minimo dettaglio,quello schema.

Diagramma di flusso

Per sintetizzare questa macchina, il primo passo consiste nel realizzare il diagramma di flusso.Partiremo evidentemente da uno stato iniziale T0 in cui la macchina è inerte, cioè non compie alcunaoperazione, ed è in attesa del segnale di START, proveniente dall’esterno, per avviarsi. Avremodunque il blocco di stato corrispondente a T0, ma non avremo alcuna particolare operazione daindicare al suo interno, proprio perché la macchina è inerte. L’uscita del blocco dovrànecessariamente andare ad un blocco condizionale, che corrisponde appunto a controllare il valoredell’ingresso S: fin quando S=0, la macchina permane in T0.

La parte superiore del diagramma è dunque fatta nel modo seguente:

Statoiniziale

T0

S0 1

Supponiamo che, in un certo istante, arrivi il segnale di start, per cui la condizione S=1 èverificata. Le specifiche dicono che, per prima cosa, devono essere azzerati sia il contatore A sia ilflip-flop F2: queste due operazioni andranno inserite in un blocco decisionale da porre in cascata alblocco condizionale:

2 Notiamo che le specifiche non si preoccupano del contenuto del registro E, contenuto che verrà fuori in seguito.



Statoiniziale

T0

S0 1

Fçç0Açç0

E’ ovvio che l’azzeramento non può essere ottenuto in qualsiasi istante, ma solo all’impulso diclock successivo; di conseguenza, il circuito di controllo predispone i segnali necessari affinché, alsuccessivo colpo di clock, vengano eseguite tali due istruzioni.

La macchina deve trovarsi adesso in nuovo stato T1, in corrispondenza del quale le specifichedicono che essa deve cominciare a contare, incrementando di 1 il contenuto di A ad ogni impulso diclock:

Statoiniziale

T0

S0 1

Fçç0Açç0

AççA+1

T1

Quindi, al secondo colpo di clock dopo lo start, la macchina avvia il conteggio, per cui ilcontenuto del contatore A, in corrispondenza del 2° colpo di clock, sarà 0001, mentre prima era 0000dato l’azzeramento di A..

Il conteggio (cioè l’incremento di A) non va però all’infinito, in quanto le specifiche dicono chebisogna controllare i valori di A3 ed A4. In particolare, il primo bit da controllare è chiaramente A3,che, essendo meno significativo di A4, commuterà prima (da 0 ad 1). Di conseguenza, dopo ogniincremento di A, la macchina (e precisamente il circuito di controllo) deve verificare il valore di A3:se A3=0, le specifiche dicono che il conteggio può proseguire e che E va posto a 0, altrimenti bisognaimpostare ad 1 il valore di E.



Possiamo allora perfezionare il diagramma nel modo seguente:

Statoiniziale

T0

S0 1

Fçç0Açç0

AççA+1

T1

A30 1

Eçç0

Quando si verifica la condizione A3=1? Evidentemente, quando sono stati contati 4 colpi di clock,cui va aggiunto il 5° colpo di clock che c’è stato tra quando è avvenuto S=1 al primo colpo di clockconteggiato. Quindi, dopo 5 colpi di clock dall’arrivo dello START, si verifica A3=1: le specifichedicono allora che, a questo punto, bisogna porre E=1. Considereremo allora ancora una volta unblocco decisionale in cascata al blocco condizionale: questo blocco indicherà che, al 6° colpo diclock, andrà posto E=13. Non è però finita, in quanto le specifiche dicono altre due cose: in primoluogo, dicono che, anche quando E=1, il conteggio deve proseguire, per cui dobbiamo comunqueprevedere un percorso che ci riporti in T1; in secondo luogo, dicono che bisogna controllare anche ilvalore di A4. Il diagramma si perfeziona allora nel modo seguente:

3 Infatti, quando arriva il 5° colpo di clock, risulta A4 A3A2A1=0100 e quindi il circuito di controllo predispone i segnali necessari

affinché, al colpo di clock successivo (cioè il 6° dall’inizio del funzionamento), venga eseguita l’istruzione E←1.



Statoiniziale

T0

S0 1

Fçç0Açç0

AççA+1

T1

A30 1

Eçç0

Eçç1

A401

Quindi, fin quando la macchina non conta 12 colpi di clock (corrispondenti ad A4A3A2A1=1100),il conteggio prosegue indisturbato, con il solo accorgimento di porre ad 1 il flip-flop E subito dopoaver contato il 4° colpo di clock.

La condizione A4=A3=1 si verifica quando la macchina conta il 12° colpo di clock (che poi è il13° dall’inizio del funzionamento). A questo punto, le specifiche dicono che F va posto ad 1 (il cheavverrà al colpo di clock successivo) e che il conteggio deve essere interrotto: quindi, al 14° colpo diclock, la macchina si porta in uno stato T2 in corrispondenza del quale viene eseguita l’istruzioneF←1 ma non viene più effettuato alcun conteggio. Al colpo di clock ancora successivo, la macchinasi porterà nuovamente nello stato iniziale T0, dal quale aspetterà l’arrivo del segnale di START peravviare un altro conteggio.

Il diagramma di flusso si perfeziona quindi nel modo seguente:



Statoiniziale

T0

S0 1

Fçç0Açç0

AççA+1

T1

A30 1

Eçç0

Eçç1

A401

Fçç1

T2

Sequenza temporale delle operazioni e relativa tabella

Ogni blocco del diagramma di flusso specifica dunque le operazioni che devono essere effettuatedalla macchina. Le operazioni specificate all’interno dei blocchi di stato e dei blocchi decisionalisono realizzate dall’elaboratore dei dati, mentre invece il cambio da uno stato all’altro è determinatodal circuito di controllo.

Al fine di comprendere ancora meglio la sequenza temporale con cui evolve il funzionamentodella macchina, possiamo elencare, in una opportuna tabella, la sequenza delle operazioni compiutead ogni singolo impulso di clock. La tabella risulta essere la seguente:



°°°°°°°°°°°°°°

14101011

13000011

12001101

11000101

10001001

9010001

8011110

7010110

6011010

5000010

4001100

3000100

2001000

10?0000T

\??????T

clock di colpoFEAAAAstato

1

0

1234

Lo stato di partenza T0 è uno stato in cui non possiamo conoscere, a priori, il contenuto delcontatore A e dei due flip-flop E ed F, per cui abbiamo lasciato in bianco le corrispondenti caselle.

Supponiamo che, in un certo istante, arrivi (in modo asincrono) l’impulso di START: sappiamo,allora, che, non appena arriva il 1° colpo di clock, sia A sia F vengono azzerati e la macchina si portanello stato T1, pronta ad iniziare il conteggio.

Al 2° colpo di clock comincia il conteggio, per cui, non appena arriva tale colpo di clock, vengonoeffettuate 3 operazioni successive: in primo luogo, viene incrementato A; in secondo luogo, vienecontrollato il valore di A3 e, dato che A3=0, viene anche azzerato il flip-flop E. Questa sequenza dioperazioni chiarisce ancora una volta il modo di funzionamento di una ASM: non appena arriva uncolpo di clock, vengono eseguite tutte le operazioni indicate nel blocco di stato e in eventualisuccessivi blocchi condizionali e blocchi decisionali. Il funzionamento si arresta, per aspettare ilsuccessivo colpo di clock, quando deve essere effettuata una operazione contenuta in un blocco distato, sia esso associato ad un nuovo stato o, come in questo caso, allo stesso stato precedente. Inaltre parole, partendo dallo stato T1, la macchina esegue sia l’istruzione A←A+1 contenuta nelblocco di stato corrispondente a T1, sia il confronto su A3 previsto dal successivo bloccocondizionale sia infine l’istruzione E←0 prevista dal successivo blocco decisionale. Dopo di che siferma, in quanto dovrebbe eseguire nuovamente l’istruzione A←A+1, per la quale deve peròaspettare il colpo di clock successivo.

Dopo il 2° colpo di clock, il conteggio prosegue fino al 5° colpo di clock: infatti, appena arrivaquesto colpo di clock, il contenuto di A viene impostato a 0100 e viene perciò rilevata la condizioneA3=1, la quale impone che al successivo colpo di clock, pur continuando regolarmente il conteggio(visto che è ancora A4=0), il flip-flop E venga posto ad 1. E’ importante notare la relazione tral’istante in cui A3 diventa 1 e l’istante in cui E viene posto ad 1: quando A=0011, il colpo di clocksuccessivo incrementa A al valore 0100, ma solo il colpo di clock successivo può dare lacommutazione di E da 0 ad 1; infatti, perché ci possa essere la commutazione di E, il valore di A3

deve già essere 1 quando arriva l’impulso di clock, in modo che il circuito di controllo abbia giàpredisposto la commutazione di E.



Il conteggio prosegue fino al 9° colpo di clock, in corrispondenza del quale diventa A4=1 edA3=0: a questo punto, al successivo colpo di clock viene nuovamente azzerato il flip-flop E ed ilconteggio riprende.

Al 13° colpo di clock il contenuto del registro diventa 1100 e viene perciò rivelata la condizioneA4=A3=1; tuttavia, dato che, prima che arrivasse il 13° colpo di clock, era ancora A4=0 e A3=1, ènecessario un ulteriore colpo di clock affinché il circuito di controllo riconosca la condizioneA4=A3=1 e predisponga perciò la commutazione di F. Quindi, quando arriva il 14° colpo di clock, Fcommuta ad 1 e la macchina di porta nello stato T2. A questo punto, il conteggio non deve piùriprendere, per cui, all’ulteriore colpo di clock, la macchina si riporta nello stato iniziale T0,lasciando invariato il contenuto del contatore e dei flip-flop E ed F. Siamo perciò in grado soloadesso di completare la tabella, assegnando i valori corrispondenti a T0:

°°°°°°°°°°°°°°°

15111011T

14101011T

13000011

12001101

11000101

10001001

9010001

8011110

7010110

6011010

5000010

4001100

3000100

2001000

10?0000T

\111011T

clock di colpoFEAAAAstato

0

2

1

0

1234

Ribadiamo ancora una volta il concetto per cui il circuito di controllo genera i segnali per tutte leoperazioni specificate nel blocco dello stato presente prima dell’arrivo del colpo di clock; in questomodo, non appena tale colpo di clock arriva, le suddette operazioni (sui registri e sui flip-flop,includendo anche quelli che costituiscono lo stesso circuito di controllo, come si vedrà) vengonorealmente eseguite.

Diagramma degli stati del circuito di controllo

A questo punto, possiamo tracciare un diagramma degli stati corrispondente alla tabella appenacompletata, indicando l’evoluzione (non più temporale) tra i tre stati T0, T1 e T2 appena individuati.Sarà, ovviamente, il diagramma degli stati relativo al solo circuito di controllo, in quanto solo questocircuito rappresenta una macchina sequenziale sincrona, le cui transizioni di stato determinano poispecifiche operazioni da parte dell’elaboratore dei dati.

Dalla tabella trovata prima, si ricava dunque il seguente diagramma:



In questo diagramma abbiamo indicato, sugli archi orientati, i valori di S,A3 ed A4, che in praticarappresentano gli ingressi al circuito di controllo, in quanto quest’ultimo cambia stato o rimane nellostesso stato in funzione proprio dei valori di tali variabili:

• partendo da T0, rimaniamo in T0, qualunque siano i valori di A3 ed A4, fin quando S=0;appena S=1, andiamo invece in T1;

• partendo da T1, non ci interessa più il valore di S, ma solo i valori di A3 ed A4: rimaniamo inT1 fin quando A3 ed A4 non sono contemporaneamente uguali ad 1, mentre passiamo in T2

non appena questa condizione si verifica;

• infine, partendo da T2, qualunque sia il valore di S,A3 ed A4, passiamo comunque in T0.

Questo diagramma ci serve per costruire uno schema a blocchi più dettagliato del funzionamentodella macchina. In base allo schema generale di una ASM visto all’inizio del capitolo, dovremodisporre di un circuito di controllo che comanda sia il registro A sia i due flip-flop E ed F, secondouno schema di principio del tipo seguente:

Circuitodi

controllo

start Flip-FlopE

Flip-FlopF

Contatore A

clock

Il circuito di controllo, una volta ricevuto l’impulso di START, avvia il funzionamento dell’interamacchina, impostando di volta in volta le operazioni sul contatore e sui due flip-flop. Nel farequesto, però, controlla anche il contenuto del contatore A, al fine di individuare il verificarsi dellecondizioni A3=1 e A4=1.



Tutti i dispositivi sono comandati dallo stesso clock, in quanto la macchina considerata è unatradizionale macchina sincrona.

Possiamo anche perfezionare questo schema, in quanto è evidente che le informazioni che dalcontatore giungono al circuito di controllo sono solo i valori di A3 ed A4, mentre non interessanoquelli di A2 ed A1. Non solo, ma possiamo anche distinguere, tra i segnali che il circuito di controlloinvia al contatore, il segnale che impone l’incremento di 1 (segnale di conteggio) ed il segnale checonsente l’azzeramento del contatore (segnale di clear) ogni volta che arriva l’impulso di start:

Circuitodi

controllo

start Flip-FlopE

Flip-FlopF

Contatore A

clock

A3

A4 clear

conteggio

Possiamo ulteriormente perfezionare lo schema scegliendo il tipo di flip-flop che vogliamo usareper realizzare E ed F: se scegliamo dei flip-flop con un solo ingresso (tipo T o tipo D), lo schemarimane invariato, in quanto il circuito di controllo dovrà inviare un unico segnale per ognuno di essi.Al contrario, se scegliamo flip-flop di tipo J-K, allora il circuito di controllo dovrà ancora generareun segnale per ogni flip-flop, ma poi servirà un opportuno circuito combinatorio che sulla base di talisegnali vada a generare i due ingressi di ciascun flip-flop:

Circuitodi

controllo

start

Contatore A

clock

A3

A4 clear

conteggio

Circuitocombinatorio

JF

KF

QF

JE

KE

QE



Sintetizzazione del circuito di controllo

A questo punto, non resta che sintetizzare il circuito di controllo ed il circuito combinatorio per ilpilotaggio dei flip-flop. Cominciamo dal circuito di controllo, che è una normale macchinasequenziale sincrona completamente specificata. La sua tabella degli stati si ricava direttamente daldiagramma degli stati trovato prima e riportato nuovamente qui di seguito:

La corrispondente tabella degli stati è la seguente (avendo 3 ingressi al circuito di controllo, ossiaS,A3 ed A4, dovremo considerare 8 combinazioni binarie di ingresso, che disponiamo, come al solito,secondo un codice Grey, in modo da facilitare il passaggio dalla tabella alle mappe di Karnaugh):

000000002

112112111

111100000

43

TTTTTTTTT

TTTTTTTTT

TTTTTTTTT

100101111110010011001000ASA\.p.s

A questa tabella degli stati dobbiamo aggiungere quella delle uscite, se vogliamo sintetizzare ilcontrollore in modo completo. Quante uscite ha il controllore? Se trascuriamo il segnale di CLEARche il controllore deve inviare al contatore A, è evidente che ci servono 3 uscite: 2 di esse servono apilotare i flip-flop E ed F, mentre l’altra serve a pilotare il conteggio del contatore A. Indichiamoallora le uscite con z0,z1,z2. Dobbiamo ricavare i valori di queste uscite ed è evidente che possiamoschematizzare la macchina come macchina di Moore, in quanto tali uscite dipendono solo dagli statie non dagli ingressi.

Facciamo allora una scelta che ci semplificherà i compiti più avanti:

100T

010T

001T

zzz.p.s

2

1

0

210

Perché questa scelta è particolarmente vantaggiosa per noi? Il fatto che, in ogni stato, una solauscita per volta valga 1 consentirà di semplificare il circuito combinatorio che, sulla base dei valoridi tale uscite, dovrà pilotare i flip-flop E ed F.

Una volta nota la tabella degli stati e delle uscite della macchina sequenziale sincrona darealizzare, dobbiamo procedere all’assegnamento, ossia alla codifica binaria dei 3 stati dellamacchina. Senza ricercare assegnamenti particolari, consideriamo il seguente: T0=00, T1=01 e T2=11(mentre rimane non assegnata la configurazione 10).



La tabella degli stati e delle uscite diventa dunque la seguente:

100000000000000000011T

010010111010111010101T

001010101010000000000T

zzz100101111110010011001000ASA\yy

2

1

0

2104321

===

Fatto questo, possiamo sintetizzare la macchina sequenziale sincrona che costituisce il circuito dicontrollo: precisamente, dobbiamo sintetizzare le 3 uscite z0,z1,z2 e, nell’ipotesi di scegliere flip-flopJ-K per realizzare la parte di memoria, le funzioni J1,K1, J2,K2. C’è, però, una sostanziale differenzatra le varie funzioni da sintetizzare: mentre le uscite dipendono solo dallo stato, per cui sonofunzioni di 2 sole variabili (y1 ed y2), le altre 4 funzioni dipendono anche dall’ingresso, per cui sonofunzioni di 5 variabili (y1,y2,S,A3,A4), la cui sintesi risulta perciò più complessa.

Cominciamo allora dalla sintesi delle 3 uscite, che sono immediate, in quanto dobbiamo usaremappe di Karnaugh a 2 sole variabili:

20

21

'yz

1

0

10y\y

=

XX11

211

21

y'yz

1

0

10y\y

=

XX11

12

21

yz

1

0

10y\y

=

11XX

In ciascuna di queste 3 mappe compare la condizione don’t care corrispondente al fatto che laconfigurazione binaria 10 non è stata usata per la codifica degli stati.

Possiamo adesso passare alle funzioni J1,K1,J2,K2, per le quali necessiteremo di mappe diKarnaugh a 5 variabili (cioè coppie di mappe a 4 variabili), che vanno costruite basandosi sullatabella di pilotaggio del flip-flop di tipo J-K, riportata qui di seguito:

0X11

RESET1X01

SETX110

X000

KJQQ +

Tutte le mappe conterranno delle condizioni don’t care: ci sono quelle legate al fatto che laconfigurazione binaria 10 non è stata usata per la codifica degli stati e quelle dovute al pilotaggio delflip-flop.

Abbiamo quanto segue (seguendo criteri già visti nel capitolo sui circuiti sequenziali sincroni):

• le mappe di Karnaugh delle funzioni J1 e K1 si ottengono considerando la prima colonna dellostato presente e la prima colonna degli stati successivi:



1S10

11

01

00

10110100AA\yy

0S10

11

01

00

10110100AA\yy

101198

14151312

6754

2310

4321

101198

14151312

6754

2310

4321

==XXXXXXXXXXXXXXXX

11

XXXXXXXXXXXXXXXX

XX

4321 AAy)31,23,15,7(J ==

1S10

11

01

00

10110100AA\yy

0S10

11

01

00

10110100AA\yy

101198

14151312

6754

23104321

101198

14151312

6754

23104321

==XXXXXXXX11111111XXXXXXXXXXXXXXXX

XXXXXXXX11111111XXXXXXXXXXXXXXXX

1K1 =

• le mappe di Karnaugh delle funzioni J2 e K2 si ottengono invece considerando la secondacolonna dello stato presente e la seconda colonna degli stati successivi:

1S10

11

01

00

10110100AA\yy

0S10

11

01

00

10110100AA\yy

101198

14151312

6754

23104321

101198

14151312

6754

23104321

==XXXXXXXXXXXXXXXXXXXXXXXX11111111

XXXXXXXXXXXXXXXXXXXXXXXX

SJ 2 =

1S10

11

01

00

10110100AA\yy

0S10

11

01

00

10110100AA\yy

101198

14151312

6754

23104321

101198

14151312

6754

23104321

==XXXXXXXX11111111

XXXXXXXX

XXXXXXXX11111111

XXXXXXXX

12 yK =

Con questo, abbiamo dunque sintetizzato il circuito di controllo, il cui schema logico è dunque ilseguente:



Non abbiamo indicato la parte combinatoria che dà origine, sulla base dei valori di z0,z1 e z2,alsegnale che comanda l’incremento del contatore ad ogni colpo di clock. Il motivo è molto semplice:l’incremento del contatore viene effettuato solo quando il circuito di controllo si trova nello stato T1

e, in corrispondenza di questo stato, l’unica variabile di uscita che vale 1 è z1. Di conseguenza, ilsegnale di comando per l’incremento del contatore sarà proprio z1: possiamo allora immaginare cheil contatore A non riceva direttamente il segnale di clock principale, ma l’AND di tale segnale conz1, in modo tale che il conteggio dei colpi di clock avvenga solo quando z1=1. In pratica, riprendendoquanto già detto in precedenza a proposito dei circuiti sincroni, z1 sarà un segnale del tipo shiftcontrol input: solo quando z1=1, il clock attraversa la porta AND e giunge ai flip-flop del contatore:



Il blocco in alto a sinistra è chiaramente il circuito di controllo, del quale sono indicati solo gliingressi, le uscite ed il clock.

Questo schema andrebbe ancora eventualmente perfezionato con il segnale di clear che il circuitodi controllo invia al contatore ogni volta che arriva lo start. Dato che il clear deve avvenire quando ilcircuito di controllo si trova nello stato T0 e dato che, in questo stato, l’unica uscita =1 è z0, ilsegnale di clear sarà semplicemente l’AND tra lo start e z0:

Sintesi del circuito di pilotaggio di E ed F

Manca adesso solo la sintetizzazione del circuito combinatorio di pilotaggio dei flip-flop E ed F.Il pilotaggio di questi flip-flop avviene mediante le 3 uscite z0,z1 e z2 del circuito di controllo. Inparticolare, avendo imposto che, di queste uscite, una sola per volta possa andare ad 1, possiamoseguire un criterio del tutto analogo a quello visto per i circuiti sequenziali asincroni in modoimpulsivo, ossia possiamo pensare a funzioni di pilotaggio dei flip-flop fatte nel modo seguente:

++=++=

→

++=++=

→

2F21F10F0F

2F21F10F0F

2E21E10E0E

2E21E10E0E

KzKzKzK

JzJzJzJ F Flop-Flip

KzKzKzK

JzJzJzJ E Flop-Flip

Per sintetizzare queste funzioni, dobbiamo rifarci alla tabella nella quale abbiamo indicato lasuccessione temporale dei valori assunti dai bit del contatore A e dai flip-flop E ed F, in modo dapoter fissare, per ogni situazione, i valori delle funzioni JE,KE,JF,KF che diano le transizioni volute:



011011T14

00001113

00110112

00010111

00100110

0100019

0111108

0101107

0110106

0000105

0011004

0001003

0010002

010000T1

111011T

KJKJFEAAAAclock

2

1

0

FFEE1234

°°°°°

°°°°°°°°°

Dobbiamo completare questa tabella in modo che si abbiano le transizioni indicate per le uscitedei flip-flop E ed F. Cominciamo, ad esempio, dal flip-flop E:

• per passare nello stato T1, in cui E=1, provenendo dallo stato T0, in cui è sempre E=1, la tabelladi pilotaggio del flip-flop J-K ci dice che dobbiamo porre a 0 il K, mentre possiamo darequalsiasi valore al J, per cui, nella riga corrispondente a T0, dobbiamo porre JE=X e KE=0;questo significa, in pratica, che il circuito di controllo, quando si trova nello stato T0, siaccorge di dover mantenere ad 1 il flip-flop E per cui predispone i due ingressi JE e KE in modoche, al successivo colpo di clock, essi abbiano effetto sul flip-flop;

• una volta avviato il conteggio (quindi A=0000), al successivo colpo di clock (0001) deverisultare E=0, cioè E deve commutare da 1 a 0: allora la tabella di pilotaggio dice chedobbiamo porre JE=X e KE=1;

• questa configurazione si mantiene fino al 5° colpo di clock (0100), in quanto, al colpo di clocksuccessivo, E deve commutare da 0 ad 1: questo significa che, nella riga corrispondente al 5°colpo di clock, dobbiamo porre JE=1 e KE=X;

• proseguendo in questo modo, è immediato riempire la tabella:

0X011011T14

X100001113

X000110112

X000010111

X000100110

1X0100019

0X0111108

0X0101107

0X0110106

X10000105

X00011004

X00001003

X00010002

1X010000T1

0X111011T

KJKJFEAAAAclock

2

1

0

FFEE1234

°°°°°

°°°°°°°°°



Adesso dobbiamo ripetere lo stesso discorso sul flip-flop F, ma qui la cosa è più semplice: infatti,le uniche due commutazioni si hanno nel passaggio da T2 a T0 (nel quale caso F va da 0 ad 1, per cuirichiede JF=1 e KF=X) e nel passaggio da T0 a T1 (nel quale caso F va da 1 a 0, per cui richiede JF=Xe KF=1). Nei casi rimanenti, F rimane a 0, per cui dobbiamo porre JF=0 e KF=X:

X10X011011T14

X0X100001113

X0X000110112

X0X000010111

X0X000100110

X01X0100019

X00X0111108

X00X0101107

X00X0110106

X0X10000105

X0X00011004

X0X00001003

X0X00010002

X01X010000T1

1X0X111011T

KJKJFEAAAAclock

2

1

0

FFEE1234

°°°°°°°°°°°°°°

Dobbiamo dunque fare in modo che dalle funzioni di uscita z0,z1 e z2 che sono state sintetizzateprima si possa ottenere il pilotaggio appena descritto dei flip-flop E ed F, secondo le relazioni

++=++=

→

++=

++=→

2F21F10F0F

2F21F10F0F

2E21E10E0E

2E21E10E0E

KzKzKzK

JzJzJzJ F Flop-Flip

KzKzKzK

JzJzJzJ E Flop-Flip

Dobbiamo dunque sintetizzare 12 funzioni, 6 per ogni flip-flop, e si tratta evidentemente difunzioni delle 4 variabili A4, A3 , A2, A1. Useremo, allora, per ciascuna di esse, mappe di Karnaugh a4 variabili. Partiamo dal flip-flop E:

• cominciamo dalla funzione JE0, relativa alla variabile z0: dato che JE0 va in AND con z0 e datoche quest’ultima vale 1 solo per lo stato T0, è evidente che JE0 sarà definita solo per lacombinazione dei valori di A4, A3 , A2, A1 corrispondente a T0, ossia la combinazione 1101;per tutte le altre combinazioni non ci interessa determinare JE0, che sarà comunque 0 in quantoè nulla la z0; avremo dunque condizioni don’t care per tutte le combinazioni di A4, A3 , A2, A1

diverse da 1101; d’altra parte, per la combinazione 1101 abbiamo trovato prima che JE=X, per

cui la mappa è composta tutta da condizioni don’t care, il che significa che 0J 0E = ;



• per la funzione KE0 vale lo stesso identico discorso di JE0 , con l’unica differenza che, incorrispondenza della combinazione 1101 delle variabili A4, A3 , A2, A1 , abbiamo trovato prima

che KE0=0: abbiamo dunque anche in questo caso che 0K 0E =

• passiamo adesso alla funzione JE1, relativa alla variabile z1: dato che JE1 va in AND con z1 edato che quest’ultima vale 1 solo per lo stato T1, è evidente che JE1 sarà definita solo per lecombinazioni dei valori di A4, A3 , A2, A1 corrispondenti a T1, mentre avrà condizioni don’tcare per tutte le altre combinazioni; basandoci sulla tabella ottenuta prima, abbiamo allora laseguente mappa:

→

XXXXXXXXXXXX1111XXXX

101198

14151312

6754

23104321

10

11

01

00

10110100AA\AA

31E AJ =

• per la funzione KE1 vale lo stesso discorso a proposito delle combinazioni di A4, A3 , A2, A1

per le quali è definita e quelle per le quali presenta sicuramente condizioni don’t care:

→

101198

14151312

6754

23104321

10

11

01

00

10110100AA\AA

XXXXXXXXXXXXXXXXXX

XXXX1111 31E 'AK =

• passiamo ora alla funzione JE2, relativa alla variabile z2: dato che JE2 va in AND con z2 e datoche quest’ultima vale 1 solo per lo stato T2, è evidente che JE2 sarà definita solo per lacombinazione dei valori di A4, A3 , A2, A1 corrispondente a T2, ossia la combinazione 1101,mentre avrà condizioni don’t care per tutte le altre combinazioni; d’altra parte, abbiamoricavato prima che, in corrispondenza di 1101, la funzione JE presenta ancora una condizionedon’t care, per cui abbiamo ancora una volta una mappa tutta di condizioni don’t care, cui

corrisponde evidentemente 0J 2E =

• discorso del tutto analogo per la funzione KE2 , la quale è definita solo per la combinazione1101AAAA 1234 = : dato che la funzione KE presenta uno 0 in corrispondenza di tale

combinazione, deduciamo anche qui che 0K 2E =

Possiamo dunque concludere, per il flip-flop E, che le funzioni di pilotaggio sono le seguenti:

=++==++=

→312E21E10E0E

312E21E10E0E

'AzKzKzKzK

AzJzJzJzJ E Flop-Flip

Adesso dobbiamo ripetere lo stesso ragionamento per il flip-flop F, per il quale la cosa è ancorapiù semplice, dato quello che abbiamo ricavato prima nella tabella temporale: si trova infatti che

0KKJJ 2F1F1F0F ==== e poi che 1JK 2F0F == . Deduciamo dunque che



==

→0F

2F

zK

zJ F Flop-Flip

Adesso abbiamo davvero concluso, per cui possiamo disegnare lo schema logico dell’interamacchina:

Autore: SANDRO PETRIZZELLIe-mail: [email protected]

sito personale: http://users.iol.it/sandrysuccursale: http://digilander.iol.it/sandry1

Appunti di Elettronica Digitale - Libero...

Documents

Transcript of Appunti di Elettronica Digitale - Libero...